This application sets forth various techniques for monitoring a status of a service. According to some embodiments, a DNS server can implement a health check engine that monitors the status of the service in order to implement round-robin DNS among a plurality of availability zones. Each service instance for the service can include a monitoring agent configured to (1) monitor the status of the service instance, and (2) respond to health check messages received from the health check engine. The monitoring agent can also be configured to (1) collect statistics associated with one or more service dependencies of the service instance during a tracking window, (2) calculate at least one ratio based on the statistics collected during the tracking window, and (3) generate the status of the service instance by comparing the at least one ratio to a threshold value.