Gossip and failure detection

News spreads like a rumour, and silent nodes are noticed.

On the roadmap:Advanced · step 4: Distributed systems

Intermediateabout 10 to 15 min7 experiments

Experiments

New here? A few short steps show what happens, one at a time.

Settings

What to look at

Nodes in the cluster1,000

Nodes told each round (fan-out)2

Messages lost0%

Rounds until 99% know

Know after 5 rounds

22%

Messages per node per round

1.7

Total messages

67,268

99% of 1,000 nodes knew after 9 rounds, with 1.7 messages per node per round. Growing the cluster ten times adds only a few rounds.

Share of the cluster that knows, round by round

share that knows

Nodes that know (%)

An S-shaped curve: slow while few know, fast in the middle, and a short tail while the last few are found.

Rounds until 99% know, as the cluster grows

rounds

Rounds

Ten times more nodes costs only a few more rounds: the time grows like the logarithm of the cluster size.

In plain words

In gossip, every node regularly tells a few random others what it knows, and they pass it on. Like a rumour, news reaches the whole cluster in a handful of rounds with no central server. Nodes also gossip heartbeats, so a node that goes quiet is noticed by everyone.

Why it matters

Large clusters need to know who is alive and what changed, without one machine that everyone depends on. Gossip is simple, tolerates lost messages, and spreads in time that grows only with the logarithm of the cluster size. The catch is a trade-off in failure detection: how long to wait before calling a node dead.

How real systems do it

The simulation is a simplified model. Here is what production systems add or do.

Apache Cassandra uses gossip so that every node learns which others are in the cluster and what state they are in. It decides whether a node is down with a phi accrual failure detector, which adapts to the delays it sees instead of a fixed timeout.
HashiCorp's Serf and Consul gossip using a protocol based on SWIM, which checks nodes directly and asks other nodes to check on its behalf before declaring one dead, to cut false alarms.
Amazon's Dynamo paper describes using a gossip protocol so that nodes learn about membership changes and failures without a central coordinator.
Gossip spreads information in a number of rounds proportional to the logarithm of the number of nodes. The price is that news arrives eventually, not at once, and different nodes briefly disagree.