Fischer, Lynch, and Paterson proved, in 1985, one of the most consequential negative results in all of computer science: no deterministic algorithm can guarantee consensus in bounded time in a fully asynchronous system, even if only a single process might crash, and even if it never actually does. Not "consensus is hard" — consensus, done deterministically with a guaranteed termination time, is provably impossible under these conditions. This sounds like it should end the whole field before it starts — yet Paxos, Raft, and every real production consensus system exist and work. This article resolves that apparent contradiction: what FLP actually proves, the proof's core idea (a system that can be kept forever in an undecided "bivalent" state), and exactly which of FLP's assumptions every practical algorithm since has relaxed to escape the impossibility — the single most important "why" behind the design of every algorithm from Phase 5 onward.
The theorem, stated precisely
The 1985 paper, "Impossibility of Distributed Consensus with One Faulty Process" (Fischer, Lynch, Paterson — hence "FLP"), proves: in an asynchronous message-passing system (no bound on message delay — article 1.1's "Lie #1," formalized), where processes communicate only by messages and can fail only by crashing (not Byzantine — the gentlest failure model, which makes the impossibility result even stronger, since it applies even under the easiest conditions), no deterministic algorithm can guarantee that all correct processes reach agreement in a finite amount of time, even if at most one process may crash.
Every word in that sentence is load-bearing, and popular summaries of FLP routinely drop one and thereby overstate or understate what it actually says:
- Asynchronous — no timing assumptions at all, not even a generous one. This is a much stronger assumption than "the network is sometimes slow"; it means literally no upper bound on message delay can be assumed by the algorithm.
- Deterministic — given the same inputs and message arrivals, the algorithm always makes the same decisions. This word is the single biggest key to how FLP gets circumvented in practice (more below).
- Crash failures only — the weakest, gentlest failure model (article 1.1's spectrum). FLP doesn't need Byzantine failures to prove impossibility — crash failures alone are already enough, which is part of what makes the result so striking.
- Bounded time / guaranteed termination — this is about liveness (the algorithm eventually decides), not safety (the algorithm never decides incorrectly). FLP does not say consensus algorithms can be unsafe — it says they cannot be guaranteed to always terminate in bounded time.
The proof idea: bivalent states, kept alive forever
The proof is an adversary argument — imagine a maximally unhelpful (but not cheating; still following the rules) network scheduler trying to prevent the algorithm from ever deciding, and show it always has a move available. The core concept is a bivalent configuration: a system state from which both outcomes (deciding 0, or deciding 1, using a simple binary consensus problem for the proof) are still reachable, depending on how future messages get scheduled and delivered. Its opposite, a univalent configuration, is one where the eventual decision is already determined no matter what happens from here — the system just hasn't necessarily realized it yet.
The proof has two main parts, sketched at a level that captures the actual mechanism without requiring the full formal machinery:
- An initial bivalent configuration always exists. With enough processes and appropriate starting inputs, you can always construct a starting state where the outcome genuinely isn't determined yet — both 0 and 1 remain reachable depending on scheduling.
- From any bivalent configuration, there's always a way to schedule the next message delivery that keeps the system bivalent. This is the crux of the whole proof. Whenever the algorithm is about to take a step that would push the system toward becoming univalent (committing to one outcome), the adversarial scheduler can instead choose to delay exactly the message that would trigger that step, and deliver a different message from a different process first, which provably preserves bivalence. Because the network is asynchronous, the scheduler is always allowed to do this — there's no timing rule preventing an indefinite delay of any single message, as long as it's eventually delivered (the delay just has to be finite, never infinite — the scheduler isn't cheating by dropping messages, only reordering and delaying them).
Chain step 2 forever, and the system never leaves the bivalent state — meaning it never actually decides, for an unbounded amount of time — while every individual message the algorithm sent is still, eventually, delivered (satisfying the fairness/liveness requirements of the message-passing model, so the adversary isn't "cheating" by simply disconnecting a process forever, which would trivially prevent consensus for an unrelated, uninteresting reason). This is the whole proof: an adversarial-but-fair scheduler can always find one more message to strategically delay, forever, keeping the algorithm undecided.
Fig 1 — The adversary never breaks fairness (every message is eventually delivered) — it just always has one more strategic delay available to preserve bivalence.
How every practical algorithm actually escapes FLP
This is the section that matters most for the rest of this series — every classical algorithm you'll encounter starting in Phase 5 is, in a real sense, a specific engineering answer to "which of FLP's assumptions do we relax, and how." There are exactly three well-studied escape hatches, and different algorithms pick different ones (or combinations):
Escape 1 — Add partial synchrony (timeouts)
FLP requires fully asynchronous — zero timing assumptions whatsoever. Real networks, while not perfectly synchronous, do have some statistical regularity most of the time (this is exactly what article 2.4's failure detectors formalize and exploit). If you assume the system is asynchronous most of the time but eventually behaves synchronously enough, long enough, for an algorithm to make progress (this is called the partial synchrony model, formalized by Dwork, Lynch, and Stockmeyer in 1988), FLP's impossibility no longer applies — you're no longer in the fully-asynchronous setting the proof requires. This is precisely why Raft and Multi-Paxos use timeouts and leader election: they're not naively ignoring FLP, they're deliberately operating in the partial-synchrony model where the impossibility doesn't hold, accepting that during genuinely bad, prolonged asynchrony (rare in practice, but not impossible), the algorithm might be temporarily unable to make progress — which is a liveness compromise, not a safety one, and one FLP itself shows is unavoidable in the worst case for any deterministic approach.
Escape 2 — Randomization
FLP's proof specifically requires the algorithm to be deterministic — the adversary's strategy (find and delay the message that would resolve bivalence) depends on being able to predict, from the algorithm's rules, exactly which message delivery would matter. A randomized consensus algorithm — one that occasionally makes a coin-flip decision when otherwise stuck — denies the adversary this predictability. Ben-Or's 1983 randomized consensus algorithm (predating FLP's 1985 publication, interestingly) terminates with probability 1 (guaranteed to eventually terminate, though not with a fixed, predictable bound on exactly when) even in a fully asynchronous system. This escape hatch is used less often in mainstream production consensus (Paxos and Raft are both deterministic, using escape hatch 1 instead) but is a real, actively used technique in some Byzantine consensus protocols in Phase 6.
Escape 3 — Failure detectors
This is the direct payoff from article 2.4: Chandra and Toueg's own follow-up work showed that augmenting an asynchronous system with a failure detector of class ◇S (eventually strong — exactly the class discussed in the previous article) is sufficient to solve consensus reliably, sidestepping FLP by adding exactly the "extra oracle-like power" that a pure asynchronous message-passing model lacks. This is, in a real sense, a formalized version of escape hatch 1 — a failure detector is essentially a structured way of encoding "some amount of timing information is available after all," proven to be exactly enough.
| Escape hatch | What it relaxes | Used by |
|---|---|---|
| Partial synchrony + timeouts | drops "fully asynchronous, zero timing assumptions" | Raft, Multi-Paxos, essentially all mainstream production consensus (Phase 5) |
| Randomization | drops "deterministic" | Ben-Or's algorithm; some randomized Byzantine protocols (Phase 6) |
| Failure detectors (◇S) | adds a formalized oracle for "who's probably alive" | The theoretical framing underlying most practical leader-election designs |
Why this is the deepest "why" in the whole series
Every design choice you'll see from Phase 5 onward — Raft's randomized election timeouts (escape hatch 1, with a touch of randomization to avoid split votes, which is itself a small use of escape hatch 2), Multi-Paxos's leader leases, the entire concept of a "term" or "epoch" number that increases across failed leader-election attempts — is traceable back to this single theorem. None of these algorithms guarantee termination within a fixed, known time bound under worst-case adversarial scheduling, because FLP proves that's impossible for a deterministic algorithm in a fully async model. What they guarantee instead is the much more nuanced, and entirely achievable, promise: safety always, and liveness eventually, under reasonable (partially synchronous) network conditions — precisely the shape of guarantee this article's escape hatches make possible.
Closing Phase 2
Phase 2 built the complete formal vocabulary for "time" and "failure" that Phase 1 used informally. 2.1 showed physical time can't be trusted for cross-machine ordering, even with excellent synchronization. 2.2 and 2.3 showed causal (logical) ordering as the alternative that needs no physical clock at all, with Lamport clocks giving cheap total ordering and vector clocks giving exact concurrency detection. 2.4 formalized exactly how much uncertainty a failure detector can responsibly resolve. This article closes the phase with the deepest result of all: a hard mathematical limit on what's achievable at all, and the three principled ways every real algorithm works around it.
Phase 3 (Replication) now returns to more concrete, mechanical ground — state machine replication, log replication, the full formal treatment of quorums (previewed informally back in article 1.2), and leases for linearizable reads. With Phase 1's motivation and Phase 2's formal vocabulary in hand, Phase 3 builds the actual machinery every consensus algorithm operates on top of, setting up Phase 4's introduction of real consensus primitives and Phase 5's classical algorithms.
FAQ
If FLP is from 1985, why does it still matter for algorithms designed decades later, like Raft (2014)?
Because it's a mathematical proof, not an engineering limitation specific to 1985-era systems — it applies to any deterministic algorithm in a fully asynchronous model, regardless of when it's designed. Raft's design (2014) is explicitly informed by FLP; its randomized election timeouts are a direct, acknowledged engineering response to exactly this theorem, not an accident of implementation.
Does FLP apply to Byzantine consensus algorithms too (Phase 6)?
Yes, and more so — FLP's impossibility already holds for the gentler crash-failure model, so it necessarily also constrains the strictly harder Byzantine failure model (any impossibility that holds for an easier problem also holds for a harder one). PBFT and other Byzantine algorithms (Phase 6) use the same escape hatches — partial synchrony assumptions in particular — for the same underlying reason.
Is there a simple, intuitive one-line summary of why FLP is true?
The cleanest intuition: in a network with literally no delay bound, you can never distinguish "this crucial message is still in flight" from "the sender crashed and it's never coming" (this is article 1.1's core ambiguity, formalized). Any deterministic algorithm that would decide based on "I haven't heard from you, so I'll assume X" can therefore always be fooled by an adversary that simply delays that one message a little longer, every time, forever — which is exactly the bivalence-preservation argument.
Do real-world network timeouts effectively make FLP a non-issue in practice?
They make it a manageable engineering trade-off rather than a blocking impossibility, yes — but it's worth being precise that timeouts don't "solve" FLP, they change the model (to partial synchrony) so FLP's specific impossibility no longer applies. The cost is that a sufficiently adversarial or catastrophically bad network can, in principle, still cause temporary unavailability (not incorrectness) — a real, if rare, phenomenon in production systems, and part of why "the network partitioned for an unusually long time" incidents (like the ones in article 1.1) can cause extended unavailability rather than data corruption.
Takeaways
- FLP (1985) proves: no deterministic algorithm can guarantee consensus in bounded time in a fully asynchronous system, even with just one possible crash failure.
- It is a statement about liveness (guaranteed bounded termination), not safety — it does not say consensus algorithms must be incorrect, only that they can't be guaranteed to always finish in bounded time under worst-case async conditions.
- The proof works by showing an adversarial-but-fair scheduler can always find one more message to strategically delay, keeping the system in an undecided bivalent state forever, without ever violating the "every message eventually delivered" fairness rule.
- Three well-studied escape hatches let real systems avoid the impossibility: partial synchrony (timeouts — used by Raft/Paxos), randomization (used by Ben-Or's algorithm and some BFT protocols), and failure detectors (the ◇S class from article 2.4, formally sufficient).
- Nearly every practical design choice in classical consensus algorithms (Phase 5) — randomized election timeouts, leader leases, term/epoch numbers — is a direct engineering response to this theorem.
- Phase 2 is now complete: physical clocks (2.1), logical/causal ordering (2.2, 2.3), failure detection (2.4), and the fundamental limit on what's achievable at all (2.5) — the full formal toolkit Phase 5's algorithms are built from.
References & further reading
- Fischer, Lynch & Paterson — Impossibility of Distributed Consensus with One Faulty Process (1985) — the primary source; the original proof.
- Dwork, Lynch & Stockmeyer — Consensus in the Presence of Partial Synchrony (1988) — formalizes the partial synchrony model that most real algorithms rely on to escape FLP.
- Chandra & Toueg — Unreliable Failure Detectors for Reliable Distributed Systems (1996) — the failure-detector escape hatch, full treatment in article 2.4.
- cvam.sight — Consensus 2.4: Failure Models and Failure Detectors — the ◇S class this article's third escape hatch relies on.
- cvam.sight — Consensus Algorithms series hub — Phase 3 (Replication) picks up next.