CAP Made Countable: a Partition Costs You 12 Refusals or 3 Conflicts

Two regions, one inter-region link, the same workload replayed twice. Cut the link and the CP (single-leader) deployment keeps every replica consistent but the follower side refuses 12 of 20 requests; the AP (multi-leader) deployment serves all of them but 3 keys diverge and must be reconciled on heal. You don't “pick 2 of 3” — the partition happens either way, and you only choose availability XOR consistency while it lasts.

Concept

You do not "pick 2 of 3." Two regions, R1 and R2, each a client and a replica, joined by one inter-region link. The link goes down — a partition, an event imposed on you, not a setting you toggled. Replay the same fixed workload against two deployments of the same two regions: (a) CP — single-leader, the leader in R1; and (b) AP — multi-leader, both regions write locally. While partitioned, the CP deployment keeps every replica consistent but R2 (the non-leader side) must refuse every write and linearizable read — 12 of 20 requests turned away, zero divergence. The AP deployment serves every request at both regions — 0 refusals — but the two states drift apart, and on heal 3 keys conflict and need reconciliation. Same partition, same workload; you chose availability XOR consistency, and each choice cost something countable.

Provenance

Designing Data-Intensive Applications, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 10 — Consistency and Consensus, §"The Cost of Linearizability" / §"The CAP theorem" / §"The Unhelpful CAP Theorem". The claim under test, paraphrased:

When a network partition occurs, a system must choose between linearizability and availability — it cannot have both while the partition lasts.

The book is emphatic that CAP is not "pick two of Consistency, Availability, Partition tolerance." Partitions are a fault you cannot opt out of; the theorem only forces a choice — consistent OR available — while a partition is happening. Here you build the two regions, cut the link, and measure both costs.

Prerequisites

The surprise is that "partition tolerance" is not a thing you choose — the partition chooses you, and then you pay one of two measurable bills. Each line notes where it shows up.

1. Linearizability — the strong-consistency model where every read returns the most recent write, as if there were a single copy. A follower cut off from the leader cannot promise this, which is why R2 must refuse linearizable reads in the CP run.
2. The CAP theorem's actual statement — under a network Partition you get Consistency or Availability, not both; it says nothing about a partition-free system. It shows up as the two deployments giving up opposite things during the same outage.
3. Single-leader vs multi-leader replication — one writable copy (all writes funnel to the leader) versus many (every region writes locally). This is the CP/AP switch: single-leader ⇒ CP, multi-leader ⇒ AP.
4. "CA" is not a real operating point — you can't choose to not tolerate partitions; a partition still happens, and a "CA" system just fails when it does. There is no third column to pick, only C-or-A once the partition is here.

Mental model

A partition is an event imposed on you, not an option. Once the link is down, the same two regions behave differently depending only on how writes are routed.

• CP — refuse service on the wrong side to stay consistent. The leader is in R1. R2 is a follower; with the leader unreachable it cannot accept writes (no one to order them) and cannot serve linearizable reads (it can't confirm it holds the latest). So it refuses them. It may still answer stale reads from its own frozen copy. Consistency is preserved — only the leader ever wrote, so nothing diverges — at the cost of availability on R2.
• AP — serve everywhere and reconcile later. Both regions are leaders; each answers every request from its local replica. Nothing is refused. But each side writes without the other seeing it, so their states diverge; on heal, any key written on both sides with different values is a conflict to reconcile.

Both deployments face the identical partition and replay the identical workload. The whole thing is one script, code/cap_partition_tradeoff.py.

Setup

cd study/ddia/ch10/code
python3 cap_partition_tradeoff.py

Do not read the output yet — make each prediction first.

What you should see

• Step 1: the partition is imposed on both deployments — 23 requests arrive during an outage neither chose.
• Step 2 (CP): 12 of 20 R2 requests refused (7 writes + 5 linearizable reads); 8 stale reads served (one returns v0, behind the leader); 0 keys diverged.
• Step 3 (AP): 0 of 23 refused; 3 keys (x, y, z) diverged and need reconciliation.
• Step 4: CP = {refused 12, diverged 0}; AP = {refused 0, diverged 3}. No deployment paid neither cost.

Why

From first principles: while the link is down, R2 is a node that has lost contact with the rest of the system. Ask it to honor a write or a linearizable read and it is trapped between two things it cannot both do — (i) answer with the latest value, which it may not have, since a newer write could exist on the far side of the partition it cannot see; and (ii) answer at all. It can guarantee at most one. If it insists on (i), correctness, it must sometimes refuse to answer — that is CP, and the refusals are the 12 requests R2 turned away. If it insists on (ii), always answering, it must sometimes answer with a value that another region has concurrently overwritten — that is AP, and the divergence is the 3 keys both sides wrote. There is no third door, because the node genuinely does not know what happened on the other side of the cut. Gilbert & Lynch's proof is exactly this impossibility formalized; the script just makes each horn of it countable.

Notice the two costs are duals of the same fact. CP refuses R2's writes, so only the leader ever mutates state, so on heal there is nothing to reconcile — 0 divergence is bought with 12 refusals. AP accepts every write, so nothing is refused, so both sides advance x, y, z independently — 0 refusals is bought with 3 conflicts. Move the cost from one column and it reappears in the other; you never make it disappear, because the partition — the thing that severed R2 from the truth — was never yours to remove.

Go deeper

• PACELC — the else-case. CAP only speaks about the partition. PACELC adds: Else (no partition), you still trade Latency against Consistency. Make R2's linearizable reads in the healthy case pay a round-trip to the leader and measure the added latency; that is the "EL vs EC" knob CAP is silent about, and it's the trade you actually pay 99.9% of the time.
• Reconcile the AP conflicts. Add a merge step on heal — last-write-wins by region-stamped timestamp, then a version-vector sibling set — and watch LWW silently drop one region's write while the version vector preserves both as conflicts for the app to resolve (the Ch. 6 CRDT/sibling machinery).
• Shrink the minority. Make R2 a 1-node minority of a 5-node CP cluster whose other 4 nodes are on R1's side. Predict which side keeps serving writes (the majority that can still form a quorum) and confirm the minority is the side that must refuse — CP availability follows the quorum, not the geography.

Sources: DDIA 2e, Ch. 10, §"The Cost of Linearizability", §"The CAP theorem", §"The Unhelpful CAP Theorem" · Gilbert & Lynch, "Brewer's Conjecture..." (2002) · Brewer, "CAP Twelve Years Later" (2012).