Distributed Systems Core · lesson 5 of 11 · about 28 min
How to spread information through thousands of machines with no coordinator: the exponential rumour, push versus pull versus push-pull, SWIM's random probing for failures, gossip that computes an average, why per-node cost stays flat as the cluster grows, and the 2008 lesson of a corrupted record that gossip spread perfectly. Tap any for a plain-language card.
A rumour
Each node does a small, constant amount of work per round, however big the cluster gets, and no node is special: lose any of them and the rumour still spreads. The price is that delivery is probabilistic and a little redundant: some messages tell a node what it already knows. The simulation spreads one rumour from node 0 with real random choices.
Go from 1,000 to 100,000 nodes: a hundred times the cluster costs only a handful more rounds.
In a cluster of 1K, a rumour told to 1 peer per round reaches 99% in 15 rounds and everyone in 19 (log₂ N is 10), using 19K messages in all. Each node sent only 1 message per round, whatever the size of the cluster.
Real simulation with random peer choice, push gossip from one starting node, seeded. Loss drops a message with the chosen probability.
Push, pull, push-pull
Each curve is a real simulation with one message per node per round. Look at the rounds needed for the last node: it is where the three differ. Real systems (Cassandra, Dynamo-style stores, Serf) exchange state in both directions for exactly this reason.
Set 1,000 nodes and compare the rounds to reach everyone for push versus push-pull.
With 1,000 nodes, push needs 19 rounds to reach everyone, pull 14, and push-pull 10. The difference is the last few nodes: push keeps pushing at nodes that already know, while pull lets an uninformed node ask until it finds someone who knows.
One contact per node per round, seeded. Push-pull sends the rumour both ways in each contact.
Gossip for failure detection
The indirect probes are the clever part. If a single direct ping is lost (the network is lossy, not the peer dead), the extra paths through other nodes almost always succeed, so the chance of wrongly accusing a healthy node drops from a few percent to a fraction of a percent. News of a failure, once found, is then spread by piggybacking on the same messages (gossip). Try the loss and the number of helper paths.
With 10% packet loss, going from 0 helper paths to 3 cuts false accusations by about 25 times.
In a cluster of 100, a dead node is probed by someone in a period with probability 63.4% (about 1.6 periods to find it, independent of size). At 10% loss, one probe wrongly accuses a healthy node 19.00% of the time with a direct ping alone and 0.773% with 3 indirect paths: about 2,782 false accusations an hour across the cluster instead of 68,400, at one probe per node per second.
Exact: P(probed) = 1 − (1 − 1/(N−1))^(N−1); a direct probe fails with prob 1 − (1 − loss)²; an indirect path has four legs. Probe rate 1 per node per second.
Gossip that computes
Here one node starts with a big value (n × 100) and all others with zero, the worst case. The curve shows how far apart the highest and lowest node are, as a fraction of the mean, on a log scale. About 20 rounds are enough for any cluster size in the range below, which is the “logarithmic in N” promise again.
Look at round 10 and round 20: the gap falls from a few percent to a few thousandths of a percent.
After 10 rounds in a cluster of 200, the highest and lowest node differ by 7.7e+0% of the true mean (100.0). Still far apart: keep gossiping. No node knew the others' values, and no coordinator collected them.
Real simulation: node 0 starts with n × 100, the rest with 0; each round every node averages with one random peer.
Scaling
The costs of gossip are not in scale but elsewhere: convergence time is seconds, not milliseconds (it is the wrong tool for anything needing instant, consistent agreement; that is consensus), delivery is probabilistic, and bad information spreads as well as good (the last scene).
Compare 10,000 nodes with 1,000,000: per-node bandwidth is identical, the time grows by two periods, and all-to-all becomes impossible.
With 10K nodes each gossiping with 3 peers every 1 s, a node sends and receives about 9 KB/s (the same at any size), news reaches everyone in about 10 periods (10 s), and the whole cluster moves 90 MB/s. All-to-all would be 150 GB/s.
Rounds ≈ ln N ÷ ln(1 + fan-out) + 3 for the tail. The traffic figures count both directions of each exchange.
Gossip, consensus or coordinator?
Gossip is cheap and approximate; consensus is exact and costly; a coordinator is simple but a single point. Match the tool to the job. Each answer is worth 20 XP.
Ask: must everyone agree exactly and now? and how many nodes are there?
Telling 10,000 nodes which of them are alive.
Tip: press 1 to 3 to answer, Enter for the next one.
Who lives by this
Four published systems and papers on gossip.
epidemic algorithms for replicated databases
The 1987 paper "Epidemic Algorithms for Replicated Database Maintenance" borrowed the mathematics of disease spread to keep copies of a database consistent: rumour mongering and anti-entropy, with push, pull and push-pull exchanges. It is the origin of gossip protocols.
each node gossips with up to 3 nodes once a second
Cassandra's documentation describes a gossip process that runs every second and exchanges state about itself and other nodes with up to three other nodes, so every node learns quickly which nodes exist, their status and their tokens, without a central membership service.
SWIM + Lifeguard
HashiCorp's memberlist library implements the SWIM protocol with extensions (Lifeguard) and powers membership in Serf and Consul. Its documentation describes random probing, indirect probes and piggybacked gossip of membership changes, with tuneable probe intervals and timeouts.
gossip state corrupted by one bit flip
Amazon published a postmortem of a multi-hour S3 outage in July 2008 whose root cause was a single corrupted message in the gossip protocol that servers use to share state: servers acted on it and spread it, and the system spent hours stopping the gossip and restoring state. Afterwards AWS added checks and tooling around gossip state.
Interview angle
Six questions, each worth 20 XP. Gossip is a favourite in designs for membership, failure detection and large key-value stores.
Say how many peers per round, how long to converge (log N), and what happens when bad data spreads.
About how many rounds does it take a gossip rumour to reach all N nodes?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
Defences: checksums on messages and records so corrupted ones are discarded (as in , a later lesson), validation of what a state change may be, limits on how fast state may change, and the ability to stop gossip or roll back the state cluster-wide. Here one corrupted record with the highest version appears on one node. Set the chance that a receiving node's validation catches it.
With no validation it takes only a few rounds to reach nearly all nodes. Then set a 50% and a 95% catch rate.
With 0% validation, 100% of 500 nodes end up holding the corrupted record, 99% of them within 5 rounds. Every node did its job correctly: it accepted a newer version and passed it on.
Seeded simulation of push-pull gossip with one corrupted record of the highest version. The July 2008 S3 incident is Amazon's own account.