FLP Impossibility (Impossibility of Distributed Consensus with One Faulty Process)

What did this paper do?

In 1985 three theorists — Fischer, Lynch and Paterson — proved something that made the whole distributed-systems field go quiet for a moment: in a network like the internet, if even one machine might crash, there is no set of rules that can guarantee all the machines will end up picking the same answer. The load-bearing word is "guarantee." Paxos, Raft and blockchain consensus all live by going around this result.

First, the job to be done

Picture five machines that must take a position on one thing — say, whether a transfer counts as committed or aborted. They can only talk by sending messages, and three rules apply: ① everyone must end up on the same answer; ② both answers must be genuinely possible (otherwise hard-coding "always abort" would count as agreement, which is cheating); ③ every machine that hasn't broken must actually pick, not dither forever. As soon as messages can be arbitrarily slow, and even one machine might crash partway, those three cannot all be met.

The hard part: you can't tell "dead" from "slow"

It all comes down to one sentence: in a network with no upper bound on delay, a machine that has gone silent and a machine that already spoke but whose message is still in flight look exactly the same.

In real life we use timeouts — no reply in ten seconds, call it dead. But that rests on a premise: "normally it won't take more than ten seconds." Here there is no such premise. So you have only two moves: wait forever (possibly forever, breaking ③); or declare it dead and move on — and if it was merely slow, it may wake up already holding a different answer, breaking ①.

How the paper proves it really can't be done

This isn't "nobody has found it yet." It's a proof that nobody can. The idea is lovely: label every momentary state of the system. Some states are already settled — however things go from here the answer must be "commit," or must be "abort." Others still allow both; call those "hanging."

The paper then proves two things: there must be a hanging state right at the start; and as long as the system is hanging, you can always pick one message, slide its delivery slightly later, and have the system still be hanging after that step. Apply that trick forever and the system circles inside "hanging" and never settles.

And the harassment is entirely fair play: it withholds no message and breaks no machine. It only arranges an awkward delivery order. The algorithm has this gap for one reason only — it must be prepared in advance to tolerate one machine crashing, and that readiness is the crack.

So what do engineers do?

If the three can't all hold, you must give one up on purpose, and which one matters. Paxos, Raft and the other algorithms actually in production defend the first two: never two contradictory answers, ever. What they give up is the "guarantee" inside ③ — they don't promise to produce a result within any fixed time. When the network is healthy they almost always settle fast; when it is a mess they would rather stall than be wrong. The other route is rolling dice: pick at random when stuck, and the chance of hanging forever falls to zero.

One honest note: the result says the worst case may drag on forever, not that this is unachievable in practice — real networks don't cooperate with that devious ordering indefinitely, which is exactly why the Paxos family works fine.

Remember this one thing

In a network where messages can be arbitrarily slow, "crashed" and "very slow" look identical; so once even one machine may fail, no algorithm can guarantee both "never two answers" and "an answer always comes out." Every usable consensus algorithm picks between them — keep correctness, give up any promise about how fast.

Want bivalent configurations, the commutativity lemma and the four ways around it? → Switch to the deep read

In one sentence

FLP draws a ceiling over consensus: in an asynchronous message-passing system, if even one process may crash, no deterministic algorithm can simultaneously guarantee "everyone decides the same value," "both values are possible decisions," and "a decision eventually happens." In other words, in an asynchronous world safety can be kept, liveness cannot be guaranteed — a sentence that became the starting point for every consensus system since.

Glossary

Consensus: a group of processes each hold an initial value and, by exchanging messages, must all "decide" the same value. Transaction commit, replica leader election and blockchain block production are all instances of it.
Asynchronous system: a model that assumes no upper bound on how long a message takes or how long a process takes to execute a step; messages are eventually delivered, never lost or forged, but may be arbitrarily slow and arbitrarily reordered. Its opposite is the synchronous model, where known time bounds make a timeout a valid verdict.
Crash fault (fail-stop): a process halts at some moment and never moves again; it never sends false messages. Far milder than a "Byzantine fault," where a process may lie — FLP uses this weakest kind of fault, which makes the result stronger.
Deterministic algorithm: given the current state and the message received, the next step is uniquely determined — no dice. FLP constrains only this class.
Safety / liveness: safety is "nothing bad ever happens" (no two contradictory decisions); liveness is "something good eventually happens" (a decision really is made). Almost every distributed-systems trade-off lives between these two.

Coordinates

The authors are Michael J. Fischer, Nancy Lynch and Michael S. Paterson; the conference version appeared at PODS in 1983 and the final version in JACM in 1985. It follows Lamport et al.'s 1982 Byzantine Generals Problem, which solved fault-tolerant agreement in a synchronous round model — making "can it be done asynchronously?" the natural next question. What it opened up is larger still: Ben-Or's randomized consensus (1983), Dwork-Lynch-Stockmeyer's partial synchrony model (1988), Chandra-Toueg's failure detectors (1996), and the entire design posture of Paxos and Raft. It received the Dijkstra Prize in Distributed Computing in 2001.

The problem and the motivation

By the early 1980s plenty of protocols for distributed transactions, reliable broadcast and replica agreement were already running, but their correctness arguments almost all hid one unspoken premise: timeouts are trustworthy — wait long enough with no reply and the other side is dead. Practical in engineering, indefensible in theory, because nobody can name a delay bound that will "definitely never be exceeded." Remove it and the old ailment of two-phase commit (the coordinator asks "are you all ready?", then announces commit or abort) resurfaces: the coordinator vanishes at the critical moment and the rest dare neither commit nor abort, so they block indefinitely.

So the real question becomes: with no timing assumptions at all, can fault-tolerant agreement be built? FLP casts it in an extremely clean setting: N deterministic processes communicating only by messages, which may be arbitrarily delayed and reordered but are never lost or forged and always eventually delivered; at most one process crashes, and a crash is permanent. Three requirements — agreement (no two distinct decision values), non-triviality (both 0 and 1 are possible decisions), and termination (every non-crashed process eventually decides). Note that the middle one is weaker than the usual "validity," and the weaker the requirement, the stronger the impossibility.

Fig. 1 · Indistinguishability: in an asynchronous network "crashed" and "extremely slow" are identical to everyone else, so a timeout is no longer a valid verdict.

Core idea and method

Step one: label every configuration with a valence

The proof's first move is to treat execution as movement between configurations: a configuration = the internal states of all processes + the messages still sitting undelivered in the buffer. An event is "some process receives one message, changes state, and sends some new messages."

Then label each configuration with its valence: which decision values can still appear in any continuation from here. If only 0 can, it is 0-valent; if only 1 can, 1-valent — jointly univalent, meaning already settled. If both remain possible it is bivalent: still hanging.

In this language, "the algorithm terminates" is equivalent to "the system cannot stay bivalent forever"; to refute it, one need only construct a single infinite execution that is bivalent throughout.

Step two: a bivalent initial configuration must exist

Line up every possible initial configuration: all-0 at the far left, all-1 at the far right, with neighbours differing in exactly one process's initial value. If no initial configuration were bivalent, the line would have to contain an adjacent pair, 0-valent on the left and 1-valent on the right, differing only in process p's input.

Now spend the one permitted crash: let p be dead from the very beginning. The remaining processes must still decide on their own, and what they hold is identical in both configurations — p never uttered a word. So the same execution must yield the same decision, yet the left is doomed to 0 and the right to 1. Contradiction. A bivalent initial configuration must exist.

Step three: bivalence can be preserved forever (the crucial step)

What remains: from any bivalent configuration, for any pending message e, one can always walk a little way first, then deliver e, and still land bivalent. This is what lets the adversary keep the system undecided while never permanently withholding any message.

By contradiction: suppose that however you walk first, delivering e always turns the configuration univalent. Following that assumption, one can always find two configurations one step apart — delivering e at C is doomed to 0, while taking one step e′ first and then delivering e is doomed to 1. Only two cases remain:

e and e′ land on different processes: the two events do not interfere — one process receives its own message and changes its own state, regardless of what the other does. So the two steps commute: e-then-e′ and e′-then-e reach the same configuration, which is then doomed to 0 and doomed to 1 at once. Contradiction.
e and e′ both go to the same process p: then hold p still — the algorithm must tolerate p crashing, so the rest must eventually reach a decision by themselves. Let them run to a univalent configuration A, then put the two held steps back in either order and you can reach both 0 and 1 from A. Contradiction again.

Neither case survives, so a walk that leaves the system bivalent after e must exist.

Fig. 2 · The commuting diamond: two events on different processes can be reordered into the same configuration — the blade that drives "delivering e must settle it" into contradiction.

Step four: assembling the infinite run

The adversary's strategy now falls out: start from a bivalent initial configuration, each round fix on the message that has waited longest in the buffer, use step three to find a walk that delivers it and stays bivalent, take it, then fix on the next oldest, and repeat. The infinite execution so constructed is perfectly legal — every message is eventually delivered and every process takes infinitely many steps — yet the system is bivalent throughout, so no process ever decides.

One sharp detail often missed: in this run no process actually crashes at all. The algorithm exposes a gap solely because it must keep an escape route ready in advance for one possible crash, and that readiness is what forces it, in certain configurations, to stop waiting.

Fig. 3 · The adversary's strategy: consume the oldest pending message each round while always sliding from one bivalent configuration to the next — a fair run that never decides.

Key results

This is a paper with no experiments; its "results" are the theorem itself, and how tightly the boundary is drawn:

The boundary is pushed to the limit: there is only one fault and it is the mildest kind, a crash; messages are guaranteed delivered; the requirement is only the weakest "both values are possible"; and it fails even if only one process is required to decide eventually. Relax any of these further and the conclusion does not weaken.
A revealing counterpoint: the paper itself shows that if the faulty processes are the "never started" kind (initially dead) and a majority are alive, consensus is solvable. The hard part isn't "a node is absent" — it's that a node may fail midway and you cannot tell.

Why it matters

It turned consensus from "how do we do it" into "what do we give up": ever since, every consensus system has had to answer one question — what assumption is your liveness hanging on? Four legitimate detours grew out of it, and they remain the whole map of consensus design:

Partial synchrony: Dwork-Lynch-Stockmeyer (1988) assume a delay bound that eventually holds, though you never know from when. Paxos and Raft take this road — safety holds unconditionally, liveness is redeemed only during stable periods, and timeouts only trigger a leader change rather than declaring who died.
Randomization: Ben-Or (1983) and others let processes roll dice when deadlocked, achieving termination with probability 1 — the adversary cannot foresee the coin flips and so cannot schedule the deadlock out forever.
Failure detectors: Chandra-Toueg (1996) abstract "guessing who died" into an external, fallible module and characterize the weakest one that still solves consensus (◇W) — timing assumptions become a separable component.
Weakening the problem: approximate agreement and k-set agreement relax "everyone must agree exactly," buying back solvability.

And one rule of thumb that still serves engineers well: any system claiming to guarantee fast agreement under arbitrary network conditions is either hiding a timing assumption or is wrong.

Limitations and criticism

The model is extreme, and covers only deterministic algorithms: the adversary in pure asynchrony is unrealistically strong — it can foresee every step of a deterministic algorithm and always schedule the worst order; switch to a randomized algorithm and it is out of range entirely. Real network delays mostly follow statistical regularities, and in practice Paxos almost always converges quickly. FLP says "cannot be guaranteed," not "cannot be done."
A pure worst-case result: it offers no probabilistic characterization — nothing about how likely stalling is or how long a decision is expected to take.
Very easily misquoted: the common misreading is "consensus is impossible in asynchronous systems" (the correct statement is that termination cannot be guaranteed), as is conflating it with CAP — CAP is about trading consistency against availability under a partition, FLP is about liveness being unguaranteeable without timing assumptions. Adjacent concerns, different propositions.

Takeaways

① In one line: in an asynchronous network, if even one process may crash, no deterministic algorithm can guarantee agreement, non-triviality and termination together.

② The pain: protocols broadly assumed "timeouts are trustworthy" while real networks give no delay bound; 2PC blocking forever when the coordinator vanishes is the symptom.

③ The core intuition: a crash and extreme slowness look identical from outside — wait forever and you may never terminate; stop waiting and you may produce two answers.

④ Mechanism one: label configurations by valence — univalent (settled) versus bivalent (still hanging); termination is equivalent to "cannot stay bivalent forever."

⑤ Mechanism two: a bivalent initial configuration must exist — adjacent initial configurations differ in one process's value, and killing that process yields a contradiction.

⑥ Mechanism three: bivalence can be preserved indefinitely — two events on different processes commute into the same configuration (the diamond), and for events on the same process you hold it still and let the others decide first; both branches end in contradiction.

⑦ The resulting infinite run is perfectly legal: every message delivered, every process stepping, yet never deciding — and no process actually crashes in it; the gap comes from the algorithm having to keep an escape route ready.

⑧ The boundary is tight: mildest crash fault, guaranteed delivery, only "both values possible" required, failing even if only one process must decide; conversely, if faulty processes are dead from the start and a majority live, it is solvable.

⑨ Impact and limits: consensus design now runs on "safety unconditional, liveness on assumptions," with four detours — partial synchrony (Paxos / Raft), randomization, failure detectors, weakened problems; but the model is extreme, it binds only deterministic algorithms, and it is often misquoted as "asynchronous consensus is impossible" or conflated with CAP.