← Back to blogs

WTH is FLP Impossibility?

Fischer, Lynch, and Patterson's 1985 proof that consensus is impossible in asynchronous distributed systems — even with only one crash fault, no algorithm can guarantee that all non-faulty processes eventually agree on a value.

1. What FLP Actually Proves

The FLP impossibility result (Fischer, Lynch, Patterson 1985) definitively placed an upper bound on what is possible with distributed processes in an asynchronous environment. The problem of consensus — getting a distributed network of processors to agree on a common value — was known to be solvable in a synchronous setting, where processors could proceed in simultaneous steps and where crash faults could be detected by waiting one step length for a reply. In an asynchronous setting, where there are no bounds on message delivery time, it is impossible to distinguish a crashed processor from one that is simply slow. The FLP result shows that in an asynchronous system, even with only one crash fault, no distributed algorithm can solve the consensus problem.

Consensus has many fundamental applications: committing database transactions, agreeing on a value across replicas, distributed lock services. The three properties that define a consensus algorithm are:

• Termination: Every non-faulty process eventually decides some value.
• Agreement: All processes that decide do so on the same value.
• Validity: The decided value must have been proposed by some process.

FLP concerns a weak form of termination: it is enough that some non-faulty process decides. A strong consensus algorithm satisfies termination for all processes, so FLP rules that out as well.

2. The Asynchronous System Model

The key assumption of the FLP model is asynchrony: there is no upper bound on the time it takes for a processor to send, receive, and process a message. This means a process can never tell whether another process has truly crashed or is simply taking a long time to respond. The model also assumes:

• Reliable communication links (messages are not corrupted, though they may be delayed)
• Fail-stop process failures (processes crash and stop; no Byzantine behavior)
• At most one faulty process in the system

Asynchrony is a general model: real-world networks have variable latency, mobile devices power down and up, and many distributed systems operate in conditions well approximated by asynchrony.

3. Formal Model: Configurations and Events

The paper formalizes the system with N > 2 processors communicating by messages. A configuration captures the internal state of all processors, their current algorithm step, memory contents, and the message buffer. System evolution happens via steps, where a processor calls receive(p), which either returns a message addressed to it or the special value ⊥ (indicating no message). The non-determinism of receive — returning ⊥ or a random message — captures the asynchronous delay. A schedule is a particular execution (possibly infinite) defined by a sequence of events from a starting configuration. An admissible run has at most one faulty process and ensures every message is eventually delivered.

4. The First Lemma: Existence of a Bivalent Configuration

The first main lemma shows that there exists an initial configuration where the decision is not predetermined — it depends on the schedule (message delivery order and failures). The proof idea: assume contrary, that every initial configuration has a predetermined decision (all-0 or all-1). By validity, both 0 and 1 must be possible decisions. Order initial configurations in a chain where adjacent configurations differ by one processor's initial value. Somewhere along this chain, a 0-deciding configuration neighbors a 1-deciding one. They differ only by one processor's initial value, say processor p. From the 0-configuration, there is a run that decides 0 even if p fails (p sends/receives nothing). This same run is also valid from the 1-configuration (since p's value is invisible when p fails). But both cannot decide differently if they take the same steps — contradiction. Hence, there must exist bivalent initial configurations where the outcome depends on the schedule.

5. The Second Lemma: Delaying a Message Preserves Bivalence

The second lemma is the technical core: if the system starts from a bivalent configuration and some message e is applicable, then no matter how e is delayed (applied last among a sequence), the set of reachable configurations always contains a bivalent configuration. The proof shows that if delaying e always led to univalent configurations, one could derive a contradiction by considering two neighboring configurations differing by a single message delivery, and using commutativity of message delivery orders for different processes. The key insight: you can always defer a message long enough to keep the system bivalent.

6. The Adversary Construction: Infinite Non-Deciding Run

Starting from a bivalent initial configuration, the proof constructs an admissible run that never decides: processors are placed in a queue and receive messages in queue order (re-queuing when done). The earliest message to the first processor in the queue (possibly ⊥) is deferred using the second lemma, reaching another bivalent configuration. This process repeats indefinitely, producing an infinite run where no process ever decides. Since all messages are eventually delivered but the adversary can always reorder/delay to preserve bivalence, the protocol is not totally correct.

7. What FLP Does Not Say

• Randomized algorithms: Flushing randomness can circumvent FLP in practice — with probability 1, consensus is eventually reached, though no deterministic guarantee exists.
• Partial synchrony: If messages have eventual known bounds, consensus becomes possible (this is the basis of many real-world systems).
• Failure detectors: Oracles that eventually suspect crashed processes strengthen the model and allow consensus.
• Real systems don't flicker: Practical systems use timeouts, leaders, and failure detectors; FLP's worst case is statistically unlikely.

8. FLP in Practice

Why does Raft or Paxos work in practice if FLP says consensus is impossible? The answer: real systems are not truly asynchronous. They have:

• Upper bounds on message latency (even if loose)
• Physical clocks for timeouts and elections
• Leader-based approaches that reduce the problem to a single coordinator
• Failure detectors (timeouts, heartbeats)

FLP remains a powerful theoretical barrier: it tells you exactly what must be true for consensus to be impossible, and it guides the design of practical workarounds (timeouts, randomization, partial synchrony assumptions).

9. Related Impossibility Results

• CAP theorem: In the presence of a partition, a system must trade consistency for availability (or vice versa). FLP is the unbounded-latency version of the same fundamental tension.
• Two Generals' Problem: Reliable coordination between two processes with unreliable messaging; also impossible deterministically.
• Wait-free hierarchy: Problems solvable without synchronization; consensus is complete for strong failure‑mode solvability.

10. Key Takeaways

• FLP proves deterministic consensus is impossible in purely asynchronous systems with even one crash fault.
• The proof rests on two lemmas: (1) a bivalent starting configuration exists, and (2) an adversary can always delay a message to keep the system bivalent forever.
• Real systems circumvent FLP via timeouts, randomization, partial synchrony, and failure detectors.
• FLP is the theoretical foundation for why practical consensus algorithms (Raft, Paxos, etc.) rely on timing assumptions.

Together with Raft, quorums, vector clocks, and two-phase commit, FLP rounds out the load-bearing pieces of distributed data: a log everyone agrees on, a way to trade consistency for availability, a way to know when updates conflict, a way to make several resources commit as one, and a precise theoretical boundary on what can be achieved without timing assumptions.