Consensus can fail even when nobody lies
In a fully asynchronous distributed system, no deterministic protocol can guarantee that correct processes will reach binary consensus if even one process may crash. Messages can be delayed indefinitely, making a slow process indistinguishable from a failed one. The result permits non-termination; it does not say consensus never occurs.
The Fischer–Lynch–Paterson proof considers reliable communication with arbitrary delay and processes that take steps at unpredictable times. Starting from a state where either decision remains possible, an adversarial schedule can always postpone the decisive event while delivering messages legally. One crash is enough because the protocol cannot wait forever for a process that might be dead, yet acting without it can create a conflicting execution. Practical systems escape by adding timing assumptions, randomness, failure detectors, quorums or probabilistic termination guarantees.
The hard part of coordination is sometimes uncertainty about time, not dishonesty or broken messages. A timeout is therefore an assumption disguised as a clock reading: it says how long ‘slow’ may look before being treated as ‘failed’. Resilient system design begins by stating that assumption rather than promising unconditional consensus.
A process that has not replied may have crashed, or its message may simply be late. In an asynchronous model there is no upper bound that lets an observer decide. Waiting preserves safety but may destroy liveness; proceeding preserves progress but risks incompatible decisions in another possible execution. The theorem makes this indistinguishability, rather than hardware unreliability, the source of the dilemma. That is the point at which a descriptive pattern becomes a research programme with observations capable of proving it wrong.
Consensus protocols commonly assume partial synchrony: after some unknown point, communication behaves within bounds. Randomised protocols can terminate with probability one. Failure detectors make guesses that eventually become accurate enough, and quorum rules ensure intersecting evidence. These are not loopholes; they are explicit engineering contracts with the environment. Trouble starts when a system presents such a contract as an unconditional guarantee.
Databases reach consensus every day, so isn’t the impossibility irrelevant?
They reach it under operational assumptions: clocks and timeouts, stable majorities, eventual message delivery, randomness or administrator intervention. FLP says no deterministic protocol guarantees both safety and termination in every execution of the fully asynchronous crash model. Most days fall outside the adversarial executions, and well-designed systems document what happens when their assumptions fail. That is why the claim is restricted to conditions the cited evidence actually tested.
A deterministic protocol guaranteeing consensus termination in every fully asynchronous execution with one possible crash would refute FLP.