Gossip Protocol

A list nobody owns

Every node in a 1,000-node storage cluster carries a list of all the others: one row per node, with its address, the data ranges it serves and whether it is believed alive. No server owns that list. Each node holds its own copy, and the copies stay close only because the nodes keep telling each other what they know, a few at a time.

That is a gossip protocol, also called an epidemic protocol, because information moves through the cluster the way an infection moves through a population. The list is the membership list. Gossip keeps it in step without a central server that every node would depend on and that would have to hear from all 1,000. Two things have to travel through it: a new row, which is news, and the end of a row whose node has died, which is a silence. News is easier, so start there.

Node 1001 joins

A new node, 1001, starts up knowing a single address, node 9's, listed in its configuration as a seed. It contacts node 9, which sends back its list, and from then on it does what every node does once per round, here once a second:

1. It picks a peer at random from its membership list.
2. It sends that peer a digest: for each entry, the node's id and the version it holds, without the state itself.
3. The peer replies with the entries where its own version is newer, and asks for the ones where the sender's is; a missing entry counts as the oldest version.
4. The sender sends those, and both sides keep, entry by entry, whichever version is higher.

Sending your entries to the peer is push, asking for the peer's is pull, and the four steps above do both, push-pull. How many peers a node contacts per round is its fan-out; in this cluster it is one.

Diagram components: Service, Service, Service, Service, Service.

Each node starts one exchange per round with a random peer. Node 9 is in two this round, its own and node 1001's; being picked by several peers is normal.

Ten rounds to reach a thousand

While few nodes know that 1001 exists, push-pull roughly triples their number each round: every node that knows tells the peer it picked, and about as many again learn it by asking one that knows. Near the end the pull half does the work: a node that has not heard asks a random peer, who almost certainly has, so the share still in the dark falls at least as fast as its square, 1% to 0.01% or less. In a simulation of this cluster with no lost messages, the news reached every node in 9.2 rounds on average and in at most 11 over 2,000 runs, and doubling the cluster added less than one round.

Each node's number of exchanges stays flat meanwhile: it starts one exchange per round and is picked by one other node on average, about two exchanges a round whether the cluster has 100 nodes or 10,000. Every node heartbeating every other each second would instead mean 999 messages out and 999 in per node. What does grow is the size of an exchange, since a digest names every member; that is why it carries versions only, and state crosses the wire only for entries that differ.

Spreading a silence

When node 9 loses power, nothing new exists that a node could pass on, so what gets gossiped is a sign of life. Each node's entry carries a heartbeat counter, which the node itself increments every round. Node 412 records, on its own clock, when it last saw node 9's counter go up, and if that was longer ago than a timeout, 15 seconds in this cluster, it marks node 9 dead. No message ever says so: each node reaches the verdict on its own, by its own clock, so no clocks need to be synchronized.

A restarted node counts from zero again, so each entry also carries a generation set at startup, higher than the one before it (the start time works if the clock never runs backward), compared before the counter. And a dead entry is kept for a while before being forgotten, or peers that have not noticed yet would gossip it back in as a new member.

Why 15 seconds, when node 9 bumped its counter every second? Because node 412 hears each new value secondhand, several rounds late: in the same simulation, the counter one node held for another was typically 5 to 6 seconds old, and in rare cases close to 10. A timeout near those ages would declare live nodes dead all day, and real clusters also lose messages and have slow machines, so the timeout keeps a margin; every second of it trades fewer false verdicts for a slower true one. A φ accrual failure detector (phi accrual) replaces the fixed timeout with a suspicion level computed from the gaps node 412 has actually seen from node 9, so a node with irregular gaps has to stay silent longer before it is suspected; Cassandra uses one.

Asking a third node

Gossiping a heartbeat for every member makes each exchange grow with the cluster, and every verdict waits for news that arrives secondhand. SWIM, a protocol published in 2002, splits the two jobs. Detection is a probe: every protocol period, each node pings one member chosen at random and waits briefly for an ack. Dissemination is gossip: what the probes conclude rides on the pings and acks themselves. When node 17 probes node 9:

1. Node 17 pings node 9 and gets no ack in time.
2. Node 17 asks a few other members, node 230 among them, to ping node 9 on its behalf, a ping-req.
3. None of them gets an ack either, so node 17 marks node 9 suspect and gossips that.
4. If node 9 is alive, it hears that it is suspected and refutes it by gossiping a higher incarnation number for itself.
5. If no refutation arrives before the suspicion timeout, node 9 is declared dead, and that is gossiped too.

Diagram components: Service, Service, Service.

Node 17 got no answer from node 9 and asks node 230 to try. One ack along any route clears node 9; silence on every route makes it a suspect, not yet dead.

The indirect probe saves node 9 when the trouble is only the direct path between node 17 and node 9, and the suspect stage gives a node that was only paused a chance to answer before anyone acts. HashiCorp's Serf and Consul build their membership on SWIM.

What the list cannot promise

Gossip converges: if membership stops changing and messages keep getting through, every list ends up the same. At any given moment it promises much less:

• No agreement. Mid-spread, some nodes list 1001 and some do not, and for seconds after node 9 dies some still count it alive. A decision that needs one answer, such as which node runs a job, cannot be read off the list; Leader Election covers how a cluster settles on one.
• A suspect may be alive. A long garbage-collection pause or a network partition looks exactly like death to every detector above. What to do about a node declared dead that keeps acting is the subject of Distributed locks & leader election.
• The highest version wins because a counter has one writer. Only node 9 increments node 9's counter, so the highest value is simply the latest; SWIM's suspect and dead notices, written by other nodes, need fixed precedence rules instead. A value several nodes may update concurrently needs a real merge, the subject of Conflict resolution for concurrent writes.

How replicas of the data itself are kept is Replication & read replicas, and how a client finds a healthy instance by name is Service discovery & the mesh and Service Registry.

Drawing it without a center

The Gossip Protocol challenge allows eight nodes, and the first diagram above already uses five: peers of equal role, each in an exchange with a random peer. Add a sixth whose heartbeat counter has stopped, mark it dead once the timeout passes, and place the Gossip Protocol node beside them; the brief also wants news shown spreading until every peer converges, which the edge labels can carry. The palette offers a Message Broker and a Coordinator, the two things this design exists to do without, so either one puts back the center the brief asks you to remove.