Completeness and Accuracy: The Two Properties Every Failure Detector Trades Against

A process stops answering. The socket accepts no data, no acknowledgement arrives, and the local clock keeps advancing. Nothing in that observation distinguishes three quite different situations: the machine lost power, the machine is running but its network path is gone, or the machine is running fine and merely busy. The first is a crash, the second is a partition, the third is a slow response that will resolve itself. A failure detector exists to answer the question anyway, and the interesting part of its design is that it cannot answer it correctly, only usefully.

Two questions a detector answers

The literature separates the output of a detector from its correctness. A detector is a set of processes, each holding a list of the processes it currently suspects. Two properties constrain that list, and they constrain it in opposite directions.

Completeness is about failures: eventually, every process that has actually crashed is permanently suspected by every correct process. The weak form requires only that some correct process eventually suspects each crashed one; the strong form requires all of them to. Completeness is easy to satisfy, because a crashed process never sends anything again. Any detector that suspects on silence gets strong completeness for free as long as its timeouts are finite and the network eventually delivers nothing from the dead.

Accuracy is about the living: it constrains when a correct process may appear in anyone’s suspicion list. The strong form says no correct process is ever suspected, at any time, by anyone. The weak form allows mistakes but demands that some correct process never suspects another. The eventual forms drop the timing requirement to “after some unknown point in time” and are written with a diamond prefix. A detector that is strongly complete and strongly accurate is perfect, written P; the version that is strongly complete and only eventually strongly accurate is written ◇P, and it is the strongest class a real network can support.

The naming is worth internalizing because it encodes the trade. Completeness is a liveness property: it says something good eventually happens. Accuracy is a safety property: it says something bad never happens, or stops happening. Any detector that answers within a bounded time is at risk on the safety side, because a bounded wait is a guess about a network that does not promise bounds. Any detector that never guesses is at risk on the liveness side, because it may wait forever for a message that will not come.

Why no detector can have both properties strongly

The impossibility is not a limitation of cleverness. It follows from the same indistinguishability argument that makes consensus impossible in a fully asynchronous system with one crash failure.

Consider two runs of the system that are identical from the perspective of an outside observer until some time t, except that in one run process p has crashed and in the other p is alive but every message it sends is delayed past t. A detector running on q sees exactly the same sequence of events in both runs up to t. If it suspects p by t, it is wrong in the second run, violating strong accuracy. If it does not suspect p by t, then for the first run to satisfy strong completeness it must suspect p at some later time, and the same argument applies at that later time. Either the detector never suspects, or it suspects a live process. The only escape is to make the delay unbounded, which is exactly what “eventually” means.

The Fischer–Lynch–Paterson result pushes this further: in a fully asynchronous system where message delay is unbounded and processes can only fail by crashing, no deterministic protocol solves consensus even with one faulty process. A detector that is perfect and always available would hand consensus a solution, so it cannot exist. The two results are the same theorem seen from two angles, and the detector formulation is usually the more useful one because it turns an impossibility into an engineering parameter.

Partial synchrony as the escape hatch

Real systems are not fully asynchronous. They are mostly synchronous with occasional excursions: queues fill, a garbage collector runs, a link flaps, a virtual machine is descheduled by a noisy neighbour. Dwork, Lynch, and Stockmeyer formalized this as partial synchrony, in two variants that both matter for detectors.

In the first variant, the system has a known bound on message delay and a known bound on relative process speed, but those bounds hold only after some unknown global stabilization time. In the second, the bounds are always respected but their values are unknown to the protocol. A detector built for either model can be both strongly accurate and strongly complete after the stabilization point, and the cost is that before that point it may suspect anyone. This is precisely ◇P, and it is the strongest detector class that a real network can support.

The engineering consequence is that a detector’s configuration is a statement about how long an excursion is expected to last, not a statement about how long a message takes. A timeout tuned to the median round trip will suspect every process that hits the tail. A timeout tuned to the maximum ever observed will take a long time to notice a genuine crash. The interesting middle ground is a timeout that adapts to the observed distribution, which is the subject of accrual detectors built from arrival statistics, and the simpler fixed version is covered in heartbeat interval and timeout arithmetic.

What each class of detector is worth

The detector classes are not decoration. They determine which consensus protocols can be built on top of them, and the strength of the detector is paid for in the quality of the timing assumptions the deployment can honestly make.

A perfect detector P solves consensus in a system that is otherwise fully asynchronous: the protocol can wait for a process it never suspects and rely on it eventually answering. An eventually perfect detector ◇P also solves consensus, but the protocol must be written so that a wrong suspicion does not cause it to make an unrecoverable decision. This is the standard structure of a leader-based protocol: a leader that is wrongly suspected is replaced, and the replacement must be able to take over without losing the decisions the old leader already made. Below those, ◇S, which combines eventual weak accuracy with strong completeness, is enough to solve consensus. ◇W, eventual weak accuracy with only weak completeness, is the weakest class for which consensus is solvable, and only when a majority of processes are correct. Chandra and Toueg proved that necessity in the other direction too: any detector strong enough to solve consensus can be used to implement ◇W.

The hierarchy runs from strongest to weakest as P, ◇P, S, ◇S, ◇W. Each step down widens the set of networks the protocol tolerates and narrows the set of protocols it supports. The reason to care is that a system claiming to be crash-tolerant is really claiming a detector class plus a failure model, and the two are usually left implicit until an incident exposes them.

The two ways to be wrong, and what each costs

Every misclassification has a price, and the prices are not symmetric.

A false suspicion, where a live process is declared dead, costs availability and can cost correctness. In a primary-backup system it triggers a failover; the old primary may still be serving clients, so the system now has two writers. In a membership protocol it removes a healthy node, which shrinks the quorum and may push the cluster below the threshold it needs to make progress. Recovering from a false suspicion usually requires the suspected process to prove it is alive, and that proof has to be distinguishable from a delayed message from a process that has since restarted. The incarnation number in SWIM exists for exactly this reason, as described in suspicion and incarnation refutation.

A missed failure, where a dead process is not suspected, costs latency and can cost liveness. Requests routed to the dead node hang until the timeout that should have fired fires; a quorum waits for a vote that will never arrive; a lock held by the dead process is not released. The cost is bounded in time but unbounded in user impact, because the system appears to be working while making no progress.

The asymmetry explains why most real detectors err toward suspicion. A false suspicion is recoverable and detectable; a missed failure is silent. It also explains why the recovery path deserves more design attention than the detection path: the detector’s job is to be wrong quickly and to let the system undo the error cheaply.

Detection is a distributed decision, not a local one

A detector running on one process observes one path to one peer. That path is not the same as the peer’s health, and the difference is not academic: a switch dropping packets between two racks makes every process in one rack suspect every process in the other, while each side’s internal traffic is fine. The suspicion set is therefore a local opinion, and turning it into a system-wide membership view requires dissemination and agreement, which is where gossip propagation of suspicion and per-observer partition diagnosis enter.

The formal properties above are stated per observer and eventually, which hides the whole difficulty: two observers can hold contradictory and individually reasonable opinions for an arbitrarily long time, and no local rule resolves that without a shared clock or a quorum. A detector that reports “suspect” is telling the truth about its own view. A system that treats that report as a fact about the world is making an assumption the detector never promised.