The present document describes systems and methods that monitor the health of a number of network-connected databases. In various embodiments, a health management subsystem measures one or more health parameters of a database and determines whether the database is operating properly. When the database is operating properly, a heartbeat associated with the database is generated. Heartbeat information is exchanged with other health management subsystems using a gossip-style protocol. Using the received and generated heartbeats, a health state table is provided that includes a health state for each database.