Failure Detection: Heartbeats, Phi-Accrual & SWIM

"Is that node dead?" You can never know for sure

A dead node and a node that is merely slow (GC pause, network blip, overloaded NIC) look identical from the outside: both go quiet. This is the impossibility at the heart of failure detection, and it forces a tradeoff you must be able to name.

That tradeoff is completeness vs accuracy. Completeness means you eventually detect every real crash. Accuracy means you never wrongly declare a live node dead. You cannot maximize both. Set your timeout aggressively (500ms) and you detect crashes fast but you flap: a routine 800ms GC pause evicts a healthy node, triggering a needless failover or re-replication storm. Set it conservatively (30s) and you never false-positive but you carry dead nodes for half a minute, sending traffic into a black hole.

The classic mechanism is a fixed-timeout heartbeat: node A pings B every second; three misses in a row and B is declared dead. Simple, but the fixed threshold is exactly the flapping problem: a threshold tuned for a quiet datacenter false-positives the moment latency rises under load, precisely when you least want spurious failovers.

Phi-accrual: adapt to the link

Phi-accrual failure detection (the Cassandra/Akka lineage) outputs a continuous suspicion level phi instead of a boolean. It records the recent inter-arrival times of heartbeats and fits a distribution. When a heartbeat is overdue, phi is the negative log of the probability that a heartbeat this late is still normal for this link. A link that normally jitters by 50ms yields a huge phi at a 2-second gap; a normally-bursty link yields a modest one. You act at a threshold (phi > 8 is roughly a 1-in-10^8 chance this is normal). The win: it adapts to each link's actual behavior with no hand-tuning.

SWIM: membership at scale

All-to-all heartbeats are O(n²): 500 nodes each pinging 499 others is ~250k messages per interval. SWIM makes per-node load O(1). Each period, a node directly probes one random peer. If that peer does not ack, the node asks k other random members to probe it indirectly (the target might be fine but the direct path congested; indirect probes distinguish a path problem from a dead node). Only if both fail does it act. Crucially, SWIM adds a suspicion sub-protocol: a non-responsive node is marked suspect, not dead, gossiped as suspect, and given a window to refute ("I'm alive") before being confirmed dead: sharply cutting false positives from transient blips. Membership changes piggyback on probe messages and spread infection-style, so the whole cluster learns in O(log n) rounds. This is what HashiCorp memberlist (Consul, Serf) implements.

Table

The highlighted column is the whole argument for gossip-based membership: all-to-all heartbeating does not fail at 500 nodes because the messages are expensive, but because the count grows with the square of the cluster.

Scheme	Messages per interval at n = 500	Growth per node	What happens as the cluster grows
All-to-all heartbeat	~250,000: every node pings all 499 others	O(n²)	The detector itself becomes the bottleneck
SWIM	1 direct probe, plus k indirect probes only on a miss	O(1)	Flat. Membership piggybacks on probe traffic and spreads in O(log n) rounds

And a node that misses a probe is not declared dead, it is declared suspect:

Order of evaluation

1. Aliveanswering direct probes
2. Suspectmissed a probe; gossiped as suspect, not as dead
3. Refute windowthe node can answer 'I am alive' and return straight to alive
4. Confirmed deadonly after the window closes, gossiped on ordinary probe traffic

Interview nuance: the tell of a weak answer is tuning a single timeout as if slow and dead were distinguishable. The strong framing: pick an adaptive detector (phi-accrual), add a suspicion window to buy accuracy, and use gossip-based membership (SWIM) so detection load stays flat as the cluster grows.

Recap: dead and slow are indistinguishable, so failure detection is a completeness-vs-accuracy tradeoff; use phi-accrual to adapt the threshold per link, a suspicion window to cut false positives, and SWIM's random direct/indirect probes plus infection-style gossip to keep per-node load O(1).