The FLP Impossibility Result: Why No Distributed Algorithm Can Guarantee Consensus in Asynchronous Networks
The 1985 Fischer, Lynch, and Paterson proof underneath every eventually consistent design decision, explained without the formal notation.
Somewhere underneath every distributed system you’ve worked with sits an uncomfortable fact that most engineers never have to think about directly. If a set of machines needs to agree on something, a value to commit, a leader to elect, a transaction to finalize, and even one of those machines might crash without warning, then no algorithm running over a genuinely asynchronous network can guarantee that agreement will ever be reached. Not “it’s hard.” Not “it’s slow.” Impossible, in the strict mathematical sense, and proven that way in 1985 by Michael Fischer, Nancy Lynch, and Michael Paterson in a paper that went on to win the Dijkstra Prize as one of the most influential results in the field. This is the proof underneath that fact, told the way you’d explain it to a colleague over coffee rather than the way it reads in the original journal article.
The Problem Consensus Is Actually Solving
Picture five servers deciding whether to commit or roll back a transaction. Each one starts with its own opinion, commit or roll back, based on whatever it observed locally. Consensus means getting all five to settle on the same final answer, and it comes with three conditions that sound almost too obvious to write down. The answer they settle on has to be one of the values somebody actually proposed, not something invented out of thin air. Every server that hasn’t crashed has to eventually reach a decision, not wait forever. And once a server decides, it can’t later change its mind. Put those three together and you have consensus, and solving it correctly, every time, no exceptions, turns out to be the hard part.
Why Asynchrony Breaks Something Synchrony Doesn’t
If you’re willing to assume the network behaves, messages arrive within some known bound and every process takes its turn on a predictable clock, consensus is entirely solvable, even when processes can crash. The trouble starts the moment you drop that assumption and allow the network to be genuinely asynchronous: no bound on how long a message can take, no bound on how slowly a process might run. In that world, a process that has crashed and a process that is simply taking its time look exactly the same from everyone else’s point of view. There is no message you can send, no timer you can set, that tells you which one you’re dealing with. And that single piece of uncertainty is enough to make guaranteed termination impossible.
| Timing Model | Message Delay Assumption | Where It Shows Up |
|---|---|---|
| Synchronous | Known upper bound on delivery time | Tightly clocked hardware buses, some real-time systems |
| Partially synchronous | A bound exists but isn’t known, or holds only eventually | Most production consensus protocols, including Paxos and Raft |
| Asynchronous | No bound at all, of any kind | The model FLP proves its result in |
That middle row matters more than it looks. The partially synchronous model was formalized a few years after FLP by Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer, and it’s closer to how real networks actually behave: your packets usually arrive within a few milliseconds, but nothing enforces that as a hard guarantee. Every consensus protocol you’ve actually deployed, Paxos, Raft, anything built on a failure detector or a leader election timeout, is quietly leaning on that “usually” to get around a proof that says pure asynchrony leaves you with no such option.
The Proof Without the Notation
The heart of the FLP argument is a concept called bivalency, and it’s more intuitive than the name suggests. Start the system in some initial configuration where the eventual decision, if the system ever reaches one, could still go either way depending on what happens next. Call that configuration bivalent. The proof’s key move is showing that from any bivalent configuration, there’s always at least one more step the system can take that leads to another bivalent configuration, one where the outcome is still genuinely undecided.
Now imagine an adversary who controls exactly one thing: the order in which messages get delivered. That adversary doesn’t need to corrupt anything or fake a crash. All it has to do is notice which message, if delivered next, would finally tip the system toward a decision, and quietly delay that one message a little longer while letting harmless ones through. Because the proof guarantees there’s always another bivalent configuration reachable, the adversary can repeat this trick forever. The system keeps taking steps, keeps looking busy, and never actually decides. That’s the whole result: not that consensus is unreachable in any particular run, but that no algorithm can rule out the possibility of a run exactly like this one, stretching on indefinitely, with a single slow message being all it takes.
“Every protocol for this problem has the possibility of nontermination, even with only one faulty process.” That’s how Fischer, Lynch, and Paterson put it in their own closing lines, and it’s worth sitting with, since the failure they’re describing is a crash, the mildest possible kind of fault a process can suffer.
What FLP Does Not Say
It’s easy to walk away from this thinking distributed consensus is a lost cause, and that reading goes further than the proof actually supports. FLP says nothing about safety, a well built protocol can still guarantee it will never decide on the wrong value. What it rules out is a guarantee of termination in the worst case, under an adversary with unlimited patience and a network with no timing guarantees whatsoever. Real networks aren’t adversaries. Real systems add exactly the kind of assumption FLP proves you need: a timeout that treats silence as failure, a leader election that breaks ties using randomness, a failure detector that’s allowed to be wrong occasionally as long as it’s eventually right. Each of those is a deliberate step away from pure asynchrony, and each one is precisely what lets Paxos, Raft, and their relatives terminate in practice even though the pure theoretical model they’re built on top of says termination can’t be guaranteed.
The Line to Eventually Consistent
This is where the proof stops being a piece of 1985 theory and starts explaining decisions made in architecture reviews forty years later. If guaranteeing consensus requires giving something up, timing assumptions, a coordinator, tolerance for occasional wrong guesses about failure, then a system that can’t afford those costs has a real alternative: stop insisting on immediate agreement at all. Let replicas diverge briefly. Let a write land on one node before every other node has heard about it. Reconcile the differences later, through version vectors, conflict free replicated data types, or a simple last write wins rule, instead of paying for a consensus round on every operation. That’s not a shortcut engineers invented because consensus was inconvenient. It’s the same tradeoff FLP describes, just made explicitly instead of accidentally, and it’s a large part of why so many systems that could have reached for a consensus protocol reached for eventual consistency instead.
What We Learned
The FLP result doesn’t say distributed systems are broken, and it doesn’t say consensus is unachievable. It says something narrower and, in its way, more useful: in a network with no timing guarantees at all, no algorithm can promise that agreement will be reached in every possible execution, because a single well timed slow message is enough to keep the outcome open forever. Every practical consensus protocol in production today works by quietly rejecting that pure asynchronous model, leaning instead on timeouts, partial synchrony, or randomness to get the guarantee FLP proves is otherwise out of reach. And every system that instead chose eventual consistency made, whether the team framed it this way or not, the other available choice: give up on immediate agreement rather than pay for the assumptions consensus requires. Both are legitimate answers to the same forty year old proof. Neither one is free.
