Failure detection: liveness is a relation, not an attribute

Why does a failure detector trade completeness against accuracy, and why is its verdict about a link?

A failure detector emits suspicion when no message arrives within T. Two properties are in tension:

• Completeness: every dead node is eventually suspected.
• Accuracy: no live node is suspected.

In an asynchronous network you can have completeness always, and accuracy only eventually. The timeout is the dial between them.

The arithmetic is unforgiving. Detection latency ≥ T + one-way delay. The false-suspicion rate = P(response time > T), which is the tail of a distribution that is fat, not Gaussian: a GC pause, a page-cache miss storm, a rebalance on the same machine. So every fixed T is either slow or wrong, and there is no value that is neither. This is why this article has more timeouts than any other and trusts none of them for safety.

Phi-accrual and its interface. Phi-accrual's real contribution is not accuracy but interface. It emits a continuous suspicion level rather than a boolean, so the caller sets its own threshold. The caller knows whether a false positive costs a spurious election or a spurious re-replication of ten terabytes. The decision migrates to the party holding the cost information.

A correction is worth making. Phi is computed by fitting a distribution (classically a normal distribution) to the inter-arrival times of heartbeats. Fitting a light-tailed model to heavy-tailed data makes a late heartbeat look far more improbable than it is. So phi overshoots under exactly the load that produces legitimate lateness. The mechanism is sound; the default distribution is optimistic.

The structural point: all-to-all heartbeats do not scale. All-to-all heartbeating costs O(N²) messages and O(N) detection work per node. It is a fixed rate meeting growth. SWIM (a membership protocol) answers with randomized probing at O(1) per node per period plus indirect probes: when A cannot reach B, A asks k random peers to try. That separates "I cannot reach B" from "nobody can reach B", and this is the distinction that matters, because a detector's output is a property of the (observer, target) pair, not of the target.

Asymmetric links, gray failure (a node that is partly broken), a node that answers its health check and nothing else: in all of them the node is simultaneously alive and dead depending on who is asking. Indirect probing is a cheap approximation of consensus about liveness, and the cheapness is the point. Full agreement on liveness is exactly the expensive thing the rest of this article buys.

Detection needs a stopwatch, not a calendar. It uses durations from a monotonic clock, never differences of wall-clock readings. That is why clocks can wait: only two mechanisms in this article need anything more than a stopwatch.

Compression: a failure detector trades completeness against accuracy with a timeout, and its verdict describes a link, not a node.