Gossip Protocols Explained: How Clusters Spread News

Gossip is the reason a 1,000-node cluster can learn that one node died without any node being in charge of telling the others. Every node, a few times a second, picks a handful of random peers and tells them what it knows. Those peers do the same. Within a few seconds the fact is everywhere. We ran a simulation to put numbers on it: a fact starting on one node reached all 1,000 nodes in about 11 rounds, and all 10,000 in about 14.

That is the whole idea. The rest of this post is why it works, what it costs, and where it is the wrong choice.

The problem gossip solves

Say you run 200 database nodes. Nodes join, nodes crash, and every node needs a reasonably current picture of who is alive. There are three obvious designs.

1. A central registry. Every node reports to one service. It works until that service is down, and then the cluster cannot see itself.
2. Everyone tells everyone. Each change sends N messages from N nodes, so traffic grows with the square of the cluster size. At 200 nodes it is tolerable. At 5,000 it will saturate your network on a bad day.
3. A ring of heartbeats. Each node watches its neighbors. It is cheap, but a break in the ring splits the picture.

Gossip is a fourth option. No central service, constant load per node, and no special topology. The price is that you get eventual knowledge, not instant knowledge.

How a gossip round works

Every node runs the same loop:

1. Wait one interval (often a second or less).
2. Pick fanout random peers (2 or 3 is typical).
3. Send them your state, or a digest of it.
4. Merge whatever they send back, keeping the newer version of each entry.

Entries carry a version number or timestamp so the merge has a rule: higher version wins. That is the only coordination in the system.

There are three flavors. Push sends your news to peers. Pull asks peers for theirs. Push-pull does both in one exchange, and it is what most production systems use because it converges fastest and repairs missed updates.

Why it takes about log(N) rounds

Think about one fact on one node. Round one, two nodes know it. Round two, up to four. The spread doubles, then triples, as long as most picks land on nodes that have not heard yet. Early rounds grow exponentially.

Late rounds are slower. When 95% of the cluster knows the fact, most random picks hit someone who already knows. The last few nodes take disproportionately long, which is why the total is “about log N” and not “exactly log N”.

Here is a push-gossip simulation you can run. It starts a rumor on node 0 and counts rounds until every node has it:

import random, statistics

def rounds_to_full(n, fanout, seed):
    rnd = random.Random(seed)
    informed = {0}
    rounds = 0
    while len(informed) < n:
        newly = set()
        for _ in informed:
            for _ in range(fanout):
                newly.add(rnd.randrange(n))   # pick a random peer
        informed |= newly
        rounds += 1
    return rounds

for n in (100, 1000, 10000):
    for fanout in (1, 2, 3):
        runs = [rounds_to_full(n, fanout, s) for s in range(50)]
        print(n, fanout, round(statistics.mean(runs), 1), min(runs), max(runs))

Mean rounds over 50 seeds each:

Nodes	Fanout 1	Fanout 2	Fanout 3
100	12.4	7.4	5.7
1,000	18.2	10.7	8.2
10,000	23.6	13.8	10.5

Two things stand out. Growing the cluster by 100x, from 100 to 10,000 nodes, added only about six rounds at fanout 2. And the jump from fanout 1 to fanout 2 helps far more than the jump from 2 to 3. Diminishing returns arrive quickly, so most systems stay at 2 or 3.

One caveat on this simulation: it is simplified. Nodes pick uniformly at random from the whole cluster, messages never get lost, and every node’s clock ticks in lockstep. Real clusters have none of those. It shows the shape of the curve, not your production numbers.

Failure detection: where gossip earns its keep

Spreading news is half the job. The other half is noticing a node is gone.

The naive approach is a heartbeat counter. Each node increments its own counter and gossips it. If a node’s counter has not changed in some time, it is suspected dead. That works, but a slow network gets healthy nodes marked dead.

The SWIM protocol (Das, Gupta and Motivala, 2002) improves on this with indirect probes. When node A cannot reach node B, A does not declare B dead. It asks a few other nodes to try B on A’s behalf. Only if all of them fail does B become suspected, and B gets a window to refute that before it is confirmed dead. One flaky link between A and B no longer triggers a false positive.

Consul’s gossip layer is built on this lineage of ideas, per its documentation, and uses gossip to handle membership and failure detection across the cluster. You see the effect when you run consul members: every node lists the others with an alive, suspect or left status without a central tracker.

What gossip is used for, and what it is not

Systems that use gossip tend to put it on the control plane, not the data path:

• Cassandra uses it to share cluster membership and node state.
• Consul uses it for membership and failure detection.
• Redis Cluster uses a gossip bus so nodes learn about each other’s slots and health.
• Dynamo (the Amazon paper) described gossip-based membership and failure detection for its ring.

None of them use gossip to decide what a user’s value is. That job belongs to quorum reads and writes or to a consensus log.

This is the dividing line. Gossip answers “who is out there, and who looks alive?” It does not answer “who is the leader?” or “did this write commit?” Those questions need agreement, and gossip only offers convergence. Our post on leader election and Raft covers the agreement side. For the tradeoff behind this split, see CAP theorem in practice.

Tradeoffs to know before you build one

• Eventual convergence. For a few seconds, two nodes can hold different views of the cluster. Code that reads membership must tolerate stale data.
• Probabilistic timing. You get “almost certainly within N rounds”, not a hard bound. Plan timeouts with margin.
• Message volume. Each node sends fanout messages per interval, so the cluster sends N times fanout. That is linear in N, which is the point, but state digests that grow with the cluster add up. Systems cap or compress them.
• Hard-to-debug misses. A dropped RPC shows up in a log. A rumor that never reached node 417 does not.
• Merge rules matter. If two nodes can both bump a version number for the same entry, the higher number is not necessarily the right one. Use a single writer per entry, or vector clocks when you cannot.

If you are building this yourself, don’t. Use memberlist (the Go library behind Consul’s gossip) or the membership layer of whatever datastore you already run. Writing a correct failure detector is a multi-month project, and the bugs only show under partial failure.

The takeaway

Gossip trades certainty for scale. Each node does a small, constant amount of work, and the cluster learns facts in roughly log N rounds. Use it to share who is alive and what the topology looks like, and use consensus when the cluster has to agree on something. If your design needs both, use both, and keep them in separate layers.