Why Consensus Is Impossible: FLP and Partial Synchrony
On this page
Learning Objective
Explain the FLP impossibility result conceptually - that no deterministic algorithm in a fully asynchronous model can guarantee both safety and termination with even one crash-faulty process - and describe the three practical escape hatches real systems use: partial synchrony, unreliable failure detectors, and randomisation.
Concept Explanation
In 1985, Fischer, Lynch, and Paterson published a result that permanently changed how the field talks about consensus. Their paper, "Impossibility of Distributed Consensus with One Faulty Process", proves that in a fully asynchronous system, no deterministic algorithm can guarantee it will reach consensus, even if at most one process may crash and even if that crash is the only fault in the entire system. This is not a statement that consensus is hard, or that nobody has found a good enough algorithm yet. It is a proof that no such algorithm exists and none will ever be found, in that model.
Everything hinges on what "fully asynchronous" means, and it is a much stronger assumption than "the network is slow". In the asynchronous model there is no upper bound on how long a message may take to arrive, and no bound on how long a process may take to execute a step. Messages are eventually delivered, but "eventually" carries no deadline at all. A message may take a microsecond or a decade. There are no synchronised clocks, and crucially there are no timeouts, because a timeout is only meaningful if exceeding it tells you something, and in a model with no bound on message delay, exceeding any threshold whatsoever tells you precisely nothing.
That single consequence is the whole intuition behind the proof, and you do not need the formal argument to feel it. A process that has heard nothing from another process cannot distinguish between two situations: the other process has crashed, or the other process is alive and its reply is merely slow. These two cases are observationally identical from the outside, forever. Now consider what an algorithm must do when it finds itself in that state. If it waits, and the process really has crashed, it waits forever and violates termination. If it proceeds without the missing process, and that process was actually alive and had already decided something different, it risks violating agreement. Every deterministic algorithm must resolve this dilemma one way or the other, and an adversarial scheduler - which the asynchronous model permits, since it puts no constraints at all on timing - can always keep the system in a state where the pending decision could still go either way. FLP formalises this as the existence of a perpetually bivalent configuration: a state from which both outcomes remain reachable, and which the scheduler can always extend to another such state.
So how does etcd exist? How does ZooKeeper run in production at enormous scale with a decade of uptime behind it? The answer is that real systems do not live in the fully asynchronous model, and none of them claim to. They escape via one of three well-understood routes. The most common by far is partial synchrony, formalised by Dwork, Lynch, and Stockmeyer in 1988: the system may behave asynchronously for arbitrary stretches, but eventually enters a period during which message delay and processing time are bounded. Raft and Paxos both live here. They are always safe, in every network condition including the fully asynchronous worst case, and they guarantee progress only during those good periods. A Raft cluster under a pathological network does not corrupt itself; it simply churns through elections without committing anything, which is FLP showing up in your monitoring dashboard as a liveness failure rather than as data loss.
The other two escapes are worth knowing. Chandra and Toueg showed in 1996 that consensus becomes solvable if you add an unreliable failure detector with certain properties, notably the eventually weak detector known as diamond-W, which may make mistakes for an unbounded period but must eventually stop suspecting some correct process. In practice, a timeout-based heartbeat is exactly such a detector: it is allowed to be wrong, and the algorithm is built to stay safe when it is. The third escape is randomisation, introduced by Ben-Or in 1983: a randomised algorithm can guarantee termination with probability one, sidestepping the proof because FLP only constrains deterministic algorithms. An adversarial scheduler can defeat any fixed strategy, but it cannot reliably defeat a coin flip. Raft uses a weak form of this idea in its randomised election timeouts, which break the symmetry that would otherwise let two candidates split the vote indefinitely.
| Model or Escape | Timing Assumption | Consensus Solvable? | Used By |
|---|---|---|---|
| Synchronous | Known upper bound on message delay and process speed | Yes, and easily | Essentially nothing over a real network |
| Fully asynchronous | No bound whatsoever on delay | No, by FLP, for any deterministic algorithm | A theoretical baseline, not a deployment target |
| Partial synchrony | Asynchronous for arbitrary periods, eventually bounded | Yes, with safety always and liveness during good periods | Paxos, Raft, ZAB, etcd, ZooKeeper, Consul |
| Unreliable failure detector | A detector that may err but eventually stops suspecting a correct process | Yes, with the detector supplying the missing information | Heartbeat and timeout mechanisms in every real implementation |
| Randomisation | Asynchronous, but the algorithm may flip coins | Yes, with probability one rather than with certainty | Ben-Or, and many Byzantine-fault-tolerant protocols |
Worked Example: A Timeout Being Wrong, and Why Safety Survives It
The productive way to read FLP is as a design constraint rather than a curiosity: it tells you that your failure detector will be wrong, so the algorithm must remain correct when it is. Walking through a false suspicion in a Raft cluster shows exactly how that requirement is met.
# 5-node Raft cluster. Node A is leader for term 7.
# Election timeout is randomised in the range 150-300ms.
t=0ms A sends heartbeats to B, C, D, E. All good.
t=40ms A experiences a 400ms garbage-collection pause. A is NOT crashed.
It is alive, it still holds leadership for term 7, and it will
resume shortly. No node can tell this from a crash.
t=210ms B's randomised election timeout fires first. B has heard nothing
for 210ms. Its failure detector is WRONG - A is fine - but the
detector is allowed to be wrong.
B increments to term 8 and requests votes from C, D, E.
t=225ms C, D, E each see term 8 > their term 7, and each grants a vote
after checking B's log is at least as up to date as their own.
B has 3 of 5 votes = a majority. B is leader for term 8.
t=440ms A wakes from its GC pause and cheerfully sends a term-7
AppendEntries to C.
C replies: {term: 8, success: false}
A sees a term higher than its own and immediately steps down to
follower. It does not argue. It does not retry. The rule is
unconditional.
# Safety was never at risk, even though the failure detector was wrong:
# - B could only win by collecting a MAJORITY, which A could not
# simultaneously hold.
# - Any node granting B a vote in term 8 will refuse A's term-7 requests.
# - Uncommitted entries A had appended but not replicated to a majority
# are simply overwritten by B's log. They were never acknowledged as
# committed, so no client was ever told they were durable.
#
# What the wrong timeout cost: one unnecessary election, a few hundred
# milliseconds of unavailability. That is FLP's bill, paid in liveness.Real-World Examples
- The Raft paper by Diego Ongaro and John Ousterhout (USENIX ATC 2014) is explicit that Raft guarantees safety unconditionally but guarantees liveness only under a timing assumption, stating that the system makes progress when broadcast time is much less than the election timeout, which in turn is much less than mean time between failures. That inequality is the partial-synchrony escape from FLP written as an operational tuning rule, and it is why etcd ships with a 100ms heartbeat interval against a 1000ms election timeout by default and warns operators specifically against deploying across high-latency links without adjusting both.
- Google's "Paxos Made Live" paper (2007), describing the Chubby implementation, reports that the engineers had to add a mechanism to prevent repeated leader turnover under load, because a leader that was merely slow would be suspected and replaced, and the replacement would then be suspected in turn, producing a cluster that spent its time electing rather than committing. This is FLP appearing directly in a production system: no safety violation ever occurred, only a liveness collapse driven by a failure detector that could not tell slow from dead.
Review Questions & Answers
FLP applies specifically to the fully asynchronous model, where message delay has no upper bound at all and timeouts therefore convey no information. etcd assumes partial synchrony instead: the network may misbehave arbitrarily for arbitrary periods, but eventually there are stretches during which messages arrive within some bound. Under that assumption etcd is always safe and makes progress during the good stretches. It does not violate FLP, it declines to live in FLP's model, and it pays for that by being genuinely unable to make progress during the bad stretches.
The proof works by constructing an adversarial schedule that keeps the system in a state where the decision could still go either way, extending that state indefinitely. Against a deterministic algorithm the adversary can compute exactly what each process will do next and choose message delivery order to maintain the indecision. Against a randomised algorithm it cannot, because the next step depends on a coin flip it does not control. This is why Ben-Or's randomised protocol achieves termination with probability one: the probability of the adversary winning every coin flip forever is zero, even though no finite bound on decision time can be given.
It is a liveness failure, exactly the outcome FLP predicts under poor timing conditions, and it confirms the safety properties are holding: the cluster would rather commit nothing than commit inconsistently. The fix is therefore about timing rather than about correctness - investigate why heartbeats are not arriving within the election timeout, whether that is network latency, packet loss, disk fsync latency stalling the leader, garbage collection pauses, or CPU starvation, and either fix the underlying cause or widen the election timeout so the partial-synchrony assumption holds again. Changing the algorithm is not on the table; the algorithm is doing its job.
An unreliable failure detector is a module that reports which processes it suspects have failed, and which is explicitly permitted to be wrong - to suspect a live process, or to fail to suspect a dead one - for an unbounded period, provided it eventually stops permanently suspecting some correct process. Being allowed to make mistakes is essential because a perfect failure detector is impossible in an asynchronous system: distinguishing crashed from slow requires timing information the model does not provide. Chandra and Toueg's contribution was showing that consensus is solvable with a detector this weak, which is what makes ordinary heartbeat timeouts a theoretically sound foundation rather than a pragmatic hack.
In the asynchronous model there is no upper bound on message delay, so the absence of a heartbeat after any interval - one second or one year - is equally consistent with the peer having crashed and with the peer being alive and its heartbeat still in flight. A timeout is only informative when exceeding it rules something out, and with no bound on delay nothing is ever ruled out. Partial synchrony restores the timeout's usefulness by asserting that a bound does eventually exist, which is precisely why every real deployment cares so much about tuning that timeout against observed network latency.