The FLP Impossibility Result

Why 1985 was the right time for this. The early 1980s had produced a run of positive results: Byzantine agreement was solvable with enough participants, various fault-tolerant protocols worked, and the mood was that distributed agreement was a hard engineering problem yielding to good algorithms. Almost all of that work assumed synchrony, usually without remarking on it. FLP isolated that assumption and showed it was load-bearing. In one stroke, the field learned that "how fast is the network" was not an implementation detail but a term in the theorem.

The result is a statement about models, not about reality. This is where serious disagreement about its practical weight lives.

One camp holds that the pure asynchronous model is a mathematical extreme with no physical instance — real networks have finite speed of light, real machines have clocks with bounded drift, and treating "arbitrarily long delay" as possible is a modelling choice, not a fact about the universe. On this reading FLP is important for what it clarifies conceptually and irrelevant to whether your cluster elects a leader tonight.

The other camp answers that the asynchronous model is precisely right for correctness arguments, because the events that stretch delays in practice — multi-second garbage-collection pauses, virtual machines suspended by the hypervisor, BGP reconvergence, a switch that buffers for thirty seconds — are unbounded in any way you can prove. A protocol whose safety depends on a timeout being long enough is a protocol with an undocumented and unverifiable assumption. Kleppmann's treatment is emphatic on this point: timeouts are fine for liveness and disastrous for safety.

Both camps agree on the design rule that follows, which is the useful output: never let safety depend on a timing assumption; let only liveness depend on it. That principle is FLP's real legacy, and it is why Paxos and Raft are structured the way they are.

What the escapes have in common. Each of the three standard escapes adds something the pure model lacks, and it is worth seeing that they are the same move in different guises.

• Partial synchrony adds an eventual timing bound.
• Failure detectors add an oracle that eventually stops suspecting live processes.
• Randomisation adds coin flips, so the adversary can no longer predict which schedule to construct.

The first two give the system a way to eventually tell "crashed" from "slow". The third removes the adversary's ability to aim. In every case the added ingredient attacks the same blind spot the impossibility exploits.

A word on how the result is misused. "FLP says consensus is impossible, so we use eventual consistency instead" is a very common sentence and a confused one. FLP does not make consensus unusable — half the internet runs on it. If a design abandons coordination, that should be justified by latency, availability or operational cost, not by an appeal to a theorem about guaranteed termination under adversarial scheduling. The theorem is precise. Borrowing its authority for a vaguer claim is a way of not making the argument.

Before 1985. The early distributed-algorithms literature was largely synchronous by default. The Byzantine agreement work of Pease, Shostak and Lamport (1980, 1982) assumed known bounds on message delivery, as did most protocols for atomic commit and clock synchronisation. The assumption was usually stated but rarely interrogated, and the open question — whether the same problems were solvable without it — was recognised as important and unresolved.

1983. A preliminary version of the result appeared at the ACM Symposium on Principles of Database Systems, arriving in the database community first, where the atomic-commit problem made its relevance immediate.

1985. The full paper, "Impossibility of Distributed Consensus with One Faulty Process", appeared in the Journal of the ACM, volume 32, pages 374–382. It is nine pages long. The reaction was not despair but redirection: within three years the partial-synchrony models existed, randomised protocols were being refined, and the question had changed from "can we do this?" to "what is the least we must assume?".

1988. Dwork, Lynch and Stockmeyer published the partial-synchrony framework, which is the model essentially every production consensus system is analysed in today.

1996. Chandra and Toueg's failure-detector papers closed the question of how much failure information consensus requires, identifying $\Diamond W$ as the weakest sufficient detector.

2001. The paper received the PODC Influential-Paper Award, since renamed the Dijkstra Prize in Distributed Computing. Fischer, Lynch and Paterson had by then been cited by essentially every subsequent paper on asynchronous fault tolerance.

Afterwards. The result's influence is visible in the shape of the field: the standard structure of a modern consensus paper — state the timing model, prove safety unconditionally, prove liveness under an eventual-synchrony assumption — is the format FLP forced into existence.

It ended a search that could not succeed. Before 1985 it was reasonable to believe that a sufficiently clever asynchronous consensus protocol existed and had simply not been found. Afterwards the question was closed, and the effort went into the models and mechanisms that make consensus achievable in practice. Impossibility results are valuable precisely because they redirect work, and this one redirected an entire subfield within three years.

It made the timing model a first-class part of a specification. After FLP, you cannot describe a distributed algorithm without saying what you assume about message delay, and the assumption is understood to be doing real work rather than being background detail. That discipline is now universal and it is a direct consequence of this paper.

It gave engineers the safety/liveness split. The most portable lesson is not the theorem but its shape. Because guaranteed termination is unavailable, a correct system must be designed so that failure to terminate is survivable — which means never letting a timeout influence whether the system is correct, only whether it is making progress. Systems that violate this rule fail silently and unrecoverably; systems that honour it stall visibly and recover. Every well-designed consensus implementation shipped since has this structure.

It explains a class of production incident. When a cluster loses quorum and elects no leader, when a transaction coordinator blocks holding locks, when a distributed lock service stops issuing leases during a network wobble, engineers are seeing FLP in operation. The system is not broken and there is no bug to fix. It has correctly chosen to stop rather than to risk splitting, and it will recover when the network does. Knowing that is the difference between waiting and making things much worse.

Every coordination service you use. etcd, Consul, ZooKeeper and the Raft or Paxos layer inside Spanner, CockroachDB, TiDB and YugabyteDB all implement the same bargain: unconditional safety, timing-dependent liveness. When Kubernetes becomes unresponsive because etcd cannot elect a leader, that is the theorem being honoured, not violated. The correct operational response — restore network health and wait — follows directly from understanding which property was given up.

Leases and fencing tokens. A distributed lock granted with a timeout is unsafe on its own: the holder may be paused by garbage collection past its lease expiry and then act as though it still holds the lock. The standard fix, which Kleppmann popularised, is a monotonically increasing fencing token checked by the storage layer, so a stale holder's writes are rejected. This is FLP-shaped reasoning applied to a routine engineering problem — the timeout cannot be trusted for safety, so safety is enforced by an order that does not depend on time.

Cloud database configuration. The election-timeout and heartbeat settings in every consensus-based database are the operator's chosen point on the liveness trade-off. Short timeouts detect real failures fast and cause spurious elections during transient delays; long ones are stable and slow to recover. There is no setting that eliminates the trade-off, because eliminating it is what the theorem forbids.

Blockchain finality. Proof-of-work chains sidestep deterministic consensus entirely, offering probabilistic finality that strengthens with depth — a randomised escape at planetary scale. Modern proof-of-stake designs including Ethereum's Casper FFG, Tendermint and HotStuff return to classical partially-synchronous BFT consensus, and consequently inherit the classical behaviour: they halt rather than fork when the network partitions or participation drops below threshold. Ethereum's inactivity leak is an explicit mechanism for recovering liveness after such a halt, and it exists because the protocol correctly refuses to trade away safety.

Serverless and autoscaling infrastructure. Systems where processes are routinely suspended, migrated or throttled by the platform have delay distributions with much fatter tails than a fixed fleet of machines. The asynchronous model is a better fit than it used to be, and protocols whose safety was quietly leaning on a timing assumption are more likely to be caught out.

Consensus-free design. CRDTs, gossip protocols and last-writer-wins replication avoid the problem by choosing a specification that does not require agreement. This is a legitimate and often excellent answer — but it is a change of requirements, not a way around the theorem, and the appropriate justification is that the application genuinely tolerates divergence, not that consensus is theoretically impossible.

The formal model

Fix $n \geq 2$ asynchronous processes $P_1, \dots, P_n$, each a deterministic automaton with an initial value in ${0,1}$ and a write-once output register. A global message buffer holds messages of the form $(p, m)$, meaning $m$ is destined for process $p$. Two primitives act on it: $\mathrm{send}(p,m)$ places a message, and $\mathrm{receive}(p)$ removes and returns some message for $p$, or returns the special value $\emptyset$.

The $\emptyset$ return is the crux of the formalisation. A process asking for messages may be told there are none even when messages for it exist in the buffer, because the network is slow. The only fairness requirement is that in an infinite run, every message is eventually delivered — no message is delayed forever. Delays may be arbitrarily long but not infinite.

A configuration $C$ is the internal state of every process plus the contents of the buffer. A step applies $\mathrm{receive}$ to one process, followed by whatever finite local computation and sends its state machine dictates; a step is identified by the event $e = (p, m)$. Applying a sequence of steps $\sigma$ to $C$ gives $\sigma(C)$, called a reachable configuration.

An admissible run is one in which all messages are eventually delivered and at most one process crashes (takes only finitely many steps). A run is a deciding run if some process writes its output register. The protocol is totally correct in spite of one fault if every admissible run is a deciding run, all decisions agree, and both outcomes are reachable from some initial configuration.

Valence

The engine of the proof is a classification of configurations by what futures remain open.

Let $V(C)$ be the set of decision values reachable from $C$ in some admissible run.

• $C$ is 0-valent if $V(C) = {0}$ — the outcome is already sealed at 0.
• $C$ is 1-valent if $V(C) = {1}$.
• $C$ is bivalent if $V(C) = {0,1}$ — both outcomes are still possible.

A bivalent configuration is one in which the system has not yet made up its mind, even implicitly. Note that no process has decided in a bivalent configuration: a decision is irrevocable, so it would fix the valence.

Lemma 1 — some initial configuration is bivalent

Suppose not: every initial configuration is univalent. Validity forces the all-0 initial configuration to be 0-valent and the all-1 configuration to be 1-valent. Arrange all $2^n$ initial configurations so that adjacent ones differ in exactly one process's input. Somewhere along the chain from all-0 to all-1 there must be adjacent configurations $C_0$ (0-valent) and $C_1$ (1-valent) differing only in the input of some process $p$.

Now consider an admissible run from $C_0$ in which $p$ crashes at the very start and never takes a step. Every other process behaves identically whether it started from $C_0$ or $C_1$, because the only difference between them is inside $p$, which never speaks. So this run is also admissible from $C_1$ and produces the same decision. But $C_0$ must decide 0 and $C_1$ must decide 1. Contradiction. Hence some initial configuration is bivalent. $\square$

This is where the single crash fault is spent. With no faults at all, the argument does not go through and consensus is straightforwardly solvable.

Lemma 2 — bivalence can always be preserved

Let $C$ be a bivalent configuration and let $e = (p,m)$ be an event applicable to $C$. Let $\mathcal{D}$ be the set of configurations reachable from $C$ without applying $e$, and let $\mathcal{E} = { e(D) : D \in \mathcal{D} }$. Then $\mathcal{E}$ contains a bivalent configuration.

Suppose it does not, so every configuration in $\mathcal{E}$ is univalent. One can show $\mathcal{E}$ contains both a 0-valent $E_0$ and a 1-valent $E_1$ (otherwise $C$ itself would be univalent). Tracing back, there must exist neighbouring configurations $C_0, C_1 \in \mathcal{D}$ with $C_1 = e'(C_0)$ for some event $e' = (p', m')$, such that $e(C_0)$ is 0-valent and $e(C_1)$ is 1-valent. Two cases:

Case $p' \neq p$. The events commute, because they act on different processes: $e(e'(C_0)) = e'(e(C_0))$. But the left side is $e(C_1)$, which is 1-valent, and the right side is reachable from the 0-valent $e(C_0)$, so it is 0-valent. Contradiction.

Case $p' = p$. Consider a finite deciding run $\sigma$ from $C_0$ in which $p$ takes no steps at all — admissible, since $p$ is allowed to be the one crashed process. Let $A = \sigma(C_0)$. Because $\sigma$ involves no step of $p$, it commutes with both $e$ and $e'$, giving $e(A) = \sigma(e(C_0))$, which is 0-valent, and $e(e'(A)) = \sigma(e(C_1))$, which is 1-valent. But $A$ is a deciding configuration, so its valence is already fixed, and every configuration reachable from it must share that valence. Contradiction. $\square$

The theorem

Build a run as follows. Start at a bivalent initial configuration, which Lemma 1 supplies. Maintain a queue of processes and, at each stage, take the process at the head of the queue and the oldest message for it in the buffer; call that event $e$. By Lemma 2, there is a finite sequence of steps after which applying $e$ leaves the configuration bivalent. Apply that sequence, then $e$, then move the process to the back of the queue.

Every stage is finite, delivers at least one message, and preserves bivalence. Repeating forever produces an infinite run in which every message is eventually delivered — so it is admissible, and indeed no process even crashes — and in which the configuration is bivalent at every point, so no process ever decides.

Theorem (Fischer, Lynch and Paterson, 1985). No consensus protocol is totally correct in spite of one fault in an asynchronous system. $\square$

Two things about this deserve emphasis. First, the constructed run has no failures in it at all; the possibility of one failure is what forces the protocol to be structured in a way the adversary can exploit. Second, the run is infinite. FLP is not about deadlock. The system is busy and alive throughout, and simply never converges.

Escape 1: partial synchrony

Cynthia Dwork, Nancy Lynch and Larry Stockmeyer (1988) defined the models that practical systems live in. Two variants, both sufficient:

• Bounds $\Delta$ on message delay and $\Phi$ on relative process speed exist and are known, but hold only after some unknown global stabilisation time.
• The bounds hold from the start but their values are unknown.

Under either, consensus is solvable, with resilience $n > 2f$ for crash faults and $n > 3f$ for Byzantine faults. The structural insight is the separation of concerns: safety holds in all executions, including fully asynchronous ones; liveness holds only after stabilisation. Since the system need not know when stabilisation has occurred, the protocol simply keeps retrying and succeeds once conditions permit.

Escape 2: failure detectors

Tushar Chandra and Sam Toueg (1996) asked how much information about failures is needed, and answered it exactly. A failure detector is an unreliable oracle at each process that outputs a set of suspected processes; it may be wrong, and may change its mind. Two properties matter:

• Completeness. Every crashed process is eventually permanently suspected.
• Accuracy. Some correct process is eventually never suspected.

The detector $\Diamond W$ — eventually weak — satisfies weak completeness and eventual weak accuracy, and Chandra and Toueg showed consensus is solvable with it for $n > 2f$. In a companion paper with Vassos Hadzilacos they proved $\Diamond W$ is the weakest failure detector for consensus: any detector that solves consensus can be transformed into one at least as strong. That is a remarkably sharp statement about the price of the escape.

In practice a failure detector is a heartbeat with a timeout, which is exactly where the smuggled timing assumption lives. The framework's value is that it isolates the assumption in one named component instead of scattering it through the protocol.

Escape 3: randomisation

Michael Ben-Or (1983) and Michael Rabin (1983) showed that a protocol allowed to flip coins solves consensus with probability 1 — termination is guaranteed with probability 1 rather than in every execution, so the theorem's letter is respected while its practical bite is removed. The FLP adversary must be able to predict the protocol's next move to construct the infinite run; against a randomised protocol it cannot, and the probability of maintaining bivalence for $k$ rounds falls off exponentially.

Ben-Or's protocol is short: processes broadcast their values, and if a strong majority appears they adopt it, otherwise they flip a coin. Expected running time is exponential in $n$ for a local coin and constant for a shared one, which is why practical randomised protocols such as those in HoneyBadgerBFT use cryptographic common-coin constructions.

Where Paxos and Raft actually sit

Neither violates FLP, and understanding why is the best single check on whether you have understood the theorem.

Paxos (Lamport, 1998) guarantees agreement and validity in every execution, with no timing assumptions whatsoever. Two proposers can duel indefinitely, each pre-empting the other's proposal with a higher ballot number, and no value is ever chosen. That live-lock is FLP, faithfully reproduced. Lamport's own resolution is to designate a distinguished proposer and note that progress requires the network to eventually behave — which is the partial-synchrony escape, stated informally.

Raft (Ongaro and Ousterhout, 2014) makes the same bargain in a more prescriptive form. Its election safety, log-matching and state-machine safety properties hold unconditionally. Its liveness depends on election timeouts, and the algorithm randomises them precisely so that split votes are unlikely to repeat — randomisation applied to the liveness problem, not the safety one. If the network delays messages just past every timeout, Raft elects nobody, exactly as the theorem allows.

The design pattern generalises, and it is the single most valuable thing FLP taught the field:

$$\text{safety: unconditional} \qquad \text{liveness: conditional on synchrony}$$

A protocol that inverts this — guaranteed to terminate, safe only if the network behaves — is broken, and the failure will be silent data corruption rather than a stalled cluster.