The FLP impossibility result states that no deterministic consensus protocol can guarantee both safety and termination in a fully asynchronous system where even a single process may crash. Given that systems like Raft and Paxos are used in production to reach consensus every day, how do real systems reconcile their existence with this theoretical impossibility?
answer
- asynchronous model = no bound on message delay, no clocks
- adversary delays exactly the decisive message forever
- safety always guaranteed; only liveness/termination is sacrificed
- partial synchrony model lets timeouts work in practice
- Raft's randomized election timeouts are the practical dodge; leader election storms are FLP showing up live
basics
~20 sFLP proves that, in theory, a perfectly asynchronous network can always delay messages just enough to stall a consensus algorithm forever. Real systems dodge this by accepting that consensus might occasionally stall for a while, never violating correctness, rather than promising it will always finish quickly - and by using timeouts that work well enough in practice even though they aren't a formal guarantee.
solid answer
~60 sFLP is a statement about a specific, adversarial model: a fully asynchronous system with no bound on message delay, where a deterministic algorithm must guarantee both safety, never deciding two different values, and termination, always eventually deciding, even with a single crash failure - and it proves no such algorithm exists, because an adversary can always delay exactly the message that would let the system decide, forever. Real consensus systems like Paxos and Raft resolve this by keeping the safety guarantee absolute and unconditional, while making liveness only a best-effort, usually-fast property rather than a guaranteed one: they rely on partial synchrony, an assumption that the network is asynchronous only for bounded, unpredictable periods and eventually behaves synchronously enough for timeouts to work, plus leader election with randomized timeouts to avoid dueling candidates, and the empirical fact that indefinite worst-case delay adversaries essentially never occur in real networks. So FLP isn't violated - it's respected exactly as stated: these systems can and occasionally do stall under bad enough conditions, they just never sacrifice correctness to do so.
go deeper
Has heard of FLP by name and can restate, roughly, that perfect consensus with guaranteed speed isn't theoretically possible if the network can be arbitrarily slow.
Can state precisely what FLP proves, no deterministic algorithm guarantees both safety and termination under one crash in a fully async model, and that it's about liveness, not safety.
Can explain the partial synchrony model and how timeouts and leader election in Raft/Paxos deliberately trade unconditional liveness for practical, usually-fast progress without ever compromising safety.
Can connect FLP to observed production phenomena like leader election storms, reason about how randomization or failure-detector assumptions formally sidestep the impossibility, and use this to set realistic availability expectations when designing or evaluating a consensus-based system.
## What the theorem actually states The **FLP impossibility result**, proven by Fischer, Lynch, and Paterson in 1985, is one of the foundational negative results in distributed computing theory, and it's frequently misquoted or misunderstood, so it's worth being precise about exactly what it does and doesn't say. The theorem considers the **asynchronous message-passing model**: - a set of processes communicate only by sending messages over a network that can delay any message by an arbitrary, unbounded but finite amount of time - there is no bound on how slowly a correct process may take its next step - crucially, there are no clocks or timeouts available to distinguish a message merely being slow from the sending process having crashed Within this model, FLP proves that no deterministic algorithm can solve consensus, where all correct processes must agree on a single value, while guaranteeing both **safety**, no two processes ever deciding differently, and **termination**, every correct process eventually deciding, in the presence of even a single crash failure, and even if that faulty process crashes only once and never causes any other visible bad behavior. ## How the proof stalls the system The proof's core mechanism is an **adversarial scheduling argument**: the theorem constructs a scenario where the network scheduler, at any point where the system is one message away from being forced to decide a particular value, can instead choose to delay exactly that critical message and deliver some other message first, keeping the system in an ambiguous state indefinitely - not by crashing anyone, but simply by choosing message delivery order and timing adversarially, forever. Because the model gives processes no way to distinguish a slow message from a permanently lost one, no timeouts exist in a truly asynchronous model, an algorithm can never safely decide to give up and proceed without a process, because that process might just be slow, not actually dead - and if it decides anyway, it risks violating safety. This is precisely the **omission/crash indistinguishability** problem: in a genuinely asynchronous network, silent and slow are the same signal, so any algorithm that would eventually make progress despite one non-responding process could, symmetrically, be tricked by the adversary into making progress based on a merely-delayed message from a process that later turns out to disagree, breaking safety. ## What FLP does not say It's essential to understand what FLP does not say: - it does not say consensus is impossible in practice - it does not say Paxos or Raft are broken It says that no protocol can guarantee termination in bounded, or even unbounded-but-eventual, time under the strict asynchronous model with adversarial scheduling - it's a worst-case, adversary-controlled result about an idealized model, not a statement about the behavior of real networks under real conditions. ## The two guarantees real systems separate Real consensus systems resolve this apparent contradiction by deliberately declining to promise what FLP proves can't be promised: | Property | What Raft and Paxos actually offer | |---|---| | Safety | they retain safety as an absolute, non-negotiable guarantee, Raft and Paxos never decide two different values for the same log slot or round, full stop, under any network condition | | Liveness | but they only offer liveness conditionally: the system will make progress as long as a majority of nodes are up and the network is reasonably well-behaved | This conditional liveness is formalized as the **partial synchrony model**, introduced by Dwork, Lynch, and Stockmeyer, which assumes the network behaves asynchronously for arbitrary but finite stretches and eventually settles into a period of synchronous, bounded-delay behavior - eventually is unknown in advance, but the assumption that it happens at all is enough to let timeout-based algorithms make progress once that period arrives, sidestepping FLP's strict no-bound-ever, no-exceptions-ever adversary. ## The fingerprint FLP leaves in production Practically, this shows up as timeouts and leader election: Raft nodes use randomized election timeouts specifically so that, once the network is behaving synchronously enough, competing candidates don't perpetually split votes - a live illustration of the FLP-adjacent stalling scenario actually manifesting briefly in real clusters, for example two candidates repeatedly timing out simultaneously and re-triggering elections. Randomization breaks the symmetry with high probability, letting one candidate win a term before another can start competing. - In pathological conditions, a badly congested or partitioned network with correlated timeout collisions, a Raft cluster genuinely can stall, failing to elect a leader or commit new entries, for extended periods; this is not a bug, it is FLP being correctly respected: the system chooses to stall, preserving safety, rather than guess and risk two leaders in the same term. - Production operators observe this as leader election storms or the cluster went briefly unavailable during a network blip, and it is the direct, empirical fingerprint of FLP in systems that are otherwise considered solved consensus implementations. The theoretical takeaway engineers should carry into design decisions is: any consensus-based system inherently trades some amount of best-effort, environment-dependent availability for its safety guarantee, and no clever engineering makes that trade-off disappear - it can only be pushed to be rare and short in well-behaved networks, never eliminated in principle.
- Does FLP mean that Raft or Paxos can technically run forever without deciding anything?In the strict asynchronous model with an adversarial scheduler, yes - FLP proves no deterministic algorithm can rule this out entirely. In practice, real networks aren't adversarially worst-case forever, so partial synchrony plus timeouts and randomized leader election make indefinite stalling astronomically unlikely, though genuinely bad conditions can still cause temporary stalls such as repeated split votes.
- How does randomization in Raft's leader election timeout relate to FLP?FLP's adversary exploits the fact that a fully deterministic algorithm can be driven into a predictable, exploitable ambiguous state forever. Randomized timeouts break that determinism just enough that, once the network is behaving synchronously enough, two candidates are very unlikely to keep colliding on identical timeouts indefinitely, which is a probabilistic, not proof-level, escape from the exact worst-case scenario FLP constructs.
- Why doesn't FLP apply to systems that use randomization, like Ben-Or's randomized consensus algorithm?FLP specifically proves the impossibility for deterministic algorithms in a strictly asynchronous model; Ben-Or's algorithm sidesteps it by using randomization, guaranteeing termination only with probability 1, almost surely and eventually, rather than deterministically in bounded steps, which is a different, weaker liveness guarantee that the FLP proof's construction doesn't rule out.
It's like a jury that can only decide a verdict once every juror's note has been passed and read, in a room where a mischievous usher can choose, forever, to lose or delay exactly the one note that would tip the vote - without ever removing a juror. The jury never wrongly convicts, so safety holds, but the usher can, in theory, stall a verdict indefinitely.
saying these in an interview costs you the question
- Claims FLP means consensus is impossible in practice or that Paxos and Raft are theoretically broken
- Thinks FLP is about safety being impossible, rather than termination/liveness
- Doesn't distinguish the asynchronous model from the partial-synchrony model real systems rely on
- Believes adding more replicas or a better network fixes FLP rather than just making the practical stall probability negligible
- Can't connect leader-election timeout storms in real clusters to the FLP result