Gossip: Epidemic Spread Instead of Everyone Telling Everyone

The obvious membership design is that every node heartbeats every other node. It is simple, it gives fast and uniform detection, and it works well — up to about fifty nodes.

The problem is quadratic. N nodes each sending to N−1 peers every interval is N² messages per interval; at N = 1,000 with a one-second interval that is a million messages per second, and — the part that actually kills it — each individual node’s inbound load grows linearly with cluster size. Adding nodes makes every existing node work harder, so the cluster gets less stable as it grows. That is the wrong shape for a scaling mechanism.

Gossip inverts it. Each node contacts a small constant number of random peers per round — often just one to three. Per-node cost is constant in N; total cost is O(N) per round. A 10,000-node cluster costs each node exactly what a 100-node cluster costs it. The cluster’s stability stops depending on its size, which is the property being bought.

The exchange itself is where the elegance lives. In round one, one node knows. In round two, two. Then four, eight — exponential growth until roughly half the cluster knows, after which the limiting factor becomes finding the remaining ignorant nodes. Full dissemination takes O(log N) rounds: about 10 rounds at N = 1,000, about 14 at N = 10,000. The time to reach everyone grows logarithmically while the cost per node stays flat.

Gossip has three variants with genuinely different behaviour, and the distinction is under-taught.

Push. A node with news sends it to random peers. Superb early: while few nodes know, almost every send lands on someone ignorant, and the informed population doubles per round. Terrible at the tail: when 99% already know, almost every message is wasted, and finding the last few nodes takes many rounds of luck.

Pull. Each node asks random peers "what do you have that I do not?" Poor early: while almost nobody knows, most requests come back empty. Excellent at the tail: any ignorant node that asks *anyone* is very likely to hit someone informed, so the remaining ignorant fraction is crushed each round.

Push-pull. Do both in one exchange. You get push’s exponential start and pull’s aggressive tail, and the ignorant fraction falls *doubly* exponentially — roughly squaring the remaining ignorance each round rather than halving it. This is why production gossip implementations exchange state bidirectionally rather than merely announcing.

The complementary trick is rumour-mongering: a node stops actively spreading a fact after it has received it redundantly a few times, on the reasoning that everyone probably has it. This bounds message volume beautifully and introduces a small probability that some node never hears. Systems therefore pair a cheap, fast rumour layer with a slower, complete Anti-Entropy: Repairing Divergence Nobody Reported layer that compares full state and repairs whatever the rumours missed. Speed from rumour, completeness from anti-entropy — that division is the standard architecture, and the reason those two lessons sit next to each other.

Gossip carries state, not events, and this is the design decision that makes it robust. An event ("node 7 failed") must be delivered or it is lost. A versioned state ("as of version 12, node 7 is suspect") can be re-derived from any peer at any time, so a lost message costs latency and nothing else.

Each node therefore keeps, for every member, a tuple of roughly: incarnation, status, version, and application metadata. Merging two views is a per-member comparison — take the entry with the higher incarnation, and within an incarnation the higher version. The merge must be commutative, associative and idempotent, or nodes converge to different answers depending on the order in which they gossiped. That is exactly the CRDT requirement (CRDTs: Deterministic Merge, Not Correct Merge, What "Eventually Converges" Actually Requires), and gossip membership is in practice a small CRDT.

The payload cost is where large clusters get hurt. Naive gossip sends the whole view every round, so payload grows with N and total traffic becomes O(N²) again in bytes, defeating the purpose. Real implementations exchange digests — member plus version only — and transfer full entries just for the members whose versions differ. That keeps the common case small when little is changing.

It also means gossiping large per-node metadata is expensive in a way that is easy to miss. A cluster that gossips a few hundred bytes per node is fine; one that gossips a few kilobytes — token lists for Virtual Nodes: Many Positions per Machine, and Why It Is Not Optional, schema versions, load statistics — multiplies every round by that factor, and startup, in which a node must learn the whole cluster, becomes slow. Several production systems have hit exactly this and responded by moving bulky metadata out of the gossip path.

Gossip is often presented as a free lunch. It is not, and the costs are specific.

No completion signal. The originator never learns that its fact reached everyone, because nobody counts. If your design needs "the whole cluster now knows X before I proceed", gossip cannot give it to you — that requirement is consensus, and it costs a majority round trip.

No bound for any individual node. The O(log N) result is about the population, not about a node. A node behind a flaky link can be many rounds behind while every cluster-level metric looks healthy, and nothing in the protocol notices.

A permanent background cost. Gossip runs whether or not anything is happening. A quiet cluster still exchanges messages forever. It is a small, constant, unavoidable tax, and on very large clusters it is a real line item in CPU and network budgets.

Convergence is not observable. No node can tell the difference between "converged" and "the update has not arrived yet". Any test of the form "wait until the cluster agrees" is not implementable inside the protocol; you can only wait a duration and hope, which is why gossip-based systems are hard to write deterministic tests for.

Rumours can oscillate. Two nodes marking each other suspect, each refuting, can produce a membership table that churns without settling. Incarnation numbers and refutation (Cluster Membership: A Belief, Not a Fact) are what damp this, and without them a partial partition produces a permanently unstable view.