# DDIA Ch. 10: only the majority side of a partition can decide — and more nodes don't mean more throughput ## Concept Single-decree consensus decides a value only when a **strict majority** of the cluster acknowledges it — `floor(n/2)+1` acks, never fewer. Partition a 5-node cluster **3–2** and the asymmetry is total: the 3-node side reaches majority (3 ≥ 3) and **decides**; the 2-node side has 2 < 3 acks and **blocks** — it can't decide, and can't even tell whether the other side already did. Then the counterintuitive part: going 3 → 5 → 7 nodes *raises the failures tolerated* (1 → 2 → 3) but the majority *grows too* (2 → 3 → 4 acks per decision), so a single decision does **more** work as the cluster grows, not less. "More replicas = more throughput, and my minority partition keeps serving" is wrong on both counts. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 10 — *Consistency and Consensus*, §"Single-value consensus" / §"Pros and cons of consensus": > only the majority portion of the network can make progress. The book presents consensus (single-decree, Paxos/Raft-style) as safe under partition precisely because a decision requires a majority, and any two majorities of the same cluster overlap. Here you watch that overlap force exactly one side to make progress — and watch the majority requirement make each decision *heavier*, not lighter, as you add nodes. ## Prerequisites The result is carried by one idea: a **strict majority**. These help; each line notes where it shows up. 1. **Majority quorums** — a decision needs `floor(n/2)+1` acks, the smallest set such that any two such sets share a node. It shows up as `majority()` and the `acks >= quorum` test in `propose()`. 2. **Consensus safety (agreement) and liveness (progress)** — safety says two nodes never decide different values; liveness says the cluster eventually decides *something*. The minority side keeps safety but loses liveness. It shows up as the 2-side returning `BLOCKED`, not a wrong value. 3. **Split-brain avoidance** — if both sides could decide, they could decide *different* values (two "leaders"). Requiring a majority makes that impossible because the two majorities would have to overlap. It shows up as only one `cluster.decided` value existing after both proposals. 4. **Why an even split can't both progress** — in a 3–2 split only the 3-side is a majority; in a 2–2 split (n=4) *neither* side is, so *nobody* progresses — which is why real clusters use an odd n. It shows up in the n=4 note in Scenario 2. ### Where to learn the prerequisites - **Majorities, safety/liveness, split-brain (#1–#3):** DDIA §"Single-value consensus", §"The leader and the lock", §"Fencing tokens"; Ongaro & Ousterhout, "In Search of an Understandable Consensus Algorithm" (Raft, 2014) §5 for the majority-overlap argument. - **Even-split / odd-n (#4):** DDIA §"Pros and cons of consensus" on quorum size and the cost of adding nodes. If only one is new, make it **#1 — strict majority**. The overlap of any two majorities is the entire reason the minority must wait, and the reason each decision's cost rises with n. ## Environment Deterministic, so the numbers reproduce exactly: - macOS 26.5.2 (Darwin 25.5.0), arm64 - Python 3.15.0a8, standard library only — no Docker, no deps - No real network: the partition and the acks are modelled in one process, so the outcome is fixed every run - Fixed cluster sizes: 5 (partitioned 3–2), then the table over n = 1, 3, 5, 7 ## Mental model A **majority** is the smallest set of nodes such that *any two majorities of the same cluster must overlap in at least one node*. For n = 5, majority = 3, and any two 3-subsets of 5 share a node — there's no room for two disjoint majorities. That single overlapping node is what makes split-brain impossible: it can't ack two conflicting values, so two majorities can never decide differently. The consequence for a partition is immediate. Split the cluster and *at most one* side can hold a majority. That side has enough acks to decide. The other side — the minority — is not missing permission, it is missing **nodes**: it physically cannot assemble `floor(n/2)+1` acks, so it must wait. It also can't distinguish "the other side decided" from "the other side is down," so it can't safely guess. The whole thing is one script, `code/majority_quorum.py`, exposing a single `Cluster.propose(value, reachable)` that decides iff `len(reachable) >= majority`. ## Setup ``` cd study/ddia/ch10/code python3 majority_quorum.py ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — partition a 5-node cluster 3–2 **Predict.** A 5-node cluster splits into a 3-node side and a 2-node side. Majority is 3. Which side (if any) can decide a value — and what does the *other* side do? **Observe.** ``` === Scenario 1: a 5-node cluster, partitioned 3-2 === cluster size n = 5, majority needed = 3 acks 3-side ['n1', 'n2', 'n3'] proposes x=BIG: collected 3 acks, need 3 -> DECIDED 2-side ['n4', 'n5'] proposes x=SMALL: collected 2 acks, need 3 -> BLOCKED cluster decided value: 'x=BIG' the 2-side cannot decide, and cannot even tell whether the 3-side already did -- it just blocks. Only the majority side progresses. ``` The 3-side decides **x=BIG**; the 2-side collects only 2 of the 3 required acks and **blocks**. Exactly one value is ever decided. ### Step 2 — failures tolerated as you add nodes **Predict.** For n = 1, 3, 5, 7: what is the majority, and how many node failures can the cluster survive and still form a majority from the rest? **Observe.** ``` === Scenario 2: failures tolerated vs. cluster size === n majority failures tolerated 1 1 0 3 2 1 5 3 2 7 4 3 adding nodes raises the failures tolerated: floor((n-1)/2) = 1, 2, 3. (an even node adds NO tolerance over the odd below it: n=4 also tolerates 1, same as n=3 -- so clusters stay odd.) ``` Failures tolerated climbs 0 → 1 → 2 → 3. More nodes really do buy more availability — this half of the intuition is right. ### Step 3 — acks per decision as you add nodes **Predict.** Same n = 3, 5, 7. Each decision needs a majority round-trip. How many acks does one decision require at each size — does a decision get *cheaper* as the cluster grows? **Observe.** ``` === Scenario 3: acks per decision vs. cluster size === n acks per decision (= majority) 3 2 5 3 7 4 every decision needs a full majority round-trip, and the majority GROWS with n: 2, 3, 4 acks. A single decision does more work, not less, as the cluster grows -- consensus throughput is flat-to- declining in n, never rising. More nodes buy availability, not speed. ``` Acks per decision *rise* 2 → 3 → 4. A single decision does **more** work at n=7 than at n=3 — the exact opposite of "add nodes to go faster." ## What you should see - 5-node cluster split 3–2: the **3-side DECIDES** (3 ≥ 3), the **2-side BLOCKS** (2 < 3), and exactly one value — `x=BIG` — is ever decided. - Failures tolerated for n = 1, 3, 5, 7 is **0, 1, 2, 3** (`floor((n-1)/2)`); an even n adds nothing over the odd below it. - Acks per decision for n = 3, 5, 7 is **2, 3, 4** (`floor(n/2)+1`) — it *grows* with n, so a single decision never gets cheaper by adding nodes. ## Why The lever behind all three results is one property of majorities: **any two majorities of the same cluster intersect.** A majority is `floor(n/2)+1` nodes; two disjoint majorities would need `2 · (floor(n/2)+1) > n` nodes, which the cluster doesn't have. So there is always at least one node in both — and that shared node cannot acknowledge two conflicting proposals. This is the whole safety argument: two majorities can never decide different values, so a decision, once made, is final and unique. Split-brain is not prevented by good behavior; it is prevented by arithmetic. That same arithmetic is why only the majority side of a partition proceeds. A partition carves the cluster into groups whose sizes sum to n; at most one group can be a majority (two would have to overlap, but a partition means they don't). The majority side has enough acks and decides. The minority side isn't waiting for permission — it is *short of nodes*, unable to assemble `floor(n/2)+1` acks no matter how long it tries, and unable to tell a decided-elsewhere cluster from a dead one. It keeps **safety** (it never decides a wrong value) at the cost of **liveness** (it decides nothing). That is the trade the book names: only the majority portion can make progress. And it is why adding nodes doesn't speed anything up. Every decision must *contact* a majority, and the majority is `floor(n/2)+1`, which grows with n: 2, 3, 4 for n = 3, 5, 7. So going from 3 to 7 nodes doubles the failures you tolerate but also raises the acks each decision waits on from 2 to 4. Per-decision work rises monotonically in n; a single decision gains nothing and typically loses (more nodes to hear from, more tail latency). Consensus throughput is flat-to-declining in n — the replicas are there for **availability**, not speed. ### The boundary — reads can scale out; it's the consensus *writes* that pay the majority This cost falls on **decisions** — the consensus writes that must be linearizable. Reads don't have to: served from a single leader (or a leader lease), reads scale out across replicas without a quorum round-trip, which is exactly how real systems get read throughput from extra nodes while write throughput stays flat. And the majority cost can be *reduced* but not removed: a **witness / voting-only** node contributes an ack without storing data (cheaper majorities), and **flexible quorums** let you shrink the write quorum if you grow the read quorum to keep the overlap — but *some* two sets must still intersect, so the fundamental "one side of a partition waits" never goes away. ### Go deeper 1. **Even split.** Set n = 4 and partition 2–2. Predict how many sides can decide, then confirm *neither* reaches majority (3) — the whole cluster stalls. This is why production clusters keep n odd. 2. **Dueling proposers.** Let two nodes on the *same* side propose different values concurrently and watch single-decree consensus livelock. This is the problem Raft/Paxos solve by electing one stable leader so only it proposes — read Raft §5 (leader election) and see why a leader turns a race into a queue. 3. **Flexible quorums.** Split the ack requirement into a write quorum `Qw` and a read quorum `Qr` with `Qw + Qr > n`, then shrink `Qw` below the majority and see reads still overlap every committed write — the generalization behind `w + r > n` and why "majority" is just the symmetric special case.