FLP Impossibility and Why Real Protocols Assume Partial Synchrony

Any protocol that terminates in a bounded number of rounds has a schedule on which it fails, and the schedule requires exactly one crashed machine. That is the content of the Fischer–Lynch–Paterson result, usually shortened to FLP. It is stated as an impossibility for deterministic consensus in an asynchronous system, and it is routinely cited as the reason practical systems “assume timeouts”. Both of those summaries are accurate and both are slightly wrong in ways that lead to bad design decisions. The proof is worth understanding at the level of its mechanism, because the mechanism identifies precisely which assumption has to be weakened and what the cost of weakening it is.

What the model actually assumes

The asynchronous model gives processes no bound on message delivery delay and no bound on relative process speed. A message can take one step or a million steps; a process can be scheduled once or a thousand times between two other processes’ steps. No clock is shared, and no clock is even required to have a bounded drift rate. The only fairness condition is that every message that is sent is eventually delivered and every process takes infinitely many steps in an infinite execution.

Within that model the problem is single-value agreement with three properties. Agreement: no two processes decide different values. Validity: a decided value must be one that some process proposed, which in the binary formulation means a decision of 0 requires that someone proposed 0. Termination: every correct process eventually decides. The protocol is deterministic: the action a process takes is a function of its local state and the messages it has received, with no local source of randomness.

The result holds with a single crash failure, meaning a process that stops taking steps at some point and never resumes, and, in the binary version, with the initial values of the processes chosen adversarially. The adversary is not a network attacker in the security sense; it is a scheduler. It chooses which process takes the next step and which pending message gets delivered. Because the model imposes no timing bound, every finite schedule the adversary produces is a legal execution.

The bivalent configuration argument

The proof works with the notion of a configuration, meaning the global state: every process’s local state plus the set of messages currently in flight. A configuration is univalent if every execution extending it decides the same value, and bivalent if some extension decides 0 and another decides 1. A configuration from which no process has decided is called decided-free for the purposes of the argument.

Three lemmas do the work.

The first says that a bivalent configuration exists at the start. If all processes begin with the same initial value, validity forces a decision of that value and the configuration is univalent, so the interesting case is a mixed initial assignment. Moving one process at a time from initial value 0 to initial value 1 changes the decision from 0 to 1, and somewhere along that chain there must be a pair of adjacent configurations with different outcomes. Neither of that pair can be univalent, so both are bivalent.

The second says a bivalent configuration has a step that keeps it bivalent. Take a bivalent decided-free configuration and a step e that can be applied to it. If applying e led to a univalent configuration, the argument constructs a finite extension of the original configuration in which that step is delayed while a conflicting decision is reached, so the same configuration could also reach the opposite decision. The construction needs the delivered message to be the only one in its recipient’s queue for one step, and it needs a second process whose pending step can be reordered around the delivery. With one crashed process available to the adversary, and with a finite number of processes, such a reordering can always be arranged.

The third composes them. Start from a bivalent initial configuration. Repeatedly apply the lemma that preserves bivalence. The result is an infinite execution in which the configuration stays bivalent forever and no process ever decides. Termination fails.

The step that people remember is the “one message in the queue” trick, because it exposes why the result is fragile in a useful way. If delivery delays are bounded, then a step that is delayed cannot be delayed indefinitely, and the adversary loses the ability to keep the system bivalent by starving one message. If processes can take steps without waiting for a specific message, or if decisions can be made on partial information, the reordering argument weakens. Every escape from FLP is a specific attack on one of these two joints.

Escaping by weakening the model

The oldest escape is to assume bounds exist. In a synchronous system every message is delivered within a known delay d and every process takes a step within a known interval, so a process can use a timeout of d and know that a non-response means a crash. Consensus in a synchronous system with authenticated or unauthenticated channels is solvable in a bounded number of rounds, tolerating up to f crash failures with f + 1 rounds of message exchange for the simple oral-messages protocol. The price is the assumption: a system that is synchronous but whose bound is unknown is not usable this way, and real networks violate any fixed bound during congestion, garbage collection pauses, or virtual machine migration.

Partial synchrony, introduced by Dwork, Lynch, and Stockmeyer, is the assumption that actually matches deployed systems. Two formulations are common. In the first, there is a known bound Δ on message delay and a known bound on process speed, but the system does not have to satisfy them from the start: there is an unknown global stabilization time after which the bounds hold forever. In the second, the bounds are unknown but hold from the beginning. Either way the system is allowed to be asynchronous for an arbitrary finite period and is required to be well-behaved only eventually.

Under partial synchrony, deterministic consensus is solvable, and the protocols that solve it have a characteristic shape: they make progress during periods when the bounds happen to hold, and they remain safe but possibly stalled during periods when they do not. Safety never depends on the timing assumption; liveness does. This split is the single most important structural fact about practical consensus implementations, and it is what makes them correct even when the network misbehaves. A Raft cluster whose leader has been isolated by a partition will not elect a new leader on the minority side, and the majority side will not accept writes from the old leader; both behaviours are safety-preserving regardless of how long the partition lasts. Only the question of when the majority side finally gives up on the old leader and starts an election is timing-dependent.

The practical consequence is that the timeout value is a performance parameter with a correctness-adjacent failure mode. Too short and the system churns through elections during ordinary jitter, spending its time re-establishing leadership rather than replicating. Too long and a genuine leader failure leaves the cluster unavailable for the duration of the timeout. No value is right for all conditions, which is why implementations expose it as configuration and why operators tune it against observed latency distributions rather than picking a round number.

Escaping by weakening determinism

The second escape keeps the asynchronous model and gives up determinism. A randomized protocol can terminate with probability 1 in an asynchronous system, because the adversary’s schedule no longer determines the outcome: the processes flip coins the adversary cannot predict, and with probability 1 the coins eventually break the symmetry that the bivalent argument relies on.

Ben-Or’s protocol is the clean example. Each round has two phases. In the first, every process broadcasts its current preference and adopts the value held by a clear majority of the messages it receives, or a special bottom value if it sees no clear majority. In the second phase, processes broadcast again: a process that sees enough support for one value decides it, a process that sees enough support for the bottom value adopts bottom, and otherwise it adopts a value chosen by a local coin flip. The thresholds are set so that if any correct process decides a value, every correct process adopts that value in the same round, which is what keeps the protocol safe despite the coins. The randomization in the second phase is what prevents the adversary from holding the system in a bivalent state, because the adversary cannot arrange for all processes to keep flipping the same way.

The cost is termination time. Randomized binary consensus terminates in an expected constant number of rounds, but the distribution has a long tail, and the constant is not small. The protocols are also not what most systems run, because they need many more messages per round than a leader-based protocol and they do not naturally batch operations. Randomized consensus shows up in systems that genuinely cannot assume any timing bound, and in the theory of what is achievable rather than in the common replication library.

There is a third escape that is often presented as a fourth: failure detectors. An eventually strong failure detector, which eventually suspects every crashed process and eventually stops suspecting every live one, is sufficient for consensus in an asynchronous system with a majority of correct processes. This is not really a contradiction of FLP, because the failure detector is an additional oracle that supplies the timing information the model otherwise lacks. It is a useful way to state the requirement: consensus needs a source of information about which processes are down, and any such source is either a timeout, a randomized schedule, or an external service. The heartbeat and suspicion machinery that real systems use is an implementation of a failure detector, with all the imperfection that implies.

What the result does not say

Several misreadings circulate widely enough to be worth naming.

FLP does not say consensus is impossible in practice. It says no deterministic protocol terminates in every asynchronous execution. A protocol that terminates in every execution where the network eventually behaves is entirely consistent with the theorem, and that is exactly what deployed systems provide. The theorem is a statement about the worst-case schedule, and the worst case is not the common case.

FLP does not require a majority of faulty processes. The result holds with one crash failure in a system of any size, including two processes. This is the part that surprises people who have internalized “tolerates f failures with 2f+1 nodes”. The quorum arithmetic is about how many failures can be tolerated while preserving safety; FLP is about whether termination can be guaranteed at all. The two numbers are unrelated.

FLP does not apply to protocols that never claim bounded termination. A protocol that always eventually decides when the network stabilizes, and that is safe under any schedule, has not violated the theorem. What it has done is decline to promise anything about the asynchronous period, which is the honest position.

The result also does not forbid all forms of progress during asynchrony. A protocol may decide some values quickly and stall on others; a system may commit some operations during a partition if the partition happens to leave a quorum on one side. What FLP forbids is a guarantee that every proposal is decided within a bounded time regardless of the schedule.

The assumption is the design

The useful way to read FLP is as a map of the design space. Every consensus protocol chooses where to put its timing assumption: a bounded delay in the message layer, an eventually-stable bound with a stabilization time, a failure detector that supplies suspicion, or randomness that makes the adversary’s choices irrelevant. The protocol’s safety argument holds without the assumption; its liveness argument requires it, and the requirement is always stated in terms of eventual behaviour rather than a bound that must hold from the first message.

That structure is visible in every practical design. The leader election rules in Raft’s term mechanism are safe under any schedule and live only once a majority can hear each other. The promise mechanism in Paxos preserves safety across arbitrary delays and completes a round only when a quorum responds. Reading a protocol’s documentation with the question “which part of this depends on the timeout” answers most questions about how it behaves during an outage, and that question is the practical residue of the impossibility result.