Dead or just slow?

Why can no machine ever tell a crashed neighbour apart from a slow one?

One machine asks another for something and hears nothing back. Two seconds pass, then ten. What has happened?

The candidate answers are easy to list. The other machine crashed. Or it is alive but overloaded and has not got to the request. Or it answered and the reply was lost. Or the network between them is partitioned. Or it is paused mid-computation for a garbage collection.

Now here is the uncomfortable part. Ask what the waiting machine could do to distinguish these. Send another request? Silence again is equally consistent with all of them. Ask a third party? It can only report its own silence. Wait longer? Every one of these states can produce silence for any length of time. So the question worth sitting with is not which technique is best, but whether the distinction is available at all.

Reason about what evidence exists. The only thing one machine ever learns about another is the messages that arrive. A message that arrives is positive evidence: the sender was alive at the moment it was sent. But the absence of a message is not evidence of anything, because absence has many possible causes and the observer cannot see which one applies — it sees the same nothing in every case.

That asymmetry is the whole thing. Liveness is observable; death is not. A machine can prove it is alive by speaking, but nothing can prove a machine is dead, because "has not spoken yet" and "will never speak again" look identical from outside for any finite period.

Could you close the gap with a timeout? Only by adding an assumption. A timeout says: if nothing arrives within T, treat the peer as dead. That converts an unanswerable question into a decision, which is genuinely useful — but notice what it does not do. It does not obtain the missing information. It guesses, and the guess can be wrong in both directions. Set T short and you declare healthy but busy peers dead. Set T long and you leave real failures undetected for that long. There is no T that eliminates both errors, because the underlying states are genuinely indistinguishable and T only chooses which mistake you prefer.

Why can no clever protocol escape this? Because it would need a bound on how long a message can take, and in an asynchronous network there is none. Without a bound on message delay or on relative processing speed, "slow" is not a bounded condition, so it cannot be separated from "stopped". This is the setting of the classic 1985 impossibility result of Fischer, Lynch and Paterson, which showed that in a purely asynchronous system no deterministic protocol can guarantee agreement if even one process may fail — and the reason is precisely this indistinguishability.

So what do real systems do? They stop trying to detect failure and start trying to manufacture it. If you cannot know whether a peer is dead, you can arrange that it becomes harmless. A lease says: you hold this role until time T unless you renew, and if you do not renew, you must stop acting. Now a peer that goes quiet is either dead or has stopped by its own rule, and those two are equivalent to everyone else. Fencing does the same at the resource: storage refuses writes carrying an old token, so a revived straggler cannot do damage even though nobody established it was gone.

The distinction matters. Detection tries to answer an unanswerable question; leases and fencing convert it into a question about time and tokens, which is answerable — at the cost of assuming clocks do not drift too far apart, a weaker assumption but not a free one.

There is a refinement, too. Because absence carries so little information, some systems stop treating it as binary: a detector can accumulate a suspicion level from the pattern of recent arrivals and let each caller pick its own threshold, the phi-accrual approach. That obtains no missing information either — it makes the guess adaptive, so a cheap action can trigger early while an expensive one waits.

Three clarifications.

First, this is a limit on information, not on engineering effort. No better heartbeat, no faster ping, no larger quorum of observers removes it, because every observer is subject to the same asymmetry. Systems that appear to solve it have added an assumption — bounded delay, synchronised clocks, a hardware fence — and it is worth being able to name which one, since that assumption is what will fail during an incident.

Second, the failure mode people underestimate is the false positive. Declaring a live node dead is not a harmless over-caution: if the node is alive and still holds a lock, still writes to storage, still believes it is the leader, you now have two leaders. Most split-brain incidents begin not with a crash but with a healthy node that was slow at the wrong moment — which is exactly why fencing tokens exist, since they make the stale leader's writes fail even though it never learned it had been replaced.

Third, timeouts are still right. The reasoning does not say they are useless; it says they are a policy choice being made whether or not anyone notices. Choosing T is deciding your tolerance for premature declarations against your tolerance for undetected failure, and treating it as a tuning constant rather than a decision is how it ends up set to whatever the library's default was.

• Fencing tokens and how a storage layer enforces them.
• The phi-accrual failure detector, and what a continuous suspicion level buys over a boolean.
• Partial synchrony, the assumption under which consensus becomes possible again.

Every term the collection defines is gathered in the glossary.