Notesdistributed🌱 seedling

Gossip Protocol

Also: Gossip · Epidemic Protocol · SWIM · Lifeguard · Infection-Style Dissemination

Each node periodically shares what it knows with a few random peers, who pass it on, so information reaches all n nodes in O(log n) rounds at constant load per node. SWIM uses it to spread membership and failure news.

Why it exists

All-to-all heartbeating costs O(n²) messages and collapses at thousands of nodes. A central membership server is a bottleneck and a single point of failure.

How it works

  • Dissemination: every period, pick k random peers and exchange state (or piggyback updates on messages already being sent). Rumours spread like an epidemic.
  • SWIM failure detection: each period a member pings one random member. No ack → ask k others to ping-req it indirectly, so one bad path doesn't look like a death. Still nothing → mark it suspect, not dead.
  • Suspicion: the suspect hears the rumour and refutes it with a higher incarnation number; otherwise it's declared dead after a timeout.
  • Lifeguard: a node whose own probes keep failing assumes it is the slow one (CPU starvation, slow event loop) and backs off its accusations.
  • Expected detection time and per-node load don't grow with cluster size.

Trade-offs

Gains Costs
scales to thousands of nodes, no coordinator membership is eventually consistent: nodes briefly disagree
tolerant of message loss detection is probabilistic and seconds-scale
cheap: updates ride on existing pings debugging "who knew what when" is hard

In practice

  • HashiCorp memberlist (Consul, Nomad, Serf) implements SWIM with Lifeguard; the Lifeguard paper reports false positives cut more than 50×, and new memberlist defaults gave 20× fewer with 20% faster detection.
  • Cassandra gossips cluster state every second with a few peers and judges liveness with a phi accrual detector.

Pitfalls

  • Gossip doesn't give agreement. Never use gossiped membership to decide who may write; use Consensus for that.
  • A slow node can falsely accuse healthy peers unless it accounts for its own health.

Recall

These cards are also in your review deck, scheduled with spaced repetition.