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.
Connections
- Part of
- Distributed Systems
- Mentioned
- Consensus
Recall
These cards are also in your review deck, scheduled with spaced repetition.