Epidemic spread
Gossip protocols spread information the way a rumor spreads. Each round, every node that knows an update picks a few random peers and forwards it. The number of informed nodes grows roughly exponentially, so a cluster of n nodes converges in about log n rounds.
Push, pull, and push pull
- Push sends updates to random peers; fast early but slow to reach the last few stragglers.
- Pull asks random peers what is new; fast at the tail once most nodes are informed.
- Push pull combines both and converges fastest.
Why teams love it
- Robustness: no single node is critical, and message loss only delays, never breaks, convergence.
- Scalability: each node sends a constant amount of traffic per round regardless of size.
- The cost is redundant messages and eventual, not instant, consistency.
Key idea
Gossip trades a few redundant messages for robust, scalable, log n round dissemination that tolerates loss and failures gracefully.