Gossip Protocols

How clusters spread state without a coordinator: every node regularly swaps what it knows with a random peer, so news reaches all n nodes in about log n rounds.

Overview

A gossip protocol spreads information the way a rumor spreads through a school. Every node, on a timer, picks another node at random and the two swap what they know. A node that learns something new passes it on in its next rounds. No node is in charge, and no node needs to know the whole cluster's layout to take part.

The idea comes from a 1987 paper by Alan Demers and colleagues at Xerox PARC, who used it to keep hundreds of replicated name servers in sync. They called these epidemic algorithms, because the math of how an update spreads is the math of how a disease spreads. Today gossip carries cluster membership and metadata in Cassandra, in HashiCorp's memberlist library (and so Consul and Serf), and in CockroachDB's node discovery.

Gossip is popular because it is simple and robust. Each node does a small, fixed amount of work per round, lost messages are repaired by later rounds, and news still reaches every node in a number of rounds that grows only with the logarithm of the cluster size. The price is that it is only eventually consistent: for a short time, nodes disagree.

What you will be able to do

  • Explain anti-entropy and rumor mongering, and why real systems run both.
  • Estimate how many rounds gossip needs for a cluster of a given size, and why push-pull beats push.
  • Describe what a gossip message carries (digests, versions, generations) and how nodes merge state.
  • Handle deletes, restarts and partitions in a gossiped state.
  • Say when gossip is the wrong tool and consensus is needed instead.

Key concepts

  • Epidemic spreading
  • Anti-entropy
  • Rumor mongering
  • Push, pull and push-pull
  • Rounds grow with log n
  • Digests and versions
  • Seed nodes
  • Death certificates
  • Gossip plus consensus

Interview questions

  • How does a gossip protocol work, and why does it scale?
  • What is the difference between anti-entropy and rumor mongering?
  • Compare push, pull and push-pull gossip.
  • Walk through how Cassandra uses gossip.
  • How do you delete something from a gossiped state?
  • When should you not use gossip?
  • What happens to gossip during a network partition?

Sign up free to read the full topic

More System Design topics

Start free on Cariara · Coding problems · System design studio