Notesdistributed🌱 seedling

FLP Impossibility

Also: FLP · FLP Result · Fischer Lynch Paterson

In a fully asynchronous system, no deterministic algorithm can guarantee that consensus terminates if even one process may crash. Practical algorithms keep safety unconditionally and get liveness from timeouts or randomness.

Why it exists

It explains why every real consensus system can stall, and why they all lean on timing assumptions for progress.

How it works

  • Asynchronous model: no bound on message delay or processing time, no clocks.
  • A crashed process is indistinguishable from a slow one. Waiting for it may wait forever; not waiting may decide without information that mattered.
  • The proof shows an adversarial schedule can keep the system undecided indefinitely.
  • Ways around it: partial synchrony (the network is eventually timely; use timeouts), randomization (terminate with probability 1), failure detectors.
  • Raft and Paxos: safety holds even if every timing assumption fails; leader election uses timeouts and randomness, so liveness returns when the network behaves.

Trade-offs

Design response Cost
timeouts (partial synchrony) false suspicions trigger needless elections
randomized timeouts probabilistic, not guaranteed, progress
stop rather than diverge unavailability during partitions or storms

In practice

  • Split votes in Raft are the FLP shape in miniature: they could repeat forever; randomized election timeouts make that vanishingly unlikely.

Pitfalls

  • Reading it as "consensus is impossible". It's impossible to guarantee termination deterministically in a purely asynchronous model; real networks are usually timely.
  • Confusing it with CAP Theorem: FLP concerns termination with crashes, CAP concerns availability versus linearizability under partitions.

Recall

These cards are also in your review deck, scheduled with spaced repetition.