Why Gossip Protocols?

A cluster of N nodes needs to agree on:

• Who's alive (membership)
• Configuration values
• Ownership of keys (with consistent hashing)
• Recent events

Centralized approach: one master polls all nodes. SPOF + bottleneck for large clusters.

Gossip protocols (epidemic protocols): each node periodically picks a random peer and exchanges state. Information propagates EXPONENTIALLY:

• Round 1: 1 node knows
• Round 2: 2 nodes know
• Round 3: 4 nodes know
• Round 4: 8 nodes know
• ...
• Round log_2(N): all N nodes know

For 1000 nodes: ~10 rounds. With 1-second rounds: 10 seconds for cluster-wide propagation.

Properties:

• Decentralized: no leader, no SPOF.
• Probabilistic: messages may be lost; protocol still converges.
• Bounded bandwidth: each node sends to one peer per round.
• Self-healing: temporary partitions resolve when peers reconnect.

Used by:

• Cassandra (membership + topology)
• Consul, Serf, etcd member tracking
• DynamoDB (intra-region)
• Riak
• Bitcoin / Ethereum (block propagation)