Gossip protocol: an interactive epidemic broadcast simulator
A gossip protocol spreads information through a cluster the way a rumour spreads: in every round, each node that knows something tells a few peers chosen at random. Because the number of nodes that know roughly multiplies every round, an update reaches all N nodes in about log N rounds, with no coordinator, and it keeps spreading when messages are lost or nodes are down.
In the playground, one node learns an update and the rest of the cluster finds out round by round. Change the cluster size, how many peers each node tells, how many messages are lost and how many nodes are down.
256 nodes; each node that knows the update tells 3 random peers a round. Every live node knew it after 7 rounds, 90% after 5, using 2,226 messages. The number who know grows about 4 times a round at first, so the rounds needed grow only with the logarithm of the cluster size, and slow at the end, when most peers picked already know.
How gossip works
- Every round, often once a second, each node picks a few peers at random.
- Push: a node that knows the update sends it to them.
- Pull: a node asks them what they know and takes anything newer.
- Push-pull: both at once, usually by exchanging a digest of versions and then only the entries that differ.
- Stop: a node stops spreading an update after a few rounds, or once most peers it contacts already have it.
Why it takes about log N rounds
With a fanout of 3, each node that knows tells 3 more, so the number who know grows about fourfold a round: 1, 4, 16, 57, 162. In the playground 256 nodes all know after 7 rounds, and 1,024 nodes, four times as many, need only 8. The end is the slow part: once most nodes know, most random peers picked already know too, and the last few stragglers are found by luck. That is why push-pull helps: a node that has not heard asks, and is almost certain to ask someone who knows. With a fanout of 1, push-pull finishes in 8 rounds instead of 13.
Why gossip is robust
Every node hears the update from several others, so losing some messages only slows it down: with 30% of messages lost, all 256 nodes still learn it, in 10 rounds instead of 7. Crashed nodes need no special handling; messages to them are wasted, and everyone else is reached through other paths. No node is special, so there is nothing to fail over. The price is redundancy, the same update sent to nodes that already have it, and time: with one round a second, a large cluster takes several seconds to agree.
What gossip is used for
- Membership and failure detection: which nodes exist and which seem dead. SWIM-style protocols, used by HashiCorp’s memberlist in Consul and Serf, combine random probing with gossip to spread who has joined, left or failed.
- Cluster state in databases: Cassandra nodes gossip every second with up to three others about the state of the ring; Redis Cluster nodes gossip over their cluster bus.
- Anti-entropy: replicas periodically compare data with a random peer, often using Merkle trees, so missed writes eventually spread.
- Peer-to-peer networks: blockchains relay new transactions and blocks from peer to peer in the same way.
Gossip gives eventual agreement, not a decision at a point in time. When nodes must agree on one value, such as who the leader is, use consensus instead.
A gossip loop in code
import random, time
def gossip_loop(me, peers, fanout=3, interval=1.0):
while True:
for peer in random.sample(peers, fanout):
try:
# send a digest of what I know; the peer replies with anything newer it has
theirs = peer.exchange(me.state.digest())
me.state.merge(theirs) # newest version of each entry wins
except TimeoutError:
me.suspect(peer) # failure detection rides on the same messages
time.sleep(interval)In a system design interview
Gossip answers “how do nodes find out about each other?” without a central registry: “Each storage node gossips with three random peers every second, exchanging membership and the token ring. A change reaches all 1,000 nodes in about ten rounds, so about ten seconds; nodes that stop answering are marked suspect, then dead.” Expect the follow-ups: how long convergence takes, false failure detection during a network blip, and why you would still use consensus for anything that needs a single answer.
Read the guide to gossip and failure detection, see consistent hashing for the ring that gossip keeps in sync, or watch a strong candidate design a distributed key-value store.
Questions people ask
What is a gossip protocol?
A way of spreading information in a cluster without a coordinator: every round, each node exchanges what it knows with a few randomly chosen peers. Like a rumour, an update spreads exponentially and reaches every node in a number of rounds that grows with the logarithm of the cluster size.
How long does gossip take to reach every node?
About log N rounds, where N is the number of nodes, with a small constant that depends on the fanout. With each node telling three peers a round, 256 nodes are all reached in around 7 rounds and 1,024 in around 8. With one round a second, a cluster of a few thousand nodes converges in roughly ten seconds.
What is the difference between push, pull and push-pull gossip?
In push gossip, nodes that know an update send it to random peers. In pull gossip, every node asks random peers for anything newer. Push spreads fast at first but is slow to reach the last few nodes; pull is the reverse; push-pull does both, usually by exchanging version digests, and converges fastest.
Why is gossip fault tolerant?
Each node hears an update from several others, so lost messages and crashed nodes only slow the spread down rather than stopping it, and no node plays a special role whose failure matters. The cost is redundant messages to nodes that already know, and agreement that is eventual rather than immediate.
What is gossip used for in distributed databases?
Cluster membership, failure detection and sharing metadata such as the token ring and schema versions. Cassandra nodes gossip every second with up to three peers; Redis Cluster nodes gossip over a cluster bus; Consul and Serf use the SWIM-based memberlist library. Anti-entropy repair between replicas works in a similar random, periodic way.
What is the SWIM protocol?
Scalable Weakly-consistent Infection-style Membership, a protocol for membership and failure detection. Each node periodically pings a random member, asks others to ping it indirectly if it does not answer, marks it suspect and then dead, and spreads these membership changes by piggybacking them on its gossip messages, so load per node stays constant as the cluster grows.
When should you not use gossip?
When nodes must agree on a single value at a single moment, such as electing one leader or committing a transaction in order. Gossip gives eventual convergence with no guarantee of when; those problems need a consensus protocol such as Raft or Paxos. Gossip is for state that can be briefly inconsistent across nodes.