The present invention extends to methods, systems, and computer program products for appropriately detecting node failures in a rendezvous federation. A monitor node monitors a subject node. The subject node intermittently renews a time-to-live duration value with the monitor node to indicate the monitor node that the subject node has not failed. In some embodiments, each node in a pair of nodes monitors the other nodes in the pair of nodes. Thus, each node is a subject node and a monitor node. In further embodiments, an arbitration facility arbitrates failure reports.