Gossip Protocol

Each round, a node selects peers at random and runs one of three exchange styles. In push, the node sends its updates to the peer. In pull, it asks the peer for updates. In push-pull, both sides send what they have and reconcile, which converges fastest because every contact corrects both nodes at once.

To keep messages small, nodes attach a version number or logical clock to each entry. When two nodes gossip, they compare versions and keep the newer value for each key. This is how Cassandra spreads schema changes and node state: each node carries a heartbeat counter that only goes up, and a higher counter always wins. A node that has not had its counter bumped in a while is suspected dead.

Failure detection rides on the same channel. A common design is the phi accrual failure detector, used in Cassandra and Akka, which does not give a hard alive or dead answer. Instead it tracks the gap between heartbeats and outputs a suspicion level, so the cluster can tune how trigger-happy it is about declaring nodes down. SWIM, used by HashiCorp Serf and Consul, separates failure detection from membership dissemination and adds indirect probing: if node A cannot reach node B, it asks a few other nodes to ping B before declaring it dead, which cuts down false positives on a flaky network.

Convergence time grows logarithmically with cluster size. With a fan-out of a handful of peers per round, a fact reaches a thousand nodes in roughly ten rounds, so about ten seconds at a one-second interval. Bandwidth per node stays roughly constant no matter how large the cluster gets, which is the whole point.

Apache Cassandra is the textbook case. A Cassandra ring can run hundreds of nodes with no master. Once per second, every node gossips with up to three others: one random live node, sometimes one unreachable node to check if it has recovered, and sometimes a seed node. Through these exchanges, each node learns the token ranges, schema version, and up or down status of every other node, even ones it has never talked to directly.

Suppose a node crashes. Its heartbeat counter stops incrementing. Within a few gossip rounds its neighbors notice the stale counter, their phi accrual detectors raise the suspicion level, and they mark it down in their local view. That down status then gossips outward until the whole ring routes around the dead node. No operator and no central controller was involved at any step.

HashiCorp Consul does the same for service discovery using the Serf library, which implements SWIM. A datacenter of Consul agents gossips membership so that when an agent joins or leaves, every other agent finds out within seconds, and clients can be steered away from a failed service instance automatically.