Archivedistributed-systems
Gossip Protocols Scale by Being Sloppy
Random fanout spreads state in O(log n) rounds and never needs a membership oracle.
- Published
- Reading time
- 1 min read
Gossip (epidemic) protocols spread updates by periodically sending state to a random subset of peers. With fanout f and n nodes, information reaches everyone in O(log n) rounds with high probability.
Variants
- Anti-entropy: exchange merkle-tree digests or version vectors and repair differences. Reliable, bandwidth-heavy.
- Rumor mongering: push new updates; stop after a while. Fast, probabilistic.
- SWIM: combines gossip with direct probes for failure detection, which is how many clusters track membership.
Why it works
No central coordinator, no full membership view needed for correctness, and resilience to loss: a dropped message is retried by another round. Overhead per node stays roughly constant as the cluster grows.
The costs
- Convergence is eventual — expect seconds of staleness.
- Bandwidth grows with state size, not just membership.
- Debugging is hard: the system has no single source of truth.
Takeaway: gossip is the right default for membership, failure detection, and metadata propagation. It is the wrong tool for anything requiring immediate global agreement.