Skip to main content
distributed systems

Gossip protocols

9 min read
Fully authored

How Cassandra and Serf propagate cluster state at O(log N) — like disease spread.

Gossip protocols propagate information through a cluster like disease spreads through a population. Each node periodically shares state with a small random subset of peers. In O(log N) rounds, everyone knows. It's how Cassandra tracks membership, how Serf handles service discovery, how Hedvig replicates writes.

Interactive spread

Cluster size
1K nodes
Time to full spread
~10 rounds (5.0s)

The gossip algorithm

every 500ms: {
peer = random_peer()
state = merge(local_state, peer.get_state())
peer.push_state(state)
}
  • Push-pull: both sides learn from each other in one round
  • Fanout: pick 2-3 peers per round for faster spread + more resilience
  • Anti-entropy: periodically sync full state to prevent drift

The math — why O(log N)

Each round, the number of nodes that know DOUBLES (each knower tells 1 unknown). Starting from 1 knower: 1 → 2 → 4 → 8 → 16 → ... → N. That's log₂(N) rounds. 1000 nodes = 10 rounds = 5 seconds at 500ms/round. 1M nodes = 20 rounds = 10 seconds. Cassandra tuned to be even faster.

Real deployments

Cassandra — gossip for cluster membership, failure detection, schema propagation
Consul + Serf (HashiCorp) — gossip for service discovery + health checks
Redis Cluster — gossip on port 16379 for cluster topology + failover
Kubernetes — etcd is centralized, but Cilium, Weave use gossip for CNI state

Practice what you just read

Every foundation concept has a companion quiz to close the loop.

Take the URL Shortener quizOpen the flagship problem

More in distributed systems

Consensus — Paxos and RaftConsistent hashingDistributed transactions — 2PC, 3PC, Saga, TCCVector clocks and hybrid logical clocksCRDTs — conflict-free replicated data types