FLP Impossibility and What It Means for You

In 1985, Michael Fischer, Nancy Lynch, and Michael Paterson published a two-page result that changed distributed computing forever. The paper, “Impossibility of Distributed Consensus with One Faulty Process,” proved that no deterministic protocol can guarantee consensus in an asynchronous system if even a single process can crash.

Read that again. One faulty process. Not a majority. Not a Byzantine adversary. One crash. That is all it takes to make deterministic consensus impossible in an asynchronous system.

This result, universally known as “FLP” after its authors’ initials, won the Dijkstra Prize in 2001. It is the most important impossibility result in distributed computing, and it is widely misunderstood. People cite it to argue that consensus is impossible (it is not), that distributed systems are doomed (they are not), or that their particular hack to avoid consensus is justified (it usually is not).

Let us understand what FLP actually says, why it is true, and what it means for practical system design.

What FLP Actually Says

Theorem (FLP, 1985). There is no deterministic protocol that solves consensus in an asynchronous system with reliable channels if even one process may crash.

Let us unpack every word:

• Deterministic. The protocol’s next step is entirely determined by its current state and the messages it has received. No coin flips, no random timeouts, no external oracles.
• Consensus. Agreement, Validity, and Termination as defined in Chapter 1. All three. At the same time.
• Asynchronous. No bounds on message delivery time or processing speed. Messages are eventually delivered, but “eventually” has no upper bound.
• Reliable channels. Messages are not lost, duplicated, or corrupted. They are delivered exactly once, eventually. (This makes the result stronger — even with perfect channels, consensus is impossible.)
• One process may crash. Not “one process will crash.” The protocol must be correct in executions where up to one process crashes, and also in executions where no process crashes. The adversary gets to choose.

The result says nothing about:

• Randomized protocols (which can solve consensus in asynchronous systems)
• Partially synchronous systems (which can solve consensus deterministically)
• Synchronous systems (which trivially solve consensus)
• Safety alone (which is achievable; it is the combination of safety and liveness that is impossible)

The Proof Intuition

The full proof is only a few pages but quite dense. I will walk through the intuition, which is more valuable than memorizing the formal argument.

Configurations and Decisions

Imagine the global state of the system at any point in time: the state of every process and every message in transit. Call this a configuration.

A configuration is 0-valent if, no matter what happens from this point forward, the only possible decision value is 0. It is 1-valent if the only possible decision is 1. It is bivalent if both 0 and 1 are still possible outcomes, depending on what happens next.

Think of it like a ball on a ridge. A 0-valent configuration has the ball firmly on the left slope — it can only roll left (decide 0). A 1-valent configuration has it on the right slope. A bivalent configuration has the ball balanced on the ridge — it could go either way.

Step 1: The Initial Configuration Is Bivalent

The first claim is that there exists an initial configuration that is bivalent. This follows from the Validity property: if all processes propose 0, the decision must be 0. If all processes propose 1, the decision must be 1. Now consider a sequence of initial configurations where we change one process’s input at a time, from all-0 to all-1:

Config C0: All propose 0       -> must decide 0 (0-valent)
Config C1: One proposes 1      -> decides 0 or 1
Config C2: Two propose 1       -> decides 0 or 1
...
Config Cn: All propose 1       -> must decide 1 (1-valent)

Somewhere in this sequence, there must be adjacent configurations Ck (0-valent or bivalent) and Ck+1 (1-valent or bivalent) that differ in only one process’s input. If Ck is 0-valent and Ck+1 is 1-valent, consider what happens if the process that differs crashes immediately. The remaining processes cannot tell whether they are in Ck or Ck+1 (the crashed process’s input is the only difference, and it never communicated). So they must decide the same value in both cases. But Ck requires 0 and Ck+1 requires 1. Contradiction — unless one of them is bivalent.

Therefore, at least one initial configuration is bivalent. The system starts in a state of genuine uncertainty about what it will decide.

Step 2: You Can Always Stay Bivalent

This is the core of the proof and the most subtle part.

Suppose the system is in a bivalent configuration C. There is some message m that is the “earliest” pending message — the one that the asynchronous scheduler could choose to deliver next. Consider two scenarios:

• Scenario A: Deliver message m, reaching configuration C’.
• Scenario B: Deliver some other message first, then eventually deliver m.

The proof shows that from any bivalent configuration, there exists a sequence of steps that keeps the configuration bivalent. The adversary (the asynchronous scheduler) can always choose to delay the “deciding” message just long enough to prevent the system from committing.

Here is the argument in more detail. Suppose C is bivalent, and m is a message to process p. Let D be the set of configurations reachable from C by delivering messages other than m first (keeping m pending). Then consider delivering m to each configuration in D.

Either some configuration in D is still bivalent (and we are done — the adversary stays in the bivalent region), or all configurations in D are univalent. If all are univalent, then there must be two “adjacent” configurations in D — say D0 (which becomes 0-valent after m) and D1 (which becomes 1-valent after m) — that differ by a single step e (delivering a message to some process q).

Now there are two cases:

Case 1: p and q are different processes. The step e (message to q) and the delivery of m (message to p) are independent — they involve different processes. So delivering e then m gives the same result as delivering m then e. But delivering m to D0 gives a 0-valent configuration, and delivering e then m starting from the same configuration gives a 1-valent configuration. Since these are the same configuration (by commutativity), we have a contradiction.

Case 2: p and q are the same process. This is where the crash comes in. If p crashes before either e or m is delivered, the remaining processes cannot distinguish the two configurations (they are identical without p’s state). So from those processes’ perspective, the system must decide the same value in both cases. But one is 0-valent and the other is 1-valent. Contradiction — unless the crashed scenario is bivalent, which means the adversary can keep the system bivalent by crashing p.

// The FLP adversary's strategy (conceptual)
procedure FLP_ADVERSARY(protocol):
    start in a bivalent initial configuration C  // Step 1 guarantees this exists

    while protocol has not terminated:
        // Look at all pending messages
        // Find the one that would force a univalent configuration
        // Delay it (asynchrony permits this)
        // Deliver a different message that preserves bivalency
        // If forced, crash the critical process (we get one crash)

        m = find_deciding_message(C)
        if can_avoid(m):
            deliver some other message  // stay bivalent
        else:
            crash the process that m is addressed to
            // remaining processes are in a bivalent state

The adversary does not need to know the protocol in advance. It merely needs to examine the current configuration and choose which message to deliver next. The asynchronous model gives it this power: any message ordering is a valid execution.

Step 3: Putting It Together

We have shown:

1. The system can start in a bivalent configuration.
2. From any bivalent configuration, the adversary can keep it bivalent forever (possibly using one crash).

Therefore, the adversary can construct an execution where the system never decides. Termination is violated. QED.

The beauty of the proof is its economy: it uses only one crash, only reliable channels, and only the inherent nondeterminism of asynchronous message delivery. It identifies the fundamental problem: in an asynchronous system, you cannot force a decision because you cannot distinguish “the message is delayed” from “the sender crashed.” As long as this ambiguity exists, the adversary can exploit it to prevent progress.

What FLP Does NOT Say

FLP is frequently over-interpreted. Here is what it does not prohibit:

FLP Does Not Prohibit Safety

You can always have Agreement and Validity in an asynchronous system. A protocol that never decides satisfies both trivially (vacuously true Agreement, and no incorrect decisions). More usefully, you can design protocols that maintain safety invariants under all executions — they just might not always terminate.

Paxos, for example, never violates safety. Two different values are never committed. This holds regardless of asynchrony, partitions, crashes, or any other failure. The FLP result says that Paxos might not terminate (not make progress) in some executions. And indeed, in pathological executions with competing proposers, Paxos can livelock indefinitely. But it never produces an incorrect result.

FLP Does Not Prohibit Randomized Consensus

The FLP result applies to deterministic protocols. Ben-Or (1983) showed that randomized consensus is solvable in asynchronous systems. The trick: when the protocol reaches a point where it cannot determine the decision, flip a coin.

// Ben-Or's randomized binary consensus (simplified)
procedure BEN_OR_CONSENSUS(my_value):
    v = my_value
    round = 0

    while true:
        round = round + 1

        // Phase 1: Broadcast value
        broadcast (ROUND1, round, v) to all
        wait for N - f ROUND1 messages for this round

        if more than N/2 messages carry the same value w:
            proposal = w
        else:
            proposal = UNDECIDED

        // Phase 2: Broadcast proposal
        broadcast (ROUND2, round, proposal) to all
        wait for N - f ROUND2 messages for this round

        if more than f messages carry the same decided value w:
            v = w
            if more than 2f messages carry w:
                return w  // DECIDE
        else:
            v = random_coin_flip()  // THIS breaks FLP

The randomized coin flip means the adversary cannot predict what the process will do, so it cannot keep the system in a bivalent state forever. With probability 1, the system eventually decides. But “with probability 1” is different from “definitely” — there is no upper bound on how many rounds it might take. In expectation, binary consensus takes O(2^n) rounds with Ben-Or’s protocol (later improved to O(1) expected rounds with common coins by Rabin and others).

FLP Does Not Apply to Partially Synchronous Systems

In a partially synchronous system, the adversary cannot delay messages forever. After the (unknown) Global Stabilization Time, messages are delivered within a bounded time. This breaks the adversary’s ability to indefinitely delay deciding messages.

DLS (Dwork, Lynch, Stockmeyer, 1988) showed that consensus is solvable in the partially synchronous model. This is the theoretical basis for Paxos, PBFT, and every other practical consensus protocol.

FLP Does Not Mean “Give Up”

FLP says that no single protocol can guarantee all three consensus properties in all asynchronous executions. It does not say that consensus is impractical. It says you must give something up — but you get to choose what:

How Real Protocols Work Around FLP

Every production consensus protocol works around FLP. Here is how.

Timeouts (The Partial Synchrony Escape Hatch)

The most common approach: use timeouts to detect failures and trigger leader changes. The protocol is always safe, regardless of whether the timeouts are accurate. But the protocol only makes progress when timeouts are “reasonable” — that is, when the system is in its synchronous phase.

// Raft's approach to FLP
procedure RAFT_FOLLOWER():
    while true:
        reset election_timer to random(150ms, 300ms)

        while election_timer has not expired:
            if receive AppendEntries from leader:
                reset election_timer
                process entries
            if receive RequestVote from candidate:
                if candidate's term > my term and candidate's log is up to date:
                    vote for candidate
                    reset election_timer

        // Timer expired: leader is presumed dead
        // Start election (might be wrong — leader could just be slow)
        become candidate
        increment term
        request votes from all nodes

The election timeout is the protocol’s concession to FLP. In a purely asynchronous system, no timeout value is correct: it might expire before a message from a live leader arrives. But in a partially synchronous system, there exists a timeout value that works — we just do not know what it is. So Raft randomizes the timeout, and eventually some node’s timeout is long enough to avoid false positives while short enough to detect real failures.

The randomization also prevents livelock: if two candidates start elections simultaneously, their randomized timeouts make it likely that one will complete before the other starts, breaking the tie.

Failure Detectors (The Theoretical Escape Hatch)

Chandra and Toueg (1996) showed that consensus can be solved with an unreliable failure detector — a module that sometimes suspects a process has failed. The failure detector need not be accurate; it only needs to satisfy two properties:

• Completeness: Every crashed process is eventually suspected by every correct process.
• Eventual accuracy: There exists a time after which no correct process is suspected.

This is called an “eventually perfect” failure detector (denoted diamond-P). It captures the intuition behind timeouts: they are sometimes wrong, but eventually they stabilize.

// An eventually perfect failure detector
procedure FAILURE_DETECTOR(node_j):
    timeout = INITIAL_TIMEOUT
    suspected = false

    while true:
        send HEARTBEAT_REQUEST to node_j
        start timer(timeout)

        if receive HEARTBEAT_RESPONSE from node_j:
            suspected = false
            // Optionally decrease timeout (we are in sync)
        else if timer expires:
            suspected = true
            timeout = timeout + DELTA  // increase timeout
            // Eventually, timeout > actual_delay
            // At that point, we stop falsely suspecting node_j
            // This is when "eventual accuracy" kicks in

        report suspected status to consensus module

The failure detector abstracts the timing assumptions out of the consensus protocol. The protocol itself is purely asynchronous (and therefore cannot violate safety due to timing issues). The failure detector handles liveness by providing hints about which nodes are alive. If the hints are eventually correct, the protocol terminates. If the hints are wrong, the protocol remains safe but may not make progress.

In practice, failure detectors are timeouts — the abstraction just makes the reasoning cleaner.

Randomization (The Probabilistic Escape Hatch)

As mentioned earlier, randomized protocols sidestep FLP entirely. The adversary controls the schedule but not the coin flips. With probability 1, the protocol terminates. The expected time to termination depends on the protocol:

• Ben-Or (1983): O(2^n) expected rounds. Theoretically important but impractical.
• Rabin (1983): O(1) expected rounds using a common coin (shared randomness). Requires a trusted dealer or a distributed coin-flipping protocol.
• Cachin, Kursawe, Shoup (2000): O(1) expected rounds using threshold cryptography for the common coin. This is the basis for modern asynchronous BFT protocols.

// Common coin approach (simplified)
procedure COMMON_COIN_CONSENSUS(my_value):
    v = my_value

    for round = 1, 2, 3, ...:
        // Phase 1: Propose
        broadcast (PROPOSE, round, v)
        proposals = wait for N - f proposals

        if all proposals have the same value w:
            v = w
            broadcast (COMMIT, round, w)
            return w

        // Phase 2: Common coin
        coin = common_coin(round)  // all honest nodes get the same value
        // (implemented via threshold signatures or similar)

        if more than N/2 proposals had value w and w == coin:
            v = w  // converging
        else:
            v = coin  // reset to coin value

    // With constant probability per round, all nodes converge
    // Expected rounds to consensus: O(1)

The common coin ensures that when nodes are undecided, they all “reset” to the same random value with constant probability. Once they agree (even by accident), the agreement propagates in the next round.

Leader-Based Protocols (The Practical Approach)

Most production protocols (Paxos, Raft, Viewstamped Replication) use a stable leader to drive consensus. As long as the leader is alive and can communicate with a majority, decisions are made in two message delays (propose + acknowledge). The leader serializes proposals, eliminating the competing-proposer livelock that is the practical manifestation of FLP.

// Leader-driven consensus (common case)
procedure LEADER_CONSENSUS(value):
    // Assumes: I am the leader, no contention
    entry = create_log_entry(value, current_term)

    // Phase 1: Replicate
    send AppendEntries(entry) to all followers
    acks = wait for majority of followers to acknowledge
    // (In a 5-node cluster, need 2 follower acks)

    // Phase 2: Commit
    mark entry as committed
    apply entry to state machine
    send commitment notification to followers
    return result to client

    // Total: 2 message delays in the common case
    // No contention, no livelock, no FLP problems

The FLP adversary’s power is neutralized because there is only one proposer. The adversary cannot create competing proposals — there is nobody to compete with. The only way to trigger the FLP scenario is to crash the leader, forcing a leader election.

During leader election, FLP rears its head: competing candidates can split the vote indefinitely. Raft handles this with randomized election timeouts. Paxos handles it with random backoff. Both are probabilistic solutions, consistent with our understanding that deterministic termination is impossible.

The Practical Impact of FLP

What FLP Means for System Design

1. Your consensus protocol will sometimes stall. There will be executions where no leader is elected for multiple timeout periods. This is not a bug — it is a fundamental consequence of FLP. Design your system to tolerate brief stalls.

2. Timeouts are not correctness mechanisms. They are liveness mechanisms. If your system’s safety depends on a timeout being accurate (e.g., “if the leader has not responded in 500ms, it is definitely dead, so act accordingly”), your system has a bug. Real protocols treat timeouts as hints: “the leader might be dead, so let us try to elect a new one, but do not discard anything the old leader might have committed.”

3. Test under adversarial scheduling. The FLP adversary is a useful mental model for testing. What happens if messages are delivered in the worst possible order? What if the node that would break a tie crashes at the worst moment? Jepsen and other testing frameworks explore these schedules.

4. Embrace nondeterminism for liveness. Randomized election timeouts, randomized backoff, and randomized protocol choices are not hacks — they are theoretically motivated solutions to a fundamental impossibility. Do not try to remove the randomness in pursuit of “determinism.” Determinism is exactly what FLP says you cannot have.

A Taxonomy of FLP Workarounds in Production Systems

Every single one of these uses timeouts as the liveness mechanism and quorum voting for safety. The difference is in the details: how long the timeouts are, how they adapt, and how the system recovers from a bad timeout decision.

The FLP Mindset

FLP teaches a way of thinking about distributed systems that is more valuable than the theorem itself:

Always separate safety from liveness. If you cannot clearly identify which parts of your protocol ensure safety (and work under all conditions) versus which parts ensure liveness (and require timing assumptions), your protocol is probably wrong. Safety mechanisms should never depend on timeouts. Liveness mechanisms can depend on timeouts, randomization, or other heuristics.

Impossibility results are not limitations — they are design guides. FLP does not say “give up.” It says “you must make an explicit tradeoff.” Knowing that the tradeoff is required prevents you from spending months trying to build the impossible, and instead directs your energy toward choosing the right tradeoff for your system.

The adversary is the network. In practice, the “FLP adversary” is not a malicious actor — it is your network, your kernel scheduler, your garbage collector, and your disk controller. They conspire (unintentionally) to deliver messages in the worst possible order at the worst possible time. The fact that this happens rarely is why consensus protocols work in practice. The fact that it can happen is why the protocols need to be correct under arbitrary scheduling.

A Concrete Example: FLP in Action

Let us trace through a specific scenario where FLP manifests in a Raft cluster.

Five nodes: A, B, C, D, E. Node A is the current leader in term 1.

Time    Event
----    -----
t0      A is leader (term 1). Everything is fine.
t1      Network partition: {A, B} | {C, D, E}
t2      C, D, E time out (no heartbeats from A).
t3      C starts election for term 2. Votes for itself.
t4      D starts election for term 2. Votes for itself.
        (C and D started at the same time due to similar timeouts)
t5      C receives vote from E. C has {C, E} = 2 votes. Needs 3.
        D has {D} = 1 vote. D needs 3.
        Neither wins. Term 2 election fails.
t6      C starts election for term 3. D starts election for term 3.
        Same problem. Split vote again.
t7      This could continue indefinitely.

This is FLP manifesting as livelock. The system is safe — no two leaders are elected, no data is corrupted. But the system is unavailable: no new entries can be committed because neither the {A, B} minority nor the leaderless {C, D, E} majority can make progress.

Raft’s solution: randomized election timeouts. After the failed term 2 election, C might wait 287ms and D might wait 412ms. C starts its term 3 election first, and D has not yet timed out, so D votes for C. C wins with {C, D, E} = 3 votes. The livelock is broken probabilistically.

But notice: there is no guarantee that the randomization works on any given attempt. C and D could, by extraordinary bad luck, keep choosing nearly identical timeouts. In theory, this could continue forever. In practice, the probability decreases exponentially with each attempt, so the expected time to elect a leader is quite small. But the guarantee is probabilistic, not deterministic. FLP says it has to be.

FLP and the CAP Theorem

FLP and the CAP theorem are related but distinct results.

CAP (Brewer, 2000; Gilbert and Lynch, 2002): A distributed system can provide at most two of: Consistency, Availability, and Partition tolerance. During a partition, you must choose between C and A.

FLP (1985): Deterministic consensus is impossible in an asynchronous system with even one crash failure. This holds even without a partition.

FLP is, in a sense, stronger than CAP: FLP says you have a problem even without partitions. The mere possibility that a single node might crash is enough to prevent deterministic consensus. CAP says that partitions force a choice between consistency and availability. FLP says that asynchrony forces a choice between safety and liveness — and you cannot wait for partitions to make it happen.

In practice, both results point to the same conclusion: you cannot have everything. You must choose which properties to sacrifice and under what conditions. The protocols we study in the rest of this book are different choices in this tradeoff space.

Summary

FLP tells us that the universe imposes a tax on agreement. In an asynchronous system, you cannot deterministically guarantee that processes will agree on a value if even one of them might fail. This is not an engineering limitation — it is a mathematical fact about what distributed computation can achieve.

But FLP also tells us exactly where the impossibility lies, and therefore how to work around it:

1. Add timing assumptions (partial synchrony) and the impossibility vanishes. This is what Paxos and Raft do.
2. Add randomization and the impossibility vanishes (probabilistically). This is what Ben-Or and modern asynchronous BFT do.
3. Give up termination and keep everything else. This is what some safety-critical systems do: they would rather stall than risk an incorrect decision.

The impossibility is real. The workarounds are also real. The art of consensus protocol design is choosing the right workaround for your system’s requirements and convincing yourself (and ideally proving) that the workaround does not introduce new problems.

Every consensus protocol you will encounter in the rest of this book exists in the shadow of FLP. When you see a timeout, it is there because of FLP. When you see a randomized election, it is there because of FLP. When you see a leader-based protocol, it is structured that way to minimize the window where FLP can cause livelock. Understanding FLP is not about understanding an impossibility — it is about understanding why the possible solutions look the way they do.