On this page

FLP Impossibility

In 1985, Fischer, Lynch, and Paterson published a short proof that shook the foundations of distributed systems theory. It proved something deeply uncomfortable: in a purely asynchronous distributed system, no deterministic algorithm can solve consensus if even a single process might fail.

Correction

Earlier versions of this page called it a "two-page proof". The journal paper ("Impossibility of Distributed Consensus with One Faulty Process", Journal of the ACM 32(2), April 1985) runs about nine pages, and a preliminary version appeared at PODS in 1983. The core argument is famously compact, which is where the "short proof" reputation comes from.

This is not a statement about bad implementations. It's a mathematical proof about what is possible. Every consensus protocol you've ever used — Raft, Paxos, ZooKeeper's ZAB — exists in spite of this theorem, not ignorant of it.

The result is usually called FLP after its authors, Michael Fischer, Nancy Lynch and Michael Paterson. It received the PODC Influential Paper Award in 2001 (the award was later renamed the Dijkstra Prize), and it remains the single most important negative result in the field. Nearly every later paper on consensus starts by saying which FLP assumption it relaxes.

This page walks through:

  1. what problem FLP is about and the exact model it assumes,
  2. the proof itself, at a level where you could reconstruct it on a whiteboard,
  3. what it does and does not forbid,
  4. the three classical escapes — partial synchrony, randomization and failure detectors,
  5. how Raft and Paxos live with it in production.

If you want the model vocabulary (asynchronous, partially synchronous, crash-stop, crash-recovery, Byzantine) laid out on its own first, read System Models.


What is Consensus?

Consensus requires all non-faulty processes to agree on a single value, where:

  1. Validity — The agreed value must have been proposed by some process
  2. Agreement — No two non-faulty processes decide different values
  3. Termination — Every non-faulty process eventually decides

Sounds simple. FLP proves it's impossible under one specific model.

The version FLP actually proves impossible

FLP is stronger than the textbook statement above, because the paper uses weaker requirements than those three properties. Making the problem easier and still proving it impossible makes the result harder to escape.

PropertyTextbook consensusWhat FLP requires
Input valuesAny valueA single bit, 0 or 1
ValidityDecided value was proposed by someoneNon-triviality: both 0 and 1 are possible outcomes for some initial configuration
AgreementNo two correct processes decide differentlySame
TerminationEvery correct process decidesSome process decides
FaultsUp to crashesAt most one crash, and the protocol only has to work in runs where at most one process crashes

So FLP shows that even binary consensus, where only one process needs to decide, where the protocol only needs to cope with a single crash, and where the validity condition is as weak as it can be while still excluding the trivial "always decide 0" protocol, has no deterministic solution in the asynchronous model.


The Asynchronous Model

The theorem applies specifically to the asynchronous message-passing model:

  • Processes communicate by sending messages
  • Messages are eventually delivered but with no upper bound on delay
  • Processes run at arbitrary speeds — no shared clock
  • A process can crash-stop (halt silently, never restart)
  • You cannot distinguish a crashed process from a very slow one

This last point is the crux. In a real network, a 10-second silence from a node could mean:

  • The node crashed
  • The network partition
  • The node is just very slow under load

You cannot tell. This is the asymmetry FLP exploits.

The model, precisely

The paper's model is worth stating carefully, because every escape works by changing exactly one line of it.

  • Processes. There are processes. Each is a deterministic state machine with an input register (0 or 1), an output register that starts empty and can be written once (writing it is "deciding"), and arbitrary internal state.
  • The message buffer. All messages in flight live in one global multiset. send(p, m) puts the message into the buffer. receive(p) either removes some message addressed to and returns it, or returns the null marker . The buffer is allowed to return even when messages are waiting, which is how arbitrary delay is modelled.
  • Steps. A step is one process doing: receive (possibly ), update its state deterministically, send a finite set of messages. A step is identified by the pair , called an event.
  • Configurations. A configuration is the internal state of every process plus the contents of the message buffer. Applying event to gives a new configuration .
  • Schedules and runs. A schedule is a sequence of events. A run is the sequence of configurations it produces.
  • Faults. A process is faulty in a run if it takes only finitely many steps. Crashing is the only kind of fault. No lying, no corruption.
  • Admissible runs. A run is admissible if at most one process is faulty, and every message sent to a non-faulty process is eventually received. This is the fairness condition: the network can delay, but it cannot lose messages to correct processes forever.
  • Deciding runs. A run is deciding if some process writes its output register.

A protocol is totally correct despite one fault if every admissible run is a deciding run, no configuration ever has two different decision values, and both decision values are reachable from some initial configuration.

FLP's theorem: no consensus protocol is totally correct despite one fault.

Indistinguishability, the core intuition

Here is why the right-hand column is so damaging. Consider a process waiting for a message from :

sequenceDiagram
    participant A
    participant B
    participant Net as "Network"
    Note over A,B: World 1 — B has crashed
    B-xNet: crash, never sends
    A->>A: wait... nothing arrives
    Note over A,B: World 2 — B is alive but slow
    B->>Net: vote 1
    Net-->>Net: message held for an arbitrarily long time
    A->>A: wait... nothing arrives

Up to any finite point in time, 's view in both worlds is identical: it has received nothing from . If 's protocol says "wait for ", then in World 1 it waits forever and violates termination. If the protocol says "after a while, proceed without ", then in World 2 might have already contributed to a decision elsewhere, and proceeding without it can cause disagreement. The proof turns this dilemma into a rigorous argument.


The Proof Intuition

The full proof uses a bivalent configuration argument. Here's the intuition without the formalism:

Setup: Imagine a consensus algorithm trying to decide 0 or 1. The system starts in some initial configuration.

Bivalent vs Univalent:

  • A configuration is univalent if the outcome is already determined (0-valent or 1-valent)
  • A configuration is bivalent if the outcome depends on future message ordering

The argument:

  1. There always exists a bivalent initial configuration (some starting states are undecided)
  2. From any bivalent configuration, you can always find a "critical step" where delaying one message keeps the system bivalent
  3. A crashed process is indistinguishable from a delayed one
  4. Therefore: an adversary who controls message delivery can always delay the one message that would force a decision — keeping the system bivalent forever
  5. The algorithm never terminates

The adversary doesn't need to do anything malicious. It just needs to delay one message indefinitely — something the model explicitly allows.


The Proof, Step by Step

The intuition above compresses three lemmas. This section unpacks them. You do not need to memorise the proof, but walking through it once makes every later escape obvious, because you can see exactly which step each escape breaks.

Valence, defined carefully

For a configuration , look at every configuration reachable from it by some schedule, and at the decision values that appear in them.

  • is 0-valent if every reachable decision is 0.
  • is 1-valent if every reachable decision is 1.
  • is bivalent if both 0 and 1 are reachable.

A univalent configuration is one where the outcome is already fixed, even if no process knows it yet. A bivalent one is still genuinely open. A decision can only be written in a univalent configuration (once someone writes 0, only 0 is reachable), so a protocol that stays bivalent forever never decides.

Lemma 1: steps by different processes commute

Suppose from configuration two schedules and involve disjoint sets of processes. Then applying then gives the same configuration as then .

This is close to obvious: a step only changes the state of the process taking it and adds messages to the buffer. If only touches processes and only touches , neither can see the other's effects, so order doesn't matter.

flowchart LR
    C["C"] -->|"σ1 (p, q only)"| C1["σ1(C)"]
    C -->|"σ2 (r only)"| C2["σ2(C)"]
    C1 -->|"σ2"| D["same configuration"]
    C2 -->|"σ1"| D

This "diamond" property is the only algebra the proof needs.

Lemma 2: some initial configuration is bivalent

Line up the initial configurations so that neighbours differ in the input of exactly one process. With three processes:

Config
000
100
110
111

Suppose, for contradiction, that every initial configuration is univalent. By non-triviality, some initial configuration is 0-valent and some is 1-valent. In fact, any sensible protocol has 0-valent and 1-valent, but the argument only needs one of each. Walk along the chain: somewhere there are adjacent configurations (0-valent) and (1-valent) that differ only in the input of a single process, call it .

Now take an admissible run from in which crashes at the very start and takes no steps. Since at most one fault is allowed and the protocol is correct, the other processes must still decide, say value . Run the same schedule from . Process 's input is different, but never takes a step, so nobody can ever observe its input. Every other process sees exactly the same messages and reaches exactly the same decision .

But is 0-valent, so , and is 1-valent, so . Contradiction. Therefore some initial configuration is bivalent.

Notice what made this work: one crash was enough to hide the difference between two inputs. That is the indistinguishability idea from the sequence diagram, used formally.

Lemma 3: from any bivalent configuration, any pending step can be taken while staying bivalent

This is the heart of the proof and contains the "critical step".

Let be bivalent and let be any event applicable to (message is waiting for , or ). Let be the set of configurations reachable from without applying , and let be what you get by applying at some point. Lemma 3 says contains a bivalent configuration.

In other words: the adversary may postpone as long as it likes, but it must eventually deliver it (fairness). Lemma 3 says it can always find a moment to deliver such that the result is still bivalent.

The proof is by contradiction. Assume every configuration in is univalent.

Step A: contains both a 0-valent and a 1-valent configuration. Because is bivalent, there is some reachable configuration that has decided 0. If (reached without ), then and it must be 0-valent (it descends from a 0-decision). If was reached by applying along the way, then the configuration right after applying is in and can still reach 0, so since it is univalent it is 0-valent. The same reasoning gives a 1-valent member of .

Step B: find the critical step. Since has both valences, there must be two neighbouring configurations in , and , where for a single event , such that is 0-valent and is 1-valent (or the other way round). The step is the critical step: whether it happens before or after flips the outcome.

Step C: case analysis on who takes the critical step.

Case 1: . The two events involve different processes, so by Lemma 1 they commute:

The left side is a successor of , which is 0-valent, so it must be 0-valent. The right side is , which is 1-valent. A configuration cannot be both. Contradiction.

flowchart TB
    C0["C0"] -->|"e' by p'"| C1["C1"]
    C0 -->|"e by p"| D0["e(C0): 0-valent"]
    C1 -->|"e by p"| D1["e(C1): 1-valent"]
    D0 -->|"e' by p'"| D1
    D1 --> X["same config is 0-valent and 1-valent"]

Case 2: . Both events are steps by the same process, so they don't commute. Now use the crash. Consider a finite schedule from in which takes no steps and some process decides. This must exist: the protocol must tolerate crashing, so the others must be able to decide without it. Call the result . Since does not involve , it commutes with both and :

But is a configuration in which a decision has already been reached by processes other than , so is univalent. It has a 0-valent successor and a 1-valent successor. Contradiction.

So both cases fail, and must contain a bivalent configuration.

The essence of Case 2

In Case 2, the critical decision rests entirely with process : whether sees before or after determines the outcome. The other processes cannot wait for to tell them which happened, because might have crashed. And if they go ahead without , they reach a decision that 's choice was supposed to determine. That is the formal version of "you can't tell slow from crashed".

Putting the lemmas together: the infinite bivalent run

Now build a run that never decides.

  1. Start from a bivalent initial configuration (Lemma 2).
  2. Keep a queue of processes, in round-robin order. Take the process at the front, and let be the oldest message waiting for (or if none).
  3. By Lemma 3, there is a schedule ending in event that leads to a bivalent configuration. Apply it.
  4. Move to the back of the queue and repeat forever.

Every process takes infinitely many steps (no process is faulty, which is even better than the one allowed). Every message is eventually delivered, because the oldest waiting message for each process is delivered on its turn. So the run is admissible. Yet every configuration in it is bivalent, so no process ever decides. The protocol is not totally correct.

sequenceDiagram
    participant Adv as "Adversary (scheduler)"
    participant P1 as "p1"
    participant P2 as "p2"
    participant P3 as "p3"
    Note over Adv: config is bivalent
    Adv->>P1: deliver oldest message, timed per Lemma 3
    Note over Adv: still bivalent
    Adv->>P2: deliver oldest message, timed per Lemma 3
    Note over Adv: still bivalent
    Adv->>P3: deliver oldest message, timed per Lemma 3
    Note over Adv: still bivalent, repeat forever

The striking part: no process actually crashes in the bad run. The possibility of a crash is what forces the protocol to be unable to wait, and the adversary only needs to exploit message timing. This is why FLP is sometimes summarised as "the protocol may have to run forever even if nothing fails".


What FLP Actually Says

ClaimCorrect?
"You can never build a consensus algorithm"❌ No
"You can never build a deterministic consensus algorithm in a purely async model with any failures"✅ Yes
"Raft and Paxos violate FLP"❌ No — they escape it
"FLP means distributed systems are broken"❌ No — it means you must accept trade-offs

What it does and doesn't forbid

FLP is precise, which means its boundary is precise too. This table is worth internalising.

GoalAllowed by FLP?Why
Never deciding two different values (safety) in an asynchronous network✅ YesFLP only attacks termination. Paxos and Raft are safe under arbitrary asynchrony.
Always terminating in a fully asynchronous network, deterministically, with one possible crash❌ NoThat is exactly the theorem
Terminating in every run where the network behaves well "for long enough"✅ YesPartial synchrony (DLS)
Terminating with probability 1 in a fully asynchronous network✅ YesRandomized protocols (Ben-Or) — the non-terminating runs have probability 0
Terminating in a fully asynchronous network given an eventually accurate failure detector✅ YesChandra-Toueg
Consensus in a synchronous network with crashes✅ YesNeeds rounds for crashes, and that is a lower bound
Consensus in the asynchronous model with zero faults✅ YesWait for everyone
Atomic broadcast, terminating, deterministic, asynchronous, one crash❌ NoEquivalent to consensus
Non-blocking atomic commit under the same conditions❌ NoAlso implies the impossibility, so 2PC blocks and 3PC needs timing assumptions
A wait-free consensus object from read/write registers in shared memory❌ NoThe shared-memory analogue (Loui and Abu-Amara 1987, Herlihy 1991)
-set agreement (decide at most distinct values) with crashes, asynchronous❌ NoGeneralisation proved in 1993 by Borowsky-Gafni, Herlihy-Shavit and Saks-Zaharoglou
Eventual consistency without agreement (CRDTs, gossip)✅ YesNot consensus. Replicas converge without ever deciding a single value.

Three takeaways:

  1. Safety is always available. No amount of asynchrony forces a well-designed protocol to disagree. Asynchrony only threatens progress.
  2. The bad runs are rare in practice. The adversary in the proof has perfect knowledge of the protocol state and perfectly controls timing. Real networks are noisy, not malicious, so they rarely sustain the exact schedule needed. That is why randomized timeouts work so well.
  3. The impossibility is about guarantees, not typical behaviour. "The protocol usually terminates in milliseconds" and "the protocol can be kept from terminating forever" are both true of Raft.

How Real Systems Escape FLP

Since the theorem is a proof about a specific model, real systems escape it by stepping outside the model:

1. Timeouts (Partial Synchrony)

Raft and Paxos use election timeouts. A candidate waits a random duration — if no heartbeat, assume the leader crashed and start an election.

This is not purely asynchronous. It assumes messages arrive within some bound. The system is partially synchronous — and FLP doesn't apply.

More precisely, these protocols are built so that safety never depends on the bound: if the network is slower than the timeout, the worst outcome is an unnecessary election, never two different committed values. Only liveness depends on the network eventually respecting the bound. FLP still applies in the sense that there are runs where they never make progress; partial synchrony simply rules those runs out as "not the environment we promised to work in".

FLP world:    "Messages take arbitrarily long"
Raft world:   "Messages usually arrive within 150ms; if not, assume failure"

2. Randomization

Ben-Or's randomized consensus algorithm introduces coin flips. Because the adversary can't predict random choices, the "keep it bivalent forever" strategy fails with probability 1.

FLP applies only to deterministic algorithms. Randomization sidesteps it.

3. Failure Detectors

Chandra and Toueg showed that with an unreliable failure detector (a service that suspects crashed processes, possibly incorrectly), consensus becomes solvable. You trade mathematical certainty for an oracle that's usually right.

ZooKeeper, etcd, and Consul all use failure detectors (heartbeats with timeouts) for this reason.

The next three sections take each escape in turn.


Escape 1 in Depth: Partial Synchrony (DLS)

Dwork, Lynch and Stockmeyer's 1988 paper "Consensus in the Presence of Partial Synchrony" is the theoretical foundation for nearly every production consensus protocol. It introduced the idea that a system can be asynchronous for a while and then become well behaved.

Two flavours of partial synchrony

DLS defined two models, and showed consensus is solvable in both:

FlavourAssumptionIntuition
Unknown boundThere is a fixed bound on message delay (and on relative process speed) that always holds, but the protocol doesn't know its valueNetworks have some real worst-case latency, you just don't know it
Eventual bound (GST)The bound is known, but only holds after some unknown Global Stabilization Time (GST). Before GST, anything goes.Networks have bad periods (congestion, failovers) and then recover

The GST version is the one people usually mean. It captures real networks well: most of the time they are fast, sometimes they misbehave for a while, and protocols must stay safe during the misbehaviour and make progress after it.

The design pattern DLS gives you

DLS protocols, and everything descended from them, share one shape:

  1. Safety mechanism that works under full asynchrony. Quorums and ballot (or term, or view) numbers. Any two quorums intersect, and higher ballots must learn what lower ballots might have chosen. This never relies on time.
  2. Liveness mechanism that relies on timing. Rotate or elect a leader. If the current leader doesn't make progress within a timeout, move to the next ballot. Grow the timeout when attempts fail, so that once the network stabilises the timeout eventually exceeds the real delay.
sequenceDiagram
    participant L1 as "Leader, ballot 1"
    participant F as "Followers (majority)"
    participant L2 as "Leader, ballot 2"
    Note over L1,L2: Before GST — delays are unbounded
    L1->>F: propose in ballot 1
    F--xL1: replies delayed past timeout
    Note over F: timeout fires, move to ballot 2
    L2->>F: prepare ballot 2
    F-->>L2: promises, reporting any accepted value
    Note over L1,L2: Still before GST — ballot 2 stalls too
    Note over L1,L2: After GST — delays at most Δ, timeouts have grown past it
    L2->>F: propose in ballot 3 with safe value
    F-->>L2: accepted by majority
    Note over L2: decided

Notice that before GST nothing is decided but nothing unsafe happens either. That is the trade.


Escape 2 in Depth: Randomization (Ben-Or)

Michael Ben-Or's 1983 paper "Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols" showed that if processes may flip coins, consensus can be solved in the fully asynchronous model. The adversary still controls timing completely, but it cannot predict coin flips, so it cannot keep the system bivalent forever.

The algorithm (crash version, )

Each process has an estimate , initially its input. It runs numbered rounds, each with two phases:

Phase 1 (report). Broadcast REPORT(r, x_p). Wait for reports for round . If more than of them carry the same value , set proposal to . Otherwise set proposal to ?.

Phase 2 (propose). Broadcast PROPOSE(r, proposal). Wait for proposals for round .

  • If at least of them are some ?, decide .
  • Else if at least one is some ?, set .
  • Else set to a random coin flip.

Go to round . (A decided process keeps participating, or broadcasts its decision, so the others aren't left waiting for it.)

sequenceDiagram
    participant P as "Process p"
    participant All as "All processes"
    P->>All: REPORT r with estimate x
    All-->>P: n-f reports
    Note over P: majority value v seen? then proposal = v, else proposal = ?
    P->>All: PROPOSE r with proposal
    All-->>P: n-f proposals
    Note over P: f+1 copies of v means decide v
    Note over P: any v means adopt v
    Note over P: only ? means flip a coin

Why it's safe

  • At most one non-? value per round. A process proposes only if more than processes reported . Two different values would need two disjoint majorities, which is impossible because each process reports one value per round.
  • A decision locks everyone. If decides in round , it saw proposals of . Every other process waits for of at most proposals, so it misses at most of them and therefore sees at least one . Everyone adopts . In round all reports are , every proposal is , and everyone decides .
  • Validity. If all inputs are , every report in round 1 is , every proposal is , and everyone decides in round 1.

Why it terminates with probability 1

In any round where nobody sees a non-? proposal, every process flips a coin. With probability at least , all those coins come out equal. Then in the next round every report carries the same value and everyone decides. Each round therefore has some fixed probability of success that the adversary cannot reduce, and the probability of failing forever is

The catch is the expected number of rounds. With independent local coins it can be exponential in in the worst case. That's fine for 5 nodes and useless for 500.

A runnable simulation

This Python simulation runs Ben-Or with a random scheduler (each process sees a random subset of messages) and some processes crashed. It asserts agreement and validity.

import random

def ben_or(inputs, f, crash=0, seed=None, max_rounds=10_000):
    rng = random.Random(seed)
    n = len(inputs)
    assert 2 * f < n and crash <= f
    x = list(inputs)
    decided = [None] * n
    alive = sorted(rng.sample(range(n), n - crash))
    for r in range(1, max_rounds + 1):
        # Phase 1: each live process reports its estimate.
        reports = [x[p] for p in alive]
        proposal = {}
        for p in alive:
            seen = rng.sample(reports, n - f)  # scheduler picks which n-f arrive first
            proposal[p] = next((v for v in (0, 1) if seen.count(v) > n / 2), None)
        # Phase 2: each live process proposes (value or None meaning "?").
        props = [proposal[p] for p in alive]
        for p in alive:
            seen = rng.sample(props, n - f)
            vals = {v for v in seen if v is not None}
            assert len(vals) <= 1  # at most one non-? value per round
            if vals:
                v = vals.pop()
                x[p] = v
                if seen.count(v) >= f + 1 and decided[p] is None:
                    decided[p] = v
            else:
                x[p] = rng.randint(0, 1)  # the coin flip that defeats FLP
        if all(decided[p] is not None for p in alive):
            return {decided[p] for p in alive}, r
    raise RuntimeError("no decision")

if __name__ == "__main__":
    rounds = []
    for seed in range(2000):
        vals, r = ben_or([0, 1, 0, 1, 1, 0, 1], f=3, crash=seed % 4, seed=seed)
        assert len(vals) == 1  # agreement
        rounds.append(r)
    for v in (0, 1):
        vals, r = ben_or([v] * 7, f=3, seed=1)
        assert vals == {v} and r == 1  # validity, one round
    print("agreement held in 2000 runs, mean rounds",
          sum(rounds) / len(rounds), "max", max(rounds))

On a seven-process cluster tolerating three crashes, a typical run of this script reports a mean of around six rounds, with a long tail (a maximum in the tens). That tail is the price of local coins. The scheduler here is random rather than adversarial, so a worst-case adversary would do worse.

Common coins: making randomization fast

Michael Rabin's 1983 "Randomized Byzantine Generals" used a common coin: a random value that every process sees identically in each round, produced by secret sharing or, in modern systems, threshold signatures. With a common coin, everyone's random choice matches in each round with constant probability, so the expected number of rounds is constant.

Modern asynchronous BFT protocols take this route. HoneyBadgerBFT (2016), for example, uses a threshold-cryptography common coin inside its binary agreement step so that it needs no timing assumptions at all for liveness. The trade is heavier cryptography in exchange for immunity to an adversary who controls the network's timing.

Raft's randomness is not Ben-Or's randomness

Raft randomizes election timeouts so that two candidates rarely time out at the same instant and split the vote. That makes elections converge quickly in practice, but it does not make Raft a randomized consensus protocol in Ben-Or's sense. An adversary that delays messages long enough can still prevent any leader from being elected. Raft's liveness argument rests on timing, with randomness as an accelerator.


Escape 3 in Depth: Failure Detectors (Chandra-Toueg)

Tushar Chandra and Sam Toueg's 1996 paper "Unreliable Failure Detectors for Reliable Distributed Systems" reframed the problem. Instead of adding timing assumptions directly, give each process a local module that outputs a list of processes it suspects have crashed. The module may be wrong. The question becomes: how wrong can it be while still letting consensus terminate?

Completeness and accuracy

A failure detector is characterised by two properties:

  • Completeness: crashed processes eventually get suspected.
    • Strong: every crashed process is eventually suspected permanently by every correct process.
    • Weak: every crashed process is eventually suspected permanently by some correct process.
  • Accuracy: correct processes don't get suspected (too much).
    • Strong: no correct process is ever suspected.
    • Weak: some correct process is never suspected.
    • Eventual strong: after some time, no correct process is suspected.
    • Eventual weak: after some time, some correct process is never suspected.

Combining them gives the classic classes:

ClassCompletenessAccuracyConsensus solvable with
(Perfect)StrongStrongAny
(Strong)StrongWeakAny
(Eventually perfect)StrongEventual strong
(Eventually strong)StrongEventual weak
(Eventually weak)WeakEventual weak

The "eventually" classes are the interesting ones, because they can be wrong for an arbitrarily long time and still be enough. In 1996 Chandra, Hadzilacos and Toueg went further and proved is the weakest failure detector that solves consensus. It is equivalent to , the "eventual leader" oracle: eventually, all correct processes trust the same correct process as leader.

The rotating coordinator algorithm

Chandra and Toueg's consensus algorithm uses rounds with a rotating coordinator (). Each round has four phases:

  1. Every process sends its current estimate, tagged with the round in which it last adopted it, to the coordinator.
  2. The coordinator waits for a majority of estimates and picks the one with the highest timestamp. It broadcasts that as the round's proposal.
  3. Each process waits for the proposal or for its failure detector to suspect the coordinator. If it gets the proposal, it adopts it and sends ack. If it suspects the coordinator, it sends nack.
  4. If the coordinator gets a majority of acks, it reliably broadcasts the decision.
sequenceDiagram
    participant P1 as "p1"
    participant C as "Coordinator for round r"
    participant P3 as "p3"
    P1->>C: estimate with timestamp
    P3->>C: estimate with timestamp
    Note over C: majority received, pick highest timestamp
    C->>P1: proposal v
    C->>P3: proposal v
    P1->>C: ack
    P3->>C: ack
    Note over C: majority of acks
    C->>P1: decide v (reliable broadcast)
    C->>P3: decide v (reliable broadcast)

If the coordinator crashes or is slow, the failure detector eventually suspects it (completeness), processes nack, and the round moves on. Eventually a correct coordinator is reached that nobody suspects (eventual weak accuracy), and that round succeeds. Safety comes from the majority-and-highest-timestamp rule, the same quorum-intersection idea as Paxos.

Where does the failure detector come from?

Here is the subtle point. You cannot implement in a purely asynchronous system. If you could, you could solve consensus, contradicting FLP. In practice, failure detectors are implemented with heartbeats and timeouts, which means they rely on partial synchrony after all.

So failure detectors don't escape FLP for free. Their value is modularity:

  • The consensus algorithm is proved correct assuming only the abstract failure detector properties.
  • The timing assumptions live in one small component, the detector, which you can tune, replace or reason about separately.

This is exactly how production systems are structured. etcd's heartbeat and election timeout, ZooKeeper's tickTime and session timeouts, Cassandra's phi accrual detector, Consul's SWIM-based gossip membership: all are failure detectors in the Chandra-Toueg sense. For implementations and tuning, see Failure Detectors.


Practical Implications

Every consensus system you use has made an explicit choice about which FLP assumption to violate:

graph TD
    FLP[FLP Impossibility] --> A{Which assumption<br>to violate?}
    A --> B[Asynchrony<br>Add timeouts]
    A --> C[Determinism<br>Add randomness]
    A --> D[No oracle<br>Add a failure detector]
    B --> Raft[Raft / Paxos]
    B --> ZK[ZooKeeper ZAB]
    B --> PBFT[PBFT / BFT protocols]
    C --> BenOr[Ben-Or algorithm]
    C --> HB[HoneyBadgerBFT common coin]
    D --> CT["Chandra-Toueg, built from heartbeats"]

Correction

An earlier version of this diagram listed a third branch, "Fault tolerance — Require f+1 of 2f+1 nodes", leading to PBFT. That was wrong on two counts. Majority quorums are how protocols stay safe, not how they escape FLP; FLP already allows only one crash, and quorums don't change the impossibility. And PBFT needs replicas, not , and gets liveness from partial synchrony (view-change timeouts that grow), so it belongs under the timeouts branch.

Raft: Uses randomized election timeouts. The timeouts are what take it out of the asynchronous model; the randomization only makes split votes unlikely, so Raft's liveness still depends on timing rather than on coin flips. (Correction: this line previously said Raft "sidesteps both asynchrony and determinism".)

Paxos: Uses timeouts + quorums

ZooKeeper: Uses heartbeats (timeouts) + majority quorums

Cassandra (leaderless): Doesn't do consensus per-write; uses eventual consistency + read repair (sidesteps the problem entirely by relaxing the agreement requirement). When Cassandra does need agreement, for lightweight transactions (IF NOT EXISTS, conditional updates), it runs a Paxos round and inherits Paxos's timing-dependent liveness.


How Raft and Paxos Live With FLP

Both protocols make the same structural bet: never compromise safety, and accept that liveness depends on the network being reasonable. The details differ.

The safety-liveness split

PropertyPaxosRaftDepends on timing?
Only one value chosen per slotQuorum intersection on ballot numbersElection restriction plus commit rule on termsNo
At most one leader per term/ballotBallots are unique per proposerEach node votes once per termNo
A leader gets electedNeeds one proposer to run unopposed long enoughNeeds one candidate to time out first and collect votes before othersYes
A proposed command gets committedLeader must reach a majority before being displacedSameYes
Reads are linearizable via leasesLeader lease must not overlap the next leaderSame, if lease reads are usedYes, and on bounded clock drift

The last row is worth stressing. Read-index or log-based reads keep safety independent of time. Lease-based reads are faster, but they do make safety depend on clocks. That is a deliberate step further outside FLP's model, and it's the reason lease reads are optional in most Raft implementations. See Leases and Fencing.

Paxos: the dueling proposers livelock is FLP made concrete

In Basic Paxos, any proposer can start a ballot. Two proposers can keep pre-empting each other:

sequenceDiagram
    participant PA as "Proposer A"
    participant Acc as "Acceptors (majority)"
    participant PB as "Proposer B"
    PA->>Acc: Prepare n=1
    Acc-->>PA: Promise n=1
    PB->>Acc: Prepare n=2
    Acc-->>PB: Promise n=2
    PA->>Acc: Accept n=1, v=A
    Acc--xPA: Reject, promised n=2
    PA->>Acc: Prepare n=3
    Acc-->>PA: Promise n=3
    PB->>Acc: Accept n=2, v=B
    Acc--xPB: Reject, promised n=3
    PB->>Acc: Prepare n=4
    Note over PA,PB: can continue forever — safe, never decides

This is exactly an FLP-style infinite bivalent run: every step is legal, every message is delivered, and the value is never chosen. Lamport's "Paxos Made Simple" addresses it in the section on progress, noting that FLP implies a reliable way of picking a single distinguished proposer has to use randomness or real time, such as timeouts. Production Multi-Paxos elects a stable leader and has competing proposers back off with randomized delays. For the full protocol, see Paxos and Paxos Made Simple.

Raft: split votes and the timing requirement

Raft's equivalent of dueling proposers is the split vote: two followers time out at nearly the same moment, both become candidates for the same term, each gets some votes, nobody gets a majority, and both time out again.

The Raft paper picks election timeouts randomly, suggesting a range such as 150 to 300 ms, so that one node usually times out well before the others. It also states a timing requirement that is really a statement about partial synchrony:

  • If electionTimeout is not much larger than the time to send a message round, followers time out before the leader's heartbeats arrive, triggering needless elections. In the FLP model, where broadcast time is unbounded, this inequality can never be guaranteed, which is the theorem showing through.
  • If electionTimeout is not much smaller than the mean time between failures, the cluster spends too much of its life without a leader.

etcd ships with a 100 ms heartbeat interval and a 1000 ms election timeout by default, and its tuning guide recommends setting the election timeout to several times the round-trip time between members. Cross-region clusters routinely raise both. Every one of these numbers is a bet about where GST lands for your network.


Worked Scenario: A Three-Node Raft Cluster Under a Hostile Network

To make the theory concrete, here is a timeline for a three-node etcd-style cluster (nodes A, B, C; heartbeat 100 ms; election timeout randomized in 1000 to 2000 ms) during a period of severe network trouble. Treat it as an illustrative trace, not a log from a real incident.

Time (ms)EventRaft stateFLP lens
0A is leader of term 7, committing writes normallyLeader A, term 7Post-GST: delays well under the timeout
50Network between A and both followers starts dropping or delaying packets by 1 to 3 secondsA still thinks it leadsGST has been "undone": we are in a bad period
1,250B's election timer fires firstB becomes candidate, term 8A slow leader looks exactly like a dead one
1,300B's RequestVote reaches C quickly (B to C link is fine)C votes for B, B is leader of term 8Safety: A can no longer commit anything, it can't reach a majority
1,400Client write reaches AA appends at term 7, can't get acksWrite hangs, not lost, not committed
2,100A's delayed heartbeats finally reach CC rejects them: term 7 is staleHigher terms win, ordering by term keeps it safe
2,300B's heartbeats reach AA steps down, becomes follower in term 8Uncommitted term-7 entry on A is overwritten
2,300 to 9,000The B to C link now also degrades intermittentlyElections in terms 9, 10, 11; some split, some succeed brieflyThe adversarial schedule in miniature: lots of activity, little progress
9,000Network recovers, delays back under 5 msLeader elected in term 12 within one timeoutAfter GST, progress resumes
9,000 onwardClient retries succeedNormal operationLiveness recovered, safety was never at risk

Between 50 ms and 9,000 ms the cluster was "unavailable" in the sense that writes didn't commit reliably. It was never inconsistent. That is the trade every FLP-respecting system makes, visible on a single timeline.

War Story (illustrative)

A team ran a five-node consensus cluster on VMs that occasionally suffered multi-second stop-the-world garbage collection pauses in the co-located JVM sidecar. Every pause on the leader looked, from the followers' side, exactly like a crash. Followers' election timers (500 ms) fired, a new leader was elected, then the old leader woke up, discovered it had a stale term and stepped down. On bad days this happened dozens of times an hour, and client latency spiked with each election. Nothing was ever inconsistent, but the system spent a meaningful fraction of its time electing leaders.

The fix was not a protocol change. They moved the sidecar off the consensus nodes, raised the election timeout to comfortably exceed the worst pause they'd measured, and enabled pre-vote (a would-be candidate first asks whether peers would vote for it) so a node returning from a pause couldn't force a term bump. This is FLP in the field: the protocol can't distinguish slow from dead, so you make "slow" rarer and make the guess more tolerant.


The CAP Connection

FLP and CAP are related but distinct:

TheoremModelSays
FLPAsynchronous, crash-stop failuresConsensus is impossible (termination)
CAPNetwork partitionsChoose 2 of: Consistency, Availability, Partition Tolerance

CAP is about trade-offs during partitions. FLP is about fundamental impossibility even without partitions. A system can satisfy CAP's CP guarantee while still being affected by FLP — consensus still requires escaping the async model.

An unboundedly long delay in FLP's model is indistinguishable, for any finite time, from a partition. That's why the two results feel similar. But they ask different questions: FLP asks whether you can always finish agreeing; CAP asks whether you can always answer while staying linearizable. See CAP Theorem.


Why This Matters in Practice

You will never write a FLP proof. But FLP explains why:

  • Leader election takes time — the system can't instantly agree on a new leader
  • Split-brain is possible — two nodes can simultaneously believe they're the leader during a partition
  • "Strong consistency" has a latency cost — waiting for quorum acknowledgment is the cost of escaping FLP
  • Timeouts are fundamental, not a hack — they are the mechanism by which real systems add the partial synchrony that FLP's model lacks

On split brain, a clarification: a correct consensus protocol never lets two leaders of the same term both commit. But two nodes can both believe they are leader at the same instant (an old leader that hasn't learned of the new term yet). Anything that acts on that belief outside the protocol, such as writing to external storage, needs a fencing token. See Leader Election and Leases and Fencing.

Every time you tune an election timeout, set a replication factor, or choose between CP and AP in your database, you are navigating the consequences of Fischer, Lynch, and Paterson's 1985 proof.


Interview Questions

1. State the FLP result precisely. What are the three conditions you could relax to escape it?

In an asynchronous message-passing system with reliable channels, no deterministic protocol solves binary consensus (agreement, non-triviality, termination) if even one process may crash. To escape it you can add timing assumptions (partial synchrony), add randomness (termination with probability 1), or add an oracle such as an eventually accurate failure detector. You can also give up termination guarantees while keeping safety, which is what every practical protocol does in bad periods.

2. What is a bivalent configuration, and why does the proof care about them?

A configuration is bivalent if both decision values are still reachable from it. Decisions only happen in univalent configurations, so an infinite run of bivalent configurations never decides. The proof shows there is a bivalent starting configuration and that the scheduler can always deliver any pending message while staying bivalent, giving an admissible run that never decides.

3. Explain the "critical step" argument when both steps belong to the same process.

If the two events and that decide 0 versus 1 are both steps by process , consider a schedule where takes no steps and the others decide (they must be able to, since might have crashed). Because doesn't involve , it commutes with 's steps, so the configuration after would have both a 0-valent and a 1-valent successor, yet it already contains a decision. Contradiction. The others can't wait for and can't decide without it.

4. Does Raft violate FLP? How does it get liveness?

No. Raft is safe in a fully asynchronous network: a slow network causes extra elections but never two committed values in the same log slot. Its liveness relies on partial synchrony: if broadcast time is much less than the election timeout for long enough, one candidate wins. Randomized timeouts make split votes unlikely but are not a Ben-Or coin.

5. Why can't you just implement a perfect failure detector with heartbeats?

Because in an asynchronous system a missing heartbeat could mean a crash or a delay. Any timeout either sometimes suspects a correct process (not perfect) or sometimes waits forever (not complete). If you could implement even without timing assumptions, you could solve consensus and contradict FLP.

6. Two Paxos proposers keep pre-empting each other. Is that a bug? How do you fix it?

It's not a safety bug; it's FLP's non-terminating run in practice. The fix is a liveness mechanism: elect a distinguished proposer (Multi-Paxos leader) and use randomized backoff between attempts. This relies on timing, which is exactly what FLP says you need.


Further Reading

Related pages on this site: