Deep Dive · supplement to Part 1, Lesson 8 · visual edition
Consensus — the floor beneath FLP, Raft & BFT
~30 min · 6 levels · the proofs & the safety bug you'd otherwise ship · interactive recall
Published
ConsensusPaxosRaftFLPIdempotency keys
Your bar: from a blank page, redraw why FLP is true (bivalence),
exactly what makes Raft safe (the election restriction), the one commitment rule
everyone states wrong (Figure 8), and why lying nodes force 3f+1. Five
sentences from Lesson 8 each hide a subtlety that separates “I read the Raft paper”
3
from “I could implement it without a safety bug.”
One sentence holds the whole supplement. Each level unpacks one chip of it:
Async consensus can’t be guaranteed (FLP)
so real protocols buy liveness with partial synchrony
Raft moves safety into the election
and lying nodes raise the wall to 3f+1
Memorise this banner. Every level below either proves why termination must yield, or
shows how a real protocol keeps the two safety properties anyway.
1
FLP, actually proved — the bivalence argument
“An adversary delays the deciding message forever” is the shape. The real proof says
precisely where the impossibility lives.
The bivalence argument. Configurations are 0-valent, 1-valent, or
bivalent. A bivalent start exists; from any bivalent configuration the adversary can
always step to another bivalent one, so it never reaches a decision.
Model the system as a configuration = every node’s state + every in-flight
message. Its valence is which decisions are still reachable:
The proof is two lemmas: a bivalent start exists, and from any bivalent config the adversary
can stay bivalent forever.
Lemma 1 — a bivalent start exists Order all initial input vectors so neighbours
differ in one node’s input. All-0 is 0-valent, all-1 is 1-valent; somewhere two
neighbours flip valence. Crash that one differing node and the runs are indistinguishable
→ must decide alike → one neighbour is bivalent.
Lemma 2 — bivalence is inescapable From a bivalent config, delivering a pending
message e can always be arranged to land in another bivalent one. A
“critical step” where e vs e’ forces opposite valences can’t
exist: they either commute (different nodes) or one node can crash right after (same node)
— indistinguishable.
✗ “FLP says consensus is impossible in practice”
✓ It says no deterministic protocol can guarantee termination in a
purely asynchronous model
The dagger: the adversary may not drop messages or crash more than one node — it only chooses
message order, and every message is still eventually delivered. Impossibility
comes from asynchrony alone. Relax any one assumption and consensus is solvable:
Every real protocol below takes the partial-synchrony escape: keep safety always,
get liveness once the network calms down.2
🔒 Memory rule: FLP kills guaranteed termination in pure async with one
crash — order alone is enough; real systems trade liveness for partial synchrony and never
give up safety.
Memory check
What is a "configuration"? → all node states + all in-flight messages
Which property does FLP make impossible to guarantee? → termination (safety always holds)
The adversary's only power? → choosing message order; it can't drop or extra-crash
2
Raft is safe via five properties — one is subtle
Raft (Ongaro & Ousterhout, 2014)
3
guarantees correctness through five always-true invariants. Four are mechanical; one carries
the whole proof.
#
Property
Plain meaning
1
Election Safety
at most one leader per term
2
Leader Append-Only
a leader never overwrites/deletes its own log, only appends
3
Log Matching
same index and term in two logs ⇒ all prior entries identical
4
Leader Completeness
a committed entry is present in the log of every later-term leader
5
State Machine Safety
no two servers apply a different command at the same index
Leader Completeness (4) is the one that makes the whole thing work — and it’s not
obvious. A brand-new leader is never told what was committed, so why must it already
hold every committed entry? The answer is the election restriction + the
quorum-overlap trick:
On RequestVote, a follower refuses unless the candidate's log is at least as up-to-date (compare last-entry term, then index). A candidate missing a committed entry can never assemble
a majority.
✗ “The previous leader hands its log to the new one”
✓ Nobody hands anything over — the up-to-date check at vote time guarantees it
🗳️ Memory rule: Raft moves the hard safety work into the election, not
the replication — the up-to-date vote check is what makes a leader complete.
Memory check
Which property does the real work? → Leader Completeness (#4)
What enforces it? → the election restriction + majority overlap
"Up-to-date" compares what, in order? → last-entry term, then index
3
The commitment gotcha — Raft’s Figure 8
The single most important subtlety in Raft, and the rule almost everyone states wrong on a
first reading.
✗ “An entry is committed once stored on a majority of nodes”
✓ True only for a current-term entry; a previous-term entry on a
majority can still be overwritten
The Figure-8 commitment trap. An entry from an old term, replicated to a
majority, can still be overwritten by a later leader. A leader must only count an entry
committed once it has replicated an entry from its own term on a majority.
Walk the canonical five-node scenario (S1–S5). At step (c) the old entry is on a
majority — and committing it there is the disaster:
Step
What happens
Danger
(a)
S1 is leader in term 2, replicates idx2(t2) to S1,S2
—
(b)
S1 crashes. S5 wins term 3 (S3,S4,S5 — short logs pass the check), accepts a
differentidx2(t3) on S5 only
—
(c)
S5 crashes. S1 restarts, wins term 4, re-replicates old idx2(t2) to
S1,S2,S3 — now a majority
⚠ tempting to call it committed
(d)
If it did: S1 crashes, S5 wins term 5 (S5’s idx2(t3) is a higher term →
“more up-to-date”), forces idx2(t3) onto everyone
✗ overwrites a “committed” entry — agreement violated
📌 The fix (one sentence in the paper): A leader counts an entry committed only
once it has stored an entry from its own current term on a majority; earlier-term
entries are then committed indirectly, carried by Log Matching.
So at (c), S1 must not commit idx2(t2) by replica count. It waits to
replicate a fresh idx3(t4) on a majority — the instant that commits, S5 (lacking
idx3) can never win again, so idx2 is safe too.
Commitment is only ever decided through a current-term entry; the past rides along.
Miss this and you ship an implementation that loses committed data under one specific crash
interleaving — and it passes every test that doesn’t reproduce exactly that order.
Memory check
When is replica-count commitment safe? → only for a current-term entry
How do old-term entries get committed? → indirectly, once a current-term entry above them commits
Why won't normal tests catch the bug? → it needs one exact crash interleaving
4
Membership change without splitting in two
Cluster membership isn’t fixed. Switch nodes from C_old to C_new at
slightly different moments and each set can form a majority independently — two leaders,
divergence. Changing membership is itself a consensus problem.
The cluster transitions through an intermediate C_old,new where elections and commits each need a majority of both sets, separately and simultaneously.
✗ “Just point every node at the new config and restart”
✓ A naive cutover breaks Election Safety; you need joint (overlapping) consensus
🔀 Memory rule: Joint consensus forces every decision to clear a majority of
both old and new sets at once, so two independent majorities can never coexist.
(Single-server-at-a-time changes came later; joint consensus is the idea to hold.)
Memory check
Why is a naive membership switch dangerous? → C_old and C_new can each form a majority
What does C_old,new require for any decision? → a majority of both sets, simultaneously
The two-step sequence? → commit C_old,new, then commit C_new
5
The landscape — you don’t have to use Raft
Raft is one point in a space dominated for decades by Paxos. Same safety; different
trade-offs.
All provide the same safety. Raft & Multi-Paxos are crash-fault-tolerant (CFT): they assume nodes fail by stopping, not by lying — which is the last, biggest
step.
Protocol
Idea
Trade-off
Paxos (single-decree)
agree on one value via prepare/promise then accept/accepted, around a quorum
proven minimal; famously hard to understand & productionise
Multi-Paxos
a stable leader runs a sequence of Paxos instances — a replicated log
the practical form; what most “Paxos” systems mean
Raft
same guarantees, redesigned for understandability: strong leader, terms, election
restriction
easier to get right; strong-leader bottleneck caps throughput
EPaxos / leaderless
no fixed leader; exploit that commuting commands need no agreed order
lower latency, no leader hotspot, at real complexity cost
🗺️ Memory rule: Paxos → Multi-Paxos → Raft are the same CFT family; EPaxos drops
the leader. Pick by who you trust to bottleneck (the leader) vs how much complexity you’ll
pay.
Memory check
Multi-Paxos in one line? → a stable leader running a sequence of Paxos = a replicated log
Raft's main cost? → strong-leader throughput ceiling
What do CFT protocols assume about failures? → nodes stop, never lie
6
When nodes lie — Byzantine consensus & the 3f+1 wall
Drop the crash-fault assumption. A Byzantine node (Lamport, Shostak &
Pease, 1982)
5
can do anything — send conflicting messages, forge values, collude. The model for
systems crossing trust boundaries: blockchains, compromised participants.
Crash vs Byzantine quorums. Tolerating f crashes needs 2f+1 nodes;
tolerating f liars needs 3f+1, because quorums must overlap in enough nodes to guarantee
at least one honest one in common.
Under crash faults a one-node overlap suffices — that node is trustworthy. Under Byzantine
faults the shared node might be the liar, so the overlap must contain more honest than faulty nodes → 2f+1 quorums out of 3f+1, intersecting in f+1.
Fault model
Nodes
Quorum
Why
Crash (CFT — Raft, Paxos)
2f + 1
f + 1
any two majorities overlap in ≥ 1 node, which is correct (didn’t lie)
Byzantine (BFT — PBFT)
3f + 1
2f + 1
any two quorums overlap in ≥ f + 1 nodes, so ≥ 1 of the overlap is honest
✗ “BFT is the safer choice, use it everywhere”
✓ Inside one datacenter, crash faults are the honest model — 2f+1 Raft is right; reach for
3f+1 only across trust boundaries
🛡️ Memory rule: Crash needs a quorum overlap of one trustworthy node; Byzantine
needs the overlap to out-number the liars → 2f+1 of 3f+1, intersecting in f+1 with ≥ 1
honest.
PBFT (Castro & Liskov, 1999)
5
made this practical with three phases (pre-prepare, prepare, commit). Nakamoto/Bitcoin reaches
probabilistic Byzantine agreement via proof-of-work instead of fixed quorums;
Tendermint and HotStuff are PBFT descendants.
Memory check
Why 3f+1 not 2f+1? → overlap must contain an honest node even if the liar is in it
Byzantine quorum size? → 2f+1, intersecting in f+1
PBFT's three phases? → pre-prepare, prepare, commit
Where each idea shows up — real systems
Grounding for the theory: the concept, a concrete place it bites, and the lesson it teaches.
Concept
Real system
What it teaches
FLP / partial synchrony
Any Raft/Paxos cluster wedging during a network blip, then recovering
safety holds; liveness waits for the network to calm
Election restriction
etcd / Consul leader elections refusing stale candidates
committed history can’t be lost across a leader change
Figure-8 commitment
The classic Raft implementation bug: committing prior-term entries by replica count
crossing trust boundaries triples the honest-overlap requirement
Pattern to notice: inside one company’s datacenter, 2f+1 crash-fault tolerance
is almost always the right model. The 3f+1 machinery is for when participants
genuinely can’t trust each other.
Q1. FLP proves consensus can't be guaranteed specifically when the system is…
Q2. Which consensus property does FLP make impossible to guarantee?
Q3. A brand-new Raft leader is guaranteed to hold every committed entry because…
Q4. A Raft leader may treat an entry as committed only once it has…
Q5. Joint consensus prevents split-brain during membership change by…
Q6. Byzantine consensus needs 3f+1 rather than 2f+1 because…
Reconstruct the deep dive from a blank page
Write the six levels in order, one line each, with nothing on screen. Then reveal and compare — gaps are your next drill.
1 FLP: bivalence — order alone kills guaranteed termination; partial synchrony is the
escape · 2 Raft safety lives in the election: up-to-date check + majority overlap ⇒
Leader Completeness · 3 Figure 8: commit by replica count only for current-term
entries; old ones ride along · 4 Membership: joint consensus needs a majority of both
sets ⇒ no split brain · 5 Landscape: Paxos→Multi-Paxos→Raft (CFT); EPaxos drops the
leader · 6 Byzantine: liars force 3f+1, quorum 2f+1, overlap f+1 with ≥1 honest.
I’m your teacher — ask me anything. Say “grill me on consensus” for
mixed no-clue questions, or hand me a real system and I’ll place it on CFT↔BFT and
leader↔leaderless with you. Want to whiteboard a Raft commit walkthrough or the Figure-8 trace
live? Just ask.
Interview — pick your bar
Answer out loud in ~60s, then reveal. Core = recall · Senior = trade-offs &
failure modes · Staff = synthesis under ambiguity · System Design = open
design round (a different axis, not a harder level).
What problem does consensus solve, and what are its three required properties?
Hit these points: consensus = a set of nodes agree on a single value (or a single ordering of commands) despite crashes and message delays → the three properties: Agreement (no two correct nodes decide different values), Validity (the decided value was proposed), Termination (every correct node eventually decides) → agreement + validity are safety, termination is liveness → consensus is equivalent to total-order broadcast, which is exactly what a replicated state machine / replicated log needs → so "build a replicated log" and "solve consensus" are the same problem.
Why does crash tolerance need 2f+1 nodes but Byzantine tolerance need 3f+1?
Hit these points: it's all quorum-overlap reasoning → crash (CFT): with 2f+1 nodes a majority is f+1, and any two majorities overlap in ≥1 node — that shared node is honest (crashed nodes just stop), so it carries the agreed value forward → Byzantine (BFT): the overlapping node could be the liar, so a single shared node isn't enough; you need quorums of 2f+1 out of 3f+1 so any two intersect in f+1 nodes, guaranteeing ≥1 honest node in the overlap → mnemonic: CFT survives nodes that stop, BFT survives nodes that lie → PBFT does this in three phases; Nakamoto/PoW gives only probabilistic finality.
What does FLP state precisely, and what's the standard escape hatch?
Hit these points: FLP: no deterministic protocol can guarantee termination in a purely asynchronous model that tolerates even one crash → it does not say consensus is impossible — safety is fine; it says you can't guarantee both safety and liveness with no timing assumptions → the escape is partial synchrony (DLS 1988): assume the network is eventually timely, use timeouts for liveness, and never let timeouts compromise safety → randomization is the other escape (terminate with probability 1) → that's why every real protocol (Paxos, Raft) keeps safety unconditional and makes liveness depend on the network calming down.
How does Raft elect a leader and guarantee at most one per term?
Hit these points: time is divided into terms; a follower whose election timeout fires becomes a candidate, increments the term, votes for itself, and requests votes → each node grants at most one vote per term → a candidate wins only with a majority; since two majorities always overlap and the overlap node already voted, two leaders in one term is impossible (Election Safety) → split votes are resolved by randomized election timeouts so candidates rarely time out together → the leader sends periodic heartbeats; a higher term seen anywhere makes a node step down.
State FLP precisely, then explain why the bivalence argument is sharper than "the adversary delays a message."
Hit these points: no deterministic protocol can guarantee termination in a purely asynchronous model tolerating one crash → bivalence is the engine: Lemma 1 shows a bivalent (outcome-undecided) initial configuration must exist, and Lemma 2 shows from any bivalent state the adversary can always reach another bivalent state → so the protocol can be kept perpetually undecided → the key subtlety: the adversary only reorders messages, it never drops them or crashes more than one node — far weaker than "messages get lost," which is why the result is so strong → bonus: names the partial-synchrony escape (DLS) and that randomized protocols sidestep it too.
A new Raft leader is never told what was committed. Why is it guaranteed to already hold every committed entry?
Hit these points: the election restriction — a voter grants its vote only to a candidate whose log is at least as up-to-date (compare last-entry term, then index) → a committed entry lives on a majority; a winning candidate also needs a majority; those two majorities overlap in ≥1 voter → that overlapping voter holds the committed entry and would refuse to vote for a candidate missing it → therefore the winner already has every committed entry — this is Leader Completeness → red flag answer: "the old leader hands its log over" — there is no handover; safety comes from the vote-time check, not from the predecessor.
Walk me through Raft's Figure 8 and state the commitment rule that prevents it.
Hit these points: an entry from a previous term can be replicated to a majority and still be overwritten — a later leader (S5) can win with a higher last-term entry and clobber it → so "replicated on a majority" is not sufficient to call a prior-term entry committed → the rule: a leader may only mark an entry committed once it has replicated an entry from its current term on a majority; earlier entries then commit indirectly via Log Matching → the trap is committing by replica count alone → bonus: this bug hides because it needs a specific crash/election interleaving, so naive tests pass — you need a model checker (TLA+) or targeted fault injection to force it.
How does Raft change cluster membership without risking two leaders?
Hit these points: a naive single-step cutover from C_old to C_new lets each configuration independently form a majority during the overlap → split brain, two leaders → joint consensus routes through a combined C_old,new in which every election and every commit requires a majority of both the old and new sets simultaneously → sequence: commit C_old,new, then commit C_new; once C_new is committed the old config can retire → because both majorities are required during transition, two disjoint majorities can never form → bonus: single-server add/remove (changing membership one node at a time) is the later, simpler optimization that avoids full joint consensus.
Your team's homegrown Raft loses a committed write under one rare crash sequence. What's your first hypothesis and how do you confirm it?
Hit these points: first hypothesis: the Figure-8 commitment bug — committing a prior-term entry by replica count instead of waiting to replicate a current-term entry on a majority → second candidates: missing fsync-before-ack (durability lost on crash), or a broken election restriction letting a less-up-to-date candidate win → confirm not by adding logs and hoping the race reappears, but by writing a TLA+/model-checked spec or a deterministic-scheduler test that forces the exact crash-then-elect interleaving → reproduce → fix the commit rule → keep the model check in CI as a regression → the staff move is treating safety bugs as specification problems, not log-spelunking problems, because the failing interleaving is too rare to catch by chance.
When would you choose Multi-Paxos, Raft, EPaxos, or PBFT — and when none of them?
Hit these points: all crash-fault options give identical safety, so choose on operational and performance axes → Raft for implementability and a strong leader's simple mental model (most teams); Multi-Paxos as the battle-tested incumbent where it already exists; EPaxos to remove the single-leader throughput/latency bottleneck for commuting commands, accepting a sharp jump in complexity; PBFT only when you must tolerate lying nodes across a trust boundary (3f+1, 3 phases) → none when you don't actually need linearizable agreement — if eventual consistency / CRDTs / a single-writer design satisfy correctness, consensus is needless coordination cost → the principal framing: consensus is the most expensive coordination primitive; justify the need before picking a flavor.
Distinguish safety from liveness in a replicated log, and which one you're allowed to sacrifice.
Hit these points:safety = nothing bad happens: never two leaders in a term, never lose or reorder an acknowledged committed entry, never let two correct nodes diverge → liveness = something good eventually happens: a request eventually commits, a new leader is eventually elected → FLP says you cannot guarantee both under pure asynchrony, so the universal design choice is: safety is unconditional, liveness is best-effort under partial synchrony → concretely, during a partition a CP log refuses progress (sacrifices liveness/availability) rather than risk two leaders (sacrificing safety) → the staff point: any protocol that "stays available" through a partition by relaxing majority is silently trading away safety — make that trade explicit and intentional, never accidental.
Design-round framework — drive any consensus/replicated-log prompt through these, out loud:
Fault model: crash-only (2f+1) or Byzantine/trust boundary (3f+1)? — pick the cluster size from f.
Commit path: majority replication, commit only via a current-term entry, fsync-before-ack.
Leadership: election restriction on votes, randomized timeouts, leader leases to bound stale reads.
Membership changes via joint consensus; client dedup/idempotency so retried proposals don't duplicate.
Liveness vs safety: what happens under partition (block the minority); how reads stay linearizable.
Verification & ops: TLA+/model check the safety properties; fault-injection for rare interleavings.
Whiteboard the commit path for a replicated log that must never lose an acknowledged write.
A strong answer covers: replicate to a majority before acking the client, and on each replica fsync the entry to durable storage before counting its vote — an in-memory ack that a power loss erases is not a commit → mark an entry committed only after a current-term entry reaches a majority (Figure-8 rule), so a later leader can't overwrite a "committed" prior-term entry → enforce the election restriction so any new leader already holds every committed entry (Leader Completeness) — no log handover → bound stale reads with a leader lease or read-index so a deposed leader can't serve a linearizable read → make client requests idempotent (request IDs / dedup) so a retried proposal after a timeout commits at most once → change membership via joint consensus to preserve Election Safety → verify the safety properties with a model checker and force the rare crash/election interleavings with fault injection → name the trade-off: fsync-before-ack and majority replication add tail latency, which you accept as the price of RPO = 0.
Design a consensus-backed configuration / coordination store (think etcd / ZooKeeper).
A strong answer covers: a small odd-sized cluster (3 or 5) running a single replicated log via Raft/Multi-Paxos — crash-fault model, 2f+1, since it's inside one trust domain → all writes go through the leader and the log, giving linearizable, totally-ordered updates; expose compare-and-swap / leases / watches on top of the log → serve reads via the leader with a read-index or lease so they're linearizable without a full log round-trip, or offer explicitly-stale follower reads as a separate, labeled API → durability: fsync-before-ack, periodic snapshots + log compaction so the log doesn't grow unbounded → under partition, the minority side stops serving writes (CP) — correctness over availability, which is right for locks/config → clients use sessions + fencing tokens so a client that loses its lease (GC pause, partition) can't act on a stale lock → membership changes via joint consensus; keep the cluster small because write latency = majority round-trip and grows with size → name the trade-off: this store is deliberately low-throughput and strongly consistent — it coordinates other systems, it is not your data plane.
★ Cheat sheet — the numbers & the gotchas
Mental models: FLP = order alone defeats guaranteed termination · safety
always, liveness waits · Raft safety lives in the election · commit only via a
current-term entry · joint consensus for membership · CFT = 2f+1, BFT = 3f+1.
The numbers
Quantity
Value
Crash-fault nodes for f failures
2f + 1 (quorum f+1, overlap ≥1 correct)
Byzantine nodes for f liars
3f + 1 (quorum 2f+1, overlap f+1 ⊇ honest)
Consensus properties
Agreement · Validity · Termination
FLP casualty
Termination (in pure async, 1 crash, deterministic)
① “Majority = committed” is true only for current-term entries (Figure 8).
② A new leader is complete because of the vote-time up-to-date check, not a
handover. ③ Naive membership cutover breaks Election Safety — use joint
consensus. ④ Don’t reach for BFT inside one datacenter;
crash faults are the honest model.
📄 Supplement to Part 1, Lesson 8 · DDIA Ch. 9 (Consistency & Consensus)Read next ▸ Raft paper §5.4 (Leader Completeness & Figure 8)
Was this lesson helpful?Thanks — noted.
These notes reflect my current understanding and are updated as I learn, build, and
discover better explanations.
