Systems and methods for coordinated discovery of the status of network routes by hosts in a network. A plurality of host devices is connected to at least one of a plurality of egress devices. Each of the plurality of host devices is assigned to at least one cluster group. A cluster group may include one or more host devices connected to a common egress device. A master node is selected from the members of each cluster group. The master node coordinates the issuance of probe messages from the master node and other members of the cluster group to the common egress device. The probes provide the status of a network route to and through the common egress device. The master node makes the status available to the members of the cluster group. A member of the cluster group may obtain the status by communicating with the master node or by communicating with other members of its cluster group.