Techniques disclosed herein provide a messaging protocol for a distributed system. In one embodiment, each message constructed according to the messaging protocol includes a field for a list of globally unique identifiers (GUIDs) of nodes that should not reply to the message. A new node joining the system sends a message requesting system state information and including an empty GUID list, indicating that all nodes receiving the message should reply. In normal operation, the system's state information is synchronized among all nodes at regular intervals by exchanging messages indicating local state changes at each node, and including GUID list fields specifying all other nodes' GUIDs so that no nodes reply. A node which identifies messages that should have been received from another node but are missing transmits a message requesting the missing messages, with a GUID list including all nodes other than the other node that sent the missing messages.