Failure detection: heartbeats, timeouts, and gossip

A node that has crashed and a node that's simply overloaded and slow to respond look identical from the outside — both fail to answer within some expected window. Every failure-detection mechanism in distributed systems is, underneath, really just a timeout, and every timeout is a bet: too short, and a merely-slow (but alive) node gets incorrectly declared dead; too long, and a genuinely dead node's failure takes longer than necessary to notice and route around.

The simplest mechanism: each node periodically sends a small "I'm alive" message (a heartbeat) to others (or to a central coordinator). Missing some threshold number of expected heartbeats in a row triggers a "suspected failed" state.

This is exactly the mechanism underneath Raft's leader election from lesson 8: a follower's "election timeout" is really a heartbeat-miss threshold triggering a new leader election.

A fixed heartbeat timeout treats every network as equally reliable, which is rarely true in practice — a network with occasionally-slow but genuine heartbeats needs a longer timeout than a very tight, reliable local network, and a single fixed number can't serve both well. A phi accrual failure detector instead tracks the recent history of heartbeat arrival times and outputs a continuous suspicion level (φ) rather than a binary alive/dead — "this node is increasingly unlikely to still be alive, given how heartbeat timing has actually behaved recently," letting the application decide its own threshold for how confident it needs to be before acting.

For large clusters, having every node individually monitor every other node (or funnel everything through one central coordinator) doesn't scale. A gossip protocol instead has each node periodically exchange state with a few randomly chosen peers, who each do the same with a few more — the same way a rumor spreads through a large group without any single person telling everyone directly.

Information about a node's failure (or recovery) propagates through the whole cluster in roughly logarithmic time relative to cluster size, without any single node needing a complete membership list or acting as a bottleneck — this is precisely why gossip is the default choice for very large clusters (Cassandra's cluster membership, for instance) where a central coordinator or full mesh of heartbeats would itself become a scalability problem.

A failure detector that's too trigger-happy under real network jitter can cause flapping — repeatedly declaring a healthy node dead and alive again, triggering unnecessary leader re-elections or traffic rerouting that themselves add load and instability to an already-stressed system. Several well-documented real-world outages trace back to exactly this: a brief network hiccup misread as multiple node failures, triggering a cascade of "corrective" actions that made the actual problem meaningfully worse.