Summary

  • Fischer, Lynch and Paterson proved that any deterministic, partially correct consensus protocol in their fully asynchronous message-passing model has an admissible execution that never decides when one crash is allowed.
  • The proof keeps the system bivalent by postponing a critical event; independent events can be commuted without revealing which decision value must win. Messages remain reliable and the constructed schedule can still be fair.
  • Partial synchrony, failure detectors and randomization change the assumptions. A timeout may be useful engineering, but it neither proves a process has failed nor makes an ordinary outage an instance of FLP.

Suppose a coordinator has been silent for thirty seconds. One replica calls it dead; another sees a slow network; a third is waiting on a message that will arrive next. Nothing in the observed silence settles which account is true. That uncertainty is the difficult part of asynchronous consensus—and also the source of the most common exaggeration about it.

The 1985 paper Impossibility of Distributed Consensus with One Faulty Process, by Michael J. Fischer, Nancy A. Lynch and Michael S. Paterson, is often reduced to “consensus is impossible.” Its actual claim is narrower and more useful. Within a deliberately severe model, no deterministic protocol that is safe on every reachable state can guarantee that every admissible execution reaches a decision. There is always at least one legal way for events to unfold that keeps a decision just out of reach.

A system without a stopwatch

The model contains deterministic processes communicating by messages. There is no upper bound on a process step or a message delay, no synchronized clock and no timeout that can turn waiting into knowledge. A message may arrive very late or out of order, but the channel is not casually allowed to corrupt or discard it. Messages sent to a nonfaulty process must eventually be delivered when that process continues receiving.

An admissible execution has at most one faulty process and eventually delivers every message addressed to a nonfaulty one. A process is nonfaulty if it takes infinitely many steps. These definitions matter because the impossibility is not manufactured by an endless black hole in the network. The proof constructs an infinite schedule that can keep serving processes and messages fairly while never allowing the global state to become committed to one answer.

The specification is also intentionally modest. Processes must not decide different values, and both values must be possible in some executions. For termination, the proof only needs to defeat the weak requirement that some process eventually decide in every admissible run. If even that cannot be guaranteed, stronger requirements cannot be guaranteed either.

Bivalence is suspended possibility

Fischer, Lynch and Paterson describe the system through configurations: the local state of every process plus the messages waiting in transit. A configuration is 0-valent if all possible continuations that decide choose 0, 1-valent if they choose 1, and bivalent if both outcomes remain reachable.

Bivalence is not indecision inside one machine. It is a property of the future cone of the whole distributed state. From a bivalent configuration, some legal continuation ends at 0 and another at 1. Once a configuration becomes univalent, safety prevents it from changing allegiance later.

The proof first shows that some initial configuration must be bivalent. Otherwise, as one changes inputs one process at a time, there would be adjacent initial states with opposite valency. A process whose input differs between those states could crash before acting, leaving the other processes unable to distinguish which world they occupy—a contradiction.

The decisive step then studies an applicable event, such as one process receiving one pending message. If every route that postpones that event eventually made its application univalent, there would be a critical boundary where one event changes the only possible decision. But steps by different processes commute: applying one and then the other reaches the same configuration as applying them in the reverse order. That commuting square makes incompatible valencies collapse into a contradiction.

So the scheduler can keep choosing finite stretches that preserve bivalence, eventually give the selected event its turn, and repeat. By rotating through processes and queued messages, it produces an admissible infinite run in which work continues, deliveries occur and no decision is reached.

The result is existential, not atmospheric

“There exists a nondeciding admissible execution” is not the same statement as “every execution fails.” Real systems commonly decide because their actual runs are kinder than the worst legal run, or because their design assumes more than the FLP model supplies. The theorem removes an unconditional guarantee; it does not erase successful operation.

Nor does a stalled election diagnose FLP. A production incident may involve dropped packets, overloaded storage, software defects, correlated failures, bad quorum configuration or an unsafe retry loop. Calling all of them “FLP” substitutes a famous label for evidence. To connect an incident to the theorem, an analysis would need to establish the relevant model, show that safety constrained the available steps, and explain how indistinguishable delay and failure blocked guaranteed progress.

Three ways to alter the contract

Later work made the boundary productive. Dwork, Lynch and Stockmeyer formalized partial synchrony: timing bounds may exist but be unknown, or begin to hold only after an unknown stabilization time. Protocols can then wait for a period in which the stronger condition is true and make progress without pretending it was always true.

Chandra and Toueg studied unreliable failure detectors, specifying what they eventually know through completeness and accuracy. A failure detector does not extract certainty from silence; it adds an information service whose guarantees must be stated.

Randomized protocols, including Ben-Or's early work, change another premise. Private probabilistic choices prevent a deterministic adversary from indefinitely steering the same state-transition structure, yielding probabilistic rather than universal deterministic termination claims.

These are not loopholes in a failed theorem. They are different contracts. The discipline FLP introduced is to name the contract before making a promise.

Nancy Lynch's enduring contribution

Lynch's later recollection preserves the collaborative character of the result: Fischer and Lynch began pursuing the problem in 1982, and Paterson joined the argument that became the final proof. Its intellectual economy lies in localizing a global impossibility to the ordering of critical events and to what the rest of the system can distinguish if one process is absent.

The practical lesson is therefore not pessimism. It is architecture with disclosed assumptions. A consensus system should say which failures it tolerates, what its clocks and failure detectors guarantee, when safety takes precedence over availability, and under what conditions it expects liveness. FLP is the boundary marker that makes those promises auditable.

Sources