Why Consensus Is Hard — FLP, Quorums & Paxos vs Raft

Why getting nodes to agree is the hard problem of distributed systems

Consensus — getting a set of nodes to agree on a single value (who's the leader, what's the next log entry) despite crashes and an unreliable network — sounds simple and is famously not. It underlies leader election, replicated logs, distributed locks, and strongly-consistent databases.

The FLP impossibility (why it's genuinely hard)

In a fully asynchronous network (no bound on message delay), no deterministic protocol can guarantee consensus if even a single node may crash. You can't distinguish "crashed" from "just slow." — Fischer, Lynch, Paterson, 1985.

Real systems sidestep FLP not by breaking it but by relaxing its assumptions: assume partial synchrony (messages usually arrive within some bound) and use timeouts as imperfect failure detectors, plus a touch of randomization. That's enough to make consensus work in practice, even though it's impossible in the pure model.

Worked trace: why the two worlds look identical (FLP)

Two nodes, N1 and N2, must agree on a single value. N1 proposes v1. It sends a message to N2 and waits for an ack before it can commit.

World	What really happened	What N1 can see
A	N2 crashed before receiving the proposal.	No response from N2.
B	N2 is alive, but the network delayed every message/response past N1's timeout.	No response from N2.

N1 cannot tell A from B. Suppose the protocol is deterministic and commits v1 in world A. Then there exists an execution in world B where N2 actually decided v2 independently and all its messages are simply late; N1 commits v1 while N2 commits v2. That violates consensus. If the protocol instead waits forever, it never decides in a world where N2 is merely slow — it is no longer available. A deterministic protocol cannot both always decide and always agree in a model with unbounded delay. That is the FLP impossibility.

What FLP actually forbids. Read the trace again: the fork is between deciding wrongly and never deciding. FLP does not say agreement is impossible — it says a deterministic protocol cannot guarantee a decision (termination) in bounded steps once even one node may crash. Safety is preservable; guaranteed liveness is what dies. Paxos and Raft accept exactly this bargain: they are always safe, only probabilistically live — in theory they can stall forever (dueling proposers in Paxos, repeated split votes in Raft), but they never decide two different values. So is Raft immune to FLP? No — it can fail to elect a leader indefinitely in the adversarial model; randomized election timeouts just make that outcome vanishingly unlikely in practice.

Real systems escape by not being purely asynchronous: they use timeouts to gamble that a missing response means failure, and randomized leader elections to break ties. The gamble is sometimes wrong (a slow node is treated as failed), but the cost of a wrong gamble is only delay — another election round — never a wrong decision. That asymmetry is the whole trick: push all the FLP risk onto liveness, where retrying is cheap, and keep safety unconditional.

Quorum overlap by counting

With n = 2f + 1 nodes, a majority contains f + 1 nodes. Take any two majorities and count how many nodes they must share:

(f + 1) + (f + 1) - (2f + 1) = 1

They overlap in at least one node. Because a correct node never accepts two different values, that one overlapping node is a witness: if one majority tried to certify v1 and another tried to certify v2, the overlapping node would have to accept both, which it will not. Therefore two conflicting values can never both reach majority.

Concrete case: n = 5, f = 2. A majority is 3 nodes. Two different majorities of 3 nodes, drawn from 5, must share at least 3 + 3 - 5 = 1 node. In a 3|2 partition, the 3-node side can still form a majority and commit; the 2-node side cannot. If the 2-node side tried to elect a leader or commit a value, it would need 3 votes, which it can never get. That is why the minority side halts — and why a real CP system refuses writes on the minority side during a partition.

Majorities, quorums, and why CAP falls out

The trick all consensus protocols share: decisions need a majority (quorum). With 2f+1 nodes you tolerate f failures, because any two majorities overlap in at least one node — so no two conflicting decisions can both win. (This is why clusters use odd numbers: 3, 5, 7.)

This is CAP in action: during a partition, only the side with a quorum can make progress; the minority side must refuse writes to stay consistent — it sacrifices availability (CP). A system that let both sides accept writes would be available but would diverge (split-brain).

Paxos vs Raft

	Paxos	Raft
Reputation	provably correct, famously hard to understand	designed for understandability
Structure	roles (proposer/acceptor/learner), subtle	strong leader; everything flows through it
In practice	Chubby, Spanner (Multi-Paxos)	etcd, Consul, CockroachDB, Kafka KRaft

Both achieve the same guarantee; Raft just decomposes it into leader election + log replication + safety, which is why it dominates new systems. But "understandability" is reputation, not mechanism — here is one concrete difference you should be able to say out loud. In single-decree Paxos, any proposer may start a higher-numbered prepare at any time; safety rests entirely on the acceptor promise — once an acceptor promises proposal number n, it refuses everything lower-numbered. That rule makes it impossible for competing proposers to commit two values, but it also lets them livelock, each restarting with a higher number and invalidating the other's round — which is exactly why practical Multi-Paxos elects a distinguished leader. Raft bakes the leader in and replaces the per-slot proposal-number dance with two mechanisms: randomized election timeouts (the Raft paper suggests a 150–300 ms range; implementations tune it, and etcd's defaults are larger), which make split votes a rare accident instead of a recurring duel, and the election restriction — a candidate must present a log at least as up-to-date as each voter's, so the act of winning votes itself guarantees the new leader already holds every committed entry. See the Raft walkthrough for the step-by-step mechanics.

When NOT to use consensus

Consensus is for the small coordination kernel — leader election, membership, configuration, distributed locks — not the data path. Every value routed through Raft or Paxos costs a quorum round-trip and serializes through one leader's disk and network, so running your data writes through consensus caps throughput at what a single leader can push. If a single-writer-per-key design or a per-key replication quorum meets the requirement, don't pay for a total order you don't need: use consensus to agree on who owns what, then let the owners serve the data path directly. (This is precisely how most real systems compose: a tiny Raft/ZooKeeper ensemble coordinates; the fleet it coordinates does the heavy lifting.)

Takeaways

• Consensus = agree on one value despite failures; FLP says no deterministic protocol can guarantee termination in pure async — safety survives, so real systems (timeouts + partial synchrony) run always-safe / not-always-live.
• It rests on majority quorums (2f+1 tolerates f); overlapping majorities prevent conflicting decisions — hence odd cluster sizes.
• Under partition, only the quorum side proceeds — that's CAP's CP choice. Raft = Paxos made understandable.

Drill ladder — test the reasoning

L1 · FLP. "Why can't we just wait longer before declaring a node failed?"
Trap: "Longer timeouts fix it."
Bar: FLP assumes no bound on message delay. For any finite timeout, there exists a correct-but-slow execution that looks exactly like a crash to the waiting node. A deterministic protocol that commits on timeout risks disagreeing with the slow node; a protocol that never times out is unavailable.

L2 · Quorum math. "Why do Raft clusters use odd numbers?"
Trap: "Odd numbers are just conventional."
Bar: With n = 2f + 1, a majority of f + 1 tolerates f failures. With n = 2f + 2 (even), the majority is f + 2 and still only tolerates f failures, so the extra node buys no more fault tolerance but increases the quorum size and latency.

L3 · Paxos vs Raft. "They give the same guarantee, so why does Raft dominate new systems?"
Trap: "Raft is faster."
Bar: Same safety. Raft trades Paxos's flexible roles for a strong-leader decomposition (leader election + log replication + safety) that is easier to understand, implement, and debug. The cost is a leader bottleneck and a failover availability gap.

L4 · Partition behavior. "A 5-node Raft cluster splits 2|3. Can the 2-node side elect a leader?"
Trap: "Yes if it waits long enough."
Bar: No. A candidate needs a majority of 3 votes. The 2-node side can never reach majority, so it must remain unavailable until it rejoins the 3-node side. That is the CP choice during a partition.

---

Re-authored for this guide; partition/quorum diagram hand-authored as SVG. Follows FLP (1985), Lamport's Paxos, and Ongaro & Ousterhout's Raft. See also: CAP Theorem, Quorum, Leader and Follower (Raft walkthrough), The Consistency Spectrum.

I just read a lesson on **Why Consensus Is Hard — FLP, Quorums & Paxos vs Raft** (System Design) and want to truly understand it. Explain Why Consensus Is Hard — FLP, Quorums & Paxos vs Raft from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Why Consensus Is Hard — FLP, Quorums & Paxos vs Raft** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Why Consensus Is Hard — FLP, Quorums & Paxos vs Raft** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Why Consensus Is Hard — FLP, Quorums & Paxos vs Raft** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.