Gossip Protocol

Spreading aliveness without asking a leader

HLC stamps order every write causally and fencing tokens reject the stale holder at 41 versus 42, yet those stamps ride messages between machines that never elected a leader. Your 200-node cache fleet must agree on which machines are alive and who owns which key ranges. A central registry is a single point of failure, meaning one outage blinds everyone, and having every node poll every other node costs O(n squared) messages. Gossip avoids both: each node periodically picks a few random peers and swaps version-stamped digests, so knowledge spreads like neighbors exchanging mail until every mailbox converges, with no coordinator involved.

Rejected alternative: broadcast from one source, which needs that source alive and turns it into a hot spot sending O(n) messages. At 3,000 nodes that is 3,000 sends per update from one box against gossip's 3 sends per node, so the source's NIC saturates while most of the fleet idles. The gossip fix trades immediacy for robustness: each infected node tells a small fanout of peers per round, where a gossip round means one periodic exchange interval, and infected counts multiply until the whole fleet hears. Convergence takes logarithmic rounds, so growth from hundreds to thousands of nodes adds rounds, not new single points of failure.

Round 0: Node A knows {A:alive v3}
Round 1: A gossips to B,C → B,C learn A v3
Round 2: B gossips to D,E → D,E learn A v3 (via B)
... converges in log(n) rounds, even with failures

How versioned digests and indirect probes carry the rumor

Gossip has two intertwined jobs: spreading state and detecting failure. State spreads by infect-and-spread, where each tick a node picks fanout equal to 3 random targets and sends only the delta since their last exchange. Each key carries a monotonically increasing version, meaning a counter that only moves up, and receivers keep the maximum version per key. That maximum-wins merge is eventually consistent, meaning all nodes agree if updates stop, and conflict-free as long as versions never rewind.

What gossip buys in robustness and bills in delay and duplicates

Gossip scales to thousands because every node does equal small work and no election pauses dissemination. The bill arrives three ways: convergence takes seconds depending on interval, messages are redundant because many peers hear the same rumor twice, and delivery has no ordering guarantee, so two nodes can apply the same updates in different orders. That last limit is load-bearing: gossip cannot enforce strong consistency, meaning every reader seeing the same latest write, or total ordering on its own.

How fast a rumor crosses a thousand machines at fanout three

One node learns a new membership version. Every second each informed node tells 3 random peers, so informed counts roughly triple per round after discounting duplicate hits: 1, 4, 13, 40, and onward. A thousand nodes converge in about 7 rounds and ten thousand in about 9, because rounds to infect n scale as log(n) divided by log(fanout plus 1). Broadcast would need a coordinator sending O(n); gossip needs every node sending the same small fanout.

fanout f=3, interval 1s, n=1000 nodes:
  round 0:    1 infected
  round 1:    ~4 infected (1 + 3 new, minus duplicate hits)
  round 2:    ~13 infected
  round 3:    ~40 ... round 6: ~700 ... round 7: ~950+ converged
  rounds to infect n ≈ log(n) / log(f+1) → ~5-7 for n=1000, f=3

Bandwidth per node per round: f × digest size (versions only, ~100 bytes)
  → 3 × 100B × 1/s = 300 B/s per node; trivial until payloads sneak in

The suspicion dance that stops one failed ping from burying a machine

Node A cannot reach node B. Either B died or the link between A and B failed, and declaring death on one timeout would evict healthy machines every time a switch hiccups. SWIM, meaning indirect probing with witnesses, answers by asking two random peers to ping B on A's behalf. Only consensus of failures escalates to suspicion with a higher version, and a live but partitioned B heals by gossiping an even higher incarnation number that wins every comparison without operator action.

Why voting and rumor serve opposite consistency needs

Raft, a leader-based consensus protocol where majorities vote one log into agreement, fits when you need one committed sequence every reader trusts. Gossip fits when you need every node to eventually hear everything without a leader. Randomized delivery has no ordering promise, so versioned last-writer-wins converges but concurrent writes still need vector clocks, meaning per-node counters that detect concurrency, or a consensus layer to resolve safely. Systems that pair both use each for its strength: Cassandra, a wide-column store, detects dead nodes with SWIM-style indirect probes, Consul, a service-mesh and coordination service, runs Serf gossip with SWIM, and Redis Cluster, a clustered in-memory store, gossips slot ownership.

The cost contrast decides. Gossip scales to thousands with no leader and survives partitions, billed in seconds of convergence plus redundant messages. Consensus bills leader bottleneck plus election pauses and buys a single agreed truth. Never spend gossip where a stale read costs money without adding a stronger read path.

Choosing which rumor style matches your payload and loss budget

Naive gossip sends everything everywhere, which wastes bandwidth on large payloads. Anti-entropy compares full digests every round and repairs deltas, which is reliable but chatty. Rumor mongering forwards each new update a few times then forgets, which is cheap but can miss a node. Bimodal multicast mixes both with a fast rumor path plus anti-entropy repair behind it. Cassandra, a wide-column store, leans anti-entropy for endpoint state that must converge, while monitoring pipelines lean rumor for fire-and-forget metrics that self-heal next round.

Payload budget that ships: digests of endpoint plus heartbeat version plus token version at a few hundred bytes per exchange, full state only for lagging keys. Gossiping whole configs or binaries per round turns the detector into the outage.

Growing from three seed contacts to three thousand members

A restarted node knows nobody except 2 to 3 seed addresses baked into config. It asks a seed who is alive, receives a peer sample plus versions, then gossips with that sample and becomes a full member within logarithmic rounds like any other rumor. Seeds are special only at minute zero; afterwards every node gossips identically, so losing all seeds later changes nothing.

Boot: new node N → seed S: "who is alive?" → S returns 20-peer sample + versions
  N gossips with sample → within ~log(n) rounds N is a full member
  scale math: n=3000, fanout 3, 1s interval → converge ~8–9 rounds ≈ under 10s
  steady chatter: 3000 nodes × 3 msgs/s × ~200B ≈ 1.8MB/s cluster-wide

Partition heals: both sides bump versions on contact, max-version merge reconciles.
  Writes taken on both sides still need CRDT rules or last-writer-wins, because
  CRDTs, meaning data types whose concurrent updates merge deterministically,
  are the layer that orders what gossip only spreads.

Tuning fanout where logarithmic speed meets linear bandwidth

Fanout 1 sips bandwidth and crawls, since one slow peer stalls the rumor. Fanout 5 screams through the fleet and quintuples chatter. Convergence rounds shrink logarithmically with fanout while traffic grows linearly, so fanout 2 to 3 buys nearly all the speed for a fraction of the cost. Shuffle peer lists each round, because fixed partners re-infect each other and stall near 80% coverage.

n=3000 nodes, digest 200B, interval 1s:
  f=1: rounds ≈ log(3000)/log(2) ≈ 12 → ~12s, traffic 3000×1×200B = 0.6MB/s
  f=3: rounds ≈ log(3000)/log(4) ≈ 6  → ~6s,  traffic 3000×3×200B = 1.8MB/s
  f=5: rounds ≈ log(3000)/log(6) ≈ 5  → ~5s,  traffic 3000×5×200B = 3.0MB/s
  f=3 halves convergence vs f=1 for 3x bytes; f=5 gains 1 round for 67% more bytes.
Shuffle peer lists each round; fixed partners re-infect each other and stall at ~80%.

Send digests over UDP, meaning loss-tolerant datagrams where the next round repairs drops, and repair payloads over TCP, meaning reliable streams for bytes that must arrive. Gossiping everything over TCP lets one slow peer head-of-line block the rumor that fanout was supposed to route around.

Burying paused nodes without mistaking slowness for death

A 4-second garbage-collection pause looks exactly like death to a 1-second probe: the node stops answering, suspicion spreads, it gets evicted, then returns and replays recovery for an hour. Binary alive-or-dead verdicts cannot separate slow from gone. Accrual detectors stop asking for a verdict and report a sliding suspicion level instead, where phi, meaning a score derived from overdue time relative to heartbeat history, grows the longer a heartbeat is late.

Rolling a kill-switch flag to three thousand machines without a push

A flag must reach 3,000 nodes in seconds without a control-plane push thundering one service. Versioned gossip carries it: each flag update bumps a version, nodes exchange (flag, version) digests on the normal tick, and laggards fetch the full value only where they trail. Rollback is just another higher version, with no unpush protocol. Targeting rides along: gossip the predicate with the version and nodes self-evaluate region before applying. Consul KV with Serf gossip, meaning a control plane writing once while gossip fans out and reads stay local, follows exactly this shape.

flag checkout_v2: v41 (off) → v42 (on, 10% rollout) → v43 (off, rollback)
  node at v41 meets node at v43 → adopts v43 directly (versions skip cleanly)
  rollout targeting ("only EU"): gossip the predicate WITH the version;
    nodes self-evaluate region before applying, no per-node addressing.

Remembering enough peers to keep the sample random

Gossiping to 3 random peers requires knowing some peers, but a 3,000-node fleet does not fit in a 20-entry view. Peer sampling keeps two small lists in the style of HyParView, meaning a protocol holding an active view plus a passive backup: an active view you gossip with and a passive backup of overheard addresses. Dead entries age out, live ones shuffle between nodes each round, and the view stays a fresh random sample, which is exactly what logarithmic spread assumes. Without shuffling, views ossify into cliques and rumors stall inside neighborhoods.

Healing a split brain where both sides kept writing

A partition splits the fleet 1500 versus 1500 for ten minutes and both sides accept writes, bump versions, and gossip internally. On healing, maximum-version merge reconciles membership in logarithmic rounds, but conflicting writes to the same keys cannot merge by version alone. Last-writer-wins keeps the higher stamp and silently discards the loser, which suits flags and heartbeats but destroys shopping carts. CRDTs, meaning data types whose concurrent updates merge deterministically such as add-wins sets, preserve both sides by rule, while vector clocks, meaning per-node counters detecting concurrency, keep siblings for application merge. Gossip spreads; only the reconciliation layer decides what survives contact.

Split: side A writes cart {+headphones} v5, side B writes cart {-case} v5 (concurrent)
  heal: max-version merge sees v5 == v5, neither dominates → conflict, not convergence
  LWW: keeps one, drops the other; fine for flags, data loss for carts
  CRDT add-wins set: union {headphones added} ∪ {case removed} = {headphones}, both kept
  vector clocks: keep both siblings [A:2,B:1] vs [A:1,B:2], reconcile at read or UI.
  rule: name the merge before the partition names it for you.

When to gossip, when to vote

Fanout 3 converges 3,000 nodes in about 6 seconds and max-version merge reconciles the split brain, yet every Cassandra read still walks 10 SSTables to prove a key is absent. What in-memory structure rejects those misses in microseconds without storing one key?