FLP Impossibility

Pradeep P

Sep 2

3 min read

Series: Modern System Design · Layer 3 — Reliability

Layer 3 · Post 17 of 21

← Previous: Byzantine Generals Problem → Next: PACELC

Layer 3 — Reliability · Post 101 of 119

In an asynchronous network, crash-stop consensus cannot be both always safe and always live. Timeouts are how we cheat.

What you'll learn

What Fischer, Lynch, and Paterson actually ruled out
Asynchronous vs partial synchrony, and why Raft's elections have timeouts
How to answer "does FLP mean consensus is impossible?" without panicking

The idea in one minute

FLP (1985): there is no deterministic protocol that solves consensus in a fully asynchronous network if even one process may crash, while always guaranteeing:

Safety: nodes never decide different values (agreement + validity)
Liveness: every correct node eventually decides

Asynchronous here means: messages can be delayed arbitrarily. You cannot tell a slow node from a dead one. Any round you call "the last round" might still have a message in flight that would have changed the vote. The proof shows you can always delay the right message to keep the group undecided one step longer — forever.

Is B crashed, or is B's vote 30 seconds late?
If you wait forever: not live.
If you decide without B: might violate agreement if B was just slow.

Why it matters

This is why every real consensus system uses clocks (timeouts, elections, "I haven't heard from the leader"). Timeouts leave the pure async model. You might elect a new leader while the old one was only slow — then you need terms / fencing so safety still holds (Posts 36 and 105).

Interviews: FLP is not "consensus is impossible so we give up." It is "pure async + deterministic + one crash + always both safe and live is impossible." Production picks safety first, liveness when the network is reasonable (partial synchrony).

How it works

Consensus (crash model): processes propose values; they must agree on one, the value must have been proposed, and they must terminate.

What FLP does not say:

Consensus is impossible on the internet (the internet is not purely async in practice; we use timers).
Randomized protocols cannot help (they can get almost-sure termination).
Synchrony is impossible (if you have a max delay Δ, the problem changes).
Byzantine (that's harder, previous post).

Partial synchrony (Dwork, Lynch, Stockmeyer): after some unknown global stabilization time, messages arrive within a bound. Paxos/Raft safety does not depend on that bound; elections / liveness do. If the network is a disaster forever, a Raft cluster may not elect (no liveness) but it should not commit two histories (safety).

Cheats we use:

Timeouts (failure detectors). Unreliable by FLP's lights; good enough.
Randomization (Ben-Or and descendants).
Hardware / GPS / TrueTime (Spanner): extra timing assumptions.

Paxos vs FLP. Paxos is safe when messages are delayed; it may not decide until delays look like a working network. That is FLP-compatible: you gave up "always live in full async."

A simple example

Three-node etcd. The leader is in a GC pause for 15 seconds. Followers' election timeouts fire. They start an election. If the old leader wakes and still thinks it is leader, two leaders would be a safety bug — Raft term numbers reject the stale one.

If you never timed out, you would wait forever for the paused leader (not live). If you timed out with no terms, you might double-write (not safe). FLP is why that tension exists; Raft's design is the industry answer.

Telling an interviewer "we cannot do consensus because FLP" after they asked how Kafka elects partition leaders is a miss. Say: we assume timeouts; we keep safety with epochs.

Common mistakes

FLP as a reason to use a single database forever. Single-node still fails; you just moved the problem.

"Async" meaning Node.js. FLP-async is unbounded delay, not an event loop.

Claiming Paxos "violates FLP." It does not promise liveness in full asynchrony.

Using FLP and Two Generals as synonyms. Two Generals: two parties, coordinated action, loss. FLP: n parties, crash, agreement, async. Related vibe, different theorems.

How this shows up in real systems

Raft / Paxos / Zab (ZooKeeper): election timeouts, ticks, heartbeat.
Cassandra / Dynamo "sloppy quorum": often don't wait for consensus on every write; they chose AP-ish liveness (CAP).
Spanner TrueTime: tighten the timing model so transactions can wait out uncertainty.
Kubernetes: lease duration and retry period are FLP cheats in YAML.

Recap

Full async + deterministic consensus + one crash ⇒ cannot always be safe and live.
Production consensus: safe always (under crash assumptions); live when timers make sense.
Next: CAP's everyday cousin — PACELC.