Failure Detection and Gossip

Define the problem

A machine that stops answering may be dead. It may also be slow, busy, or cut off by the network.

From the outside, these cases look identical. Silence is the only signal, and silence has many causes.

So a failure detector reports suspicion, not certainty. The rest of the system decides what to do with a suspicion.

Heartbeats and timeouts

Each machine sends a heartbeat at a steady rhythm. In this design, one heartbeat leaves every second.

A watcher records the time of the last heartbeat from each machine. A growing gap means a growing reason to worry.

A fixed timeout draws one hard line. Silence longer than the line marks the machine as failed.

The line is a trade-off in disguise. A short line reacts fast and cries wolf, while a long line stays calm and reacts late.

Gossip spreads the news

Checking every machine from one place does not scale. The watcher itself becomes a bottleneck and a single point of failure.

A gossip protocol shares the watching instead. Each machine watches a few others and passes on what it learns.

News travels in rounds. In each round, every machine that knows a fact tells one machine that does not.

Doubling seven times turns 1 knowing machine into 128 knowing machines.

Doubling ten times reaches 1,024 machines. Big groups hear the news within a few rounds.

Gossip is slow per round and cheap per machine. It suits large groups, where news within a few rounds is fast enough.

Phi accrual refines suspicion

Phi accrual is a failure detector style that turns silence into a rising score. The score is called phi, and it grows the longer the silence lasts.

Phi builds from the usual gap between one machine's heartbeats. A normal silence keeps phi low, while an unusual silence pushes phi high.

Each service sets a threshold for phi. Crossing the threshold marks the machine as suspected, not proven dead.

One threshold can serve machines with different rhythms. Each machine gets judged against its own past behaviour.

Phi accrual costs more to build and explain. It repays that cost where false alarms are expensive.

Trade-offs and wrap-up

A wrong suspicion can start an unneeded election. A missed failure can leave a dead leader in place.

No detector removes this risk. It only chooses which mistake to make more often.

A failure detector reports suspicion, never certainty, and the design must stay safe under both mistakes.

Two ways to judge a silence