FLP Impossibility

Symptom

Your cluster of five nodes elects a leader. It works. It has worked for a year.

Then one afternoon a garbage collection pause on the leader runs for twelve seconds. The followers time out, start an election, and elect a new leader. The old leader wakes up, has no idea it was deposed, and keeps serving writes. For a few hundred milliseconds you have two leaders, and if your fencing is not airtight, two writes that should have been ordered land in an order nobody chose.

You fix it by raising the timeout. Now failover takes thirty seconds instead of five, and an actual crash costs you thirty seconds of downtime. So you lower it. Now spurious elections come back.

You are tuning a dial with a bad outcome at each end, and there is no setting that makes both problems go away. That is not a gap in your understanding of the configuration. It is FLP.

The question the timeout is trying to answer is: is that node dead, or slow? And in an asynchronous system, that question has no answer. A message that has not arrived yet and a message that will never arrive look identical from where you are standing, and no amount of waiting distinguishes them, because waiting longer only ever rules out “arrived by now.”

Statement

The setting is the asynchronous model. Messages are eventually delivered, but with no bound on how long that takes. Processes have no synchronized clocks and no timeouts, because a timeout is a bound and there are none. Exactly one process may fail, and only by crashing — it stops, silently, and never lies.

Consensus requires three properties: agreement (no two correct processes decide differently), validity (the decided value was proposed by someone), and termination (every correct process eventually decides).

In an asynchronous system with even one possible crash failure, no deterministic protocol solves consensus.

Note how weak the failure model is. One crash. No Byzantine behaviour, no message loss, no network partition, no corruption, no lying. The channel is reliable. This is much weaker than Two Generals (T061), which needed message loss, and the impossibility still bites.

And note which property fails. Agreement and validity are achievable — a protocol that never decides anything satisfies both trivially. It is termination that cannot be guaranteed. FLP does not say your consensus protocol will produce a wrong answer. It says there is an execution in which it produces no answer, forever.

Argument

The proof is a strategy for an adversary who controls only message scheduling, not content, and it has two moves.

Configurations and valence. A configuration is the full global state: every process’s local state plus every message in flight. Call a configuration 0-valent if every reachable decision from it is 0, 1-valent if every reachable decision is 1, and bivalent if both outcomes remain reachable. Bivalent means undecided in the strongest sense: the outcome is not yet determined by the state.

Move one: some initial configuration is bivalent.

Line up the $2^n$ initial configurations so that adjacent ones differ in exactly one process’s input. The all-zeros configuration must decide 0 by validity, and the all-ones must decide 1. So somewhere along the line there are two adjacent configurations $C$ and $C’$, differing only at process $p$, with different decisions.

Now run the execution in which $p$ crashes immediately, at the very start. The remaining processes cannot see $p$’s input, so $C$ and $C’$ are indistinguishable to all of them, and they must reach the same decision. But $C$ decides 0 and $C’$ decides 1. Contradiction — unless at least one of them was bivalent all along.

This is where the “one crash fault” is spent. It is not used to disrupt the protocol; it is used to make two inputs indistinguishable.

Move two: from any bivalent configuration, the adversary can reach another bivalent configuration.

Let $C$ be bivalent and let $m$ be any message in flight. The adversary wants to show it can delay $m$, let the protocol take some steps, and still be bivalent when $m$ is finally delivered.

Let $\mathcal{C}$ be the set of configurations reachable from $C$ without delivering $m$, and let $\mathcal{D} = { e(m)(E) : E \in \mathcal{C} }$ be what you get by delivering $m$ last. Suppose for contradiction that every configuration in $\mathcal{D}$ is univalent. Since $C$ is bivalent, $\mathcal{D}$ contains both a 0-valent and a 1-valent configuration, so somewhere in $\mathcal{C}$ there are neighbours $E_0$ and $E_1$, one step apart, whose $m$-deliveries have opposite valence.

Say $E_1 = e’(E_0)$ where $e’$ is the delivery of some message $m’$ to process $q$. Two cases:

If $m’$ goes to a different process than $m$, the two steps commute — they touch disjoint local states — so delivering $m$ then $m’$ gives the same configuration as $m’$ then $m$. But those are claimed to be 0-valent and 1-valent. Contradiction.

If $m’$ goes to the same process $q$ as $m$, consider the execution where $q$ crashes right after $E_0$ and takes no further steps. The remaining processes must still decide, by termination, reaching some configuration $A$. But $A$ is reachable both from $e(m)(E_0)$ and from $e(m)(E_1)$ by having $q$ crash, and those have opposite valence. Contradiction again.

So $\mathcal{D}$ contains a bivalent configuration. $\blacksquare$

Putting it together. Start bivalent by move one. By move two, the adversary can always delay the oldest undelivered message just long enough to land in another bivalent configuration, then deliver it. Every message is eventually delivered, so the execution is legal in the asynchronous model. And the system is bivalent at every step, so it never decides.

The adversary never drops a message, never corrupts one, and crashes at most one process. It only ever chooses the order. That is the whole attack.

What the proof is really about. Every contradiction above came from indistinguishability: two different global situations that some process cannot tell apart, forcing it to act identically in both. It is the same engine as Two Generals. The difference is that FLP needs only reordering where Two Generals needed loss, which makes FLP the stronger statement about a weaker world.

Forbids

A consensus protocol with a guaranteed termination bound in an asynchronous network. Not a slow one, not an unlikely one — no bound exists.

A perfect failure detector. If you could reliably distinguish crashed from slow, consensus would be solvable, so FLP says you cannot build one. Every health check, heartbeat, and liveness probe you have ever configured is an unreliable failure detector making a guess with a false-positive rate.

Atomic broadcast, leader election, and distributed locking with guaranteed termination, since each is equivalent to consensus. If your service discovery promises a bounded time to converge on a new leader in an asynchronous network, it is promising something no algorithm has.

Deterministic termination for blockchain consensus in an asynchronous network. Tendermint and HotStuff are explicit about this: they guarantee safety always and liveness only under partial synchrony.

Does not forbid

It does not forbid Paxos, Raft, or ZooKeeper, and “FLP proves consensus is impossible so Raft must be broken” is the single most common misreading of this result. These protocols are always safe — they never violate agreement, in any execution, including the pathological FLP one. What they give up is guaranteed liveness. Raft in an unlucky execution keeps holding split elections and never commits. That is not a bug in Raft; it is Raft being correct about a world where progress cannot be guaranteed. etcd, Consul, and ZooKeeper all ship this tradeoff and run global infrastructure on it.

It does not forbid termination with probability 1. FLP rules out deterministic protocols. Ben-Or’s randomized consensus (1983) terminates with probability 1, and randomized leader election in Raft — that jittered election timeout — is the same trick in production. The probability of never terminating is zero, but there is no bound on when, so the theorem is untouched. This is the most practically important escape and the most frequently overlooked.

It does not apply to the partially synchronous model, which is where every real system lives. Dwork, Lynch, and Stockmeyer showed in 1988 that if the network is eventually synchronous — bounds exist, you just do not know them or when they start holding — consensus becomes solvable. Real networks behave this way: mostly well-behaved, occasionally awful, eventually well-behaved again. Raft and Paxos are designed exactly for this model, and their liveness argument is “once the network settles, we make progress.”

It does not mean timeouts are wrong. A timeout is not a failure detector; it is a suspicion generator, and protocols built on it treat suspicion as a hint rather than a fact. Raft’s key design property is that a wrong suspicion costs you an election, not correctness. Understanding that timeouts affect performance and never safety is the difference between tuning a cluster and being afraid of it.

It does not apply to a synchronous system. With a known bound on message delay and clock drift, a missing message is a crash, and consensus is solvable with a simple round-based protocol. Real-time systems, avionics buses, and lockstep replication live here — at the cost of enforcing the bound physically.

It says nothing about Google Spanner being impossible. Spanner uses TrueTime, atomic clocks and GPS giving a bounded uncertainty interval, and then simply waits out the interval. That is buying partial synchrony with hardware. The commit-wait latency is the theorem’s price, paid in milliseconds.

Boundary

The exits are exactly four, and every production consensus system uses one or more:

• Randomization. Termination with probability 1. Ben-Or, and Raft’s randomized election timeouts.
• Partial synchrony. Assume bounds eventually hold. Paxos, Raft, PBFT, Tendermint. This is the mainstream answer.
• Failure detectors. Chandra and Toueg showed $\Diamond W$ — eventually weak, meaning eventually some correct process is never suspected — is the weakest detector sufficient for consensus. This is the same assumption as partial synchrony in different clothing, and it tells you the minimum you must assume.
• Buy synchrony. TrueTime, atomic clocks, dedicated networks.

What survives all four: in any given moment, you cannot know whether a silent node is dead or slow, and any action you take is a bet. The right engineering response is not to make the bet more accurate but to make being wrong survivable — fencing tokens, leases with generation numbers, idempotent operations. That is the same conclusion T061 reached from a different direction, and the agreement between them is not a coincidence.

Read next