CAP and PACELC

The previous lesson measured the cost of strong consistency as 10 turns of ack per write and closed on the note that this number is paid even while the cluster is healthy. This lesson opens that note. The second matter it takes up is a misstatement: when distributed stores are discussed, a store is said to be “CP” or “AP,” as if that were a product property.

The CAP theorem’s three letters and PACELC’s two branches were defined in the Introduction to System Design course; the same split scenario was run under two policies, stale responses and rejected requests were counted, the non-split latency trade-off was measured, and the theorem’s common misreadings were sorted out. Those definitions and that discussion are not repeated here. The work here is to apply that same measurement layout to a store’s setting and count where the label actually belongs.

The Label Belongs to the Setting, Not the Product

The previous three lessons showed the same thing over and over: write concern, read concern, and read direction are settings that can be given per request. If a store supports all of these settings, giving that store a single classification is a category error. The class is a property of the running request, not the store.

Testing this is direct: same cluster, same split, same code, only the setting changes. If the class name changes, the label belongs to the setting.

The Mechanism

NS23 — the split lasts 16 turns and divides the cluster in two: two members on the branch side, three on the central side. Reason: the branch is connected to the central site by a single link, and when that link breaks, the two branch members are left alone. NS24 — a primary that loses contact with the majority steps itself down after a timeout; this is 3 or 12 turns. Reason: how long a primary keeps accepting writes after losing majority contact is a setting. The second assumption’s effect is linear and is shown in the table with two values.

// cap/model.mjs — the split is a MODEL: a turn is an abstract step, member distance and the
// split window are parameters in turns, no real network is built. A five-member replica set
// splits in two: u0 (the current primary) and u1 on the branch side, u2, u3, u4 on the central
// side. The branch client can never reach the central side. SAME CLUSTER, SAME CODE — only the setting changes.
export const DELAY = [0, 3, 5, 6, 8], MEMBERS = 5, MAJORITY = 3;
export const TURNS = 40, SPLIT = [11, 26], DETECTION = 2, ELECTION = 2;
const RANKED = DELAY.slice(1).slice().sort((a, b) => a - b);
export const ackTurns = (w) => (w <= 1 ? 0 : 2 * RANKED[w - 2]);

export function run({ w, read, stepDown = 3, split = true }) {
  const s0 = split ? SPLIT[0] : TURNS + 1, s1 = split ? SPLIT[1] : TURNS + 1;
  const down = s0 + stepDown;                 // a primary that loses majority contact steps itself down
  const electAt = s0 + DETECTION + ELECTION;  // the central side elects its own primary
  const ack = ackTurns(w);
  const writtenAt = [0];                      // seq -> the turn it was written (branch side)
  let seq = 0, branchAccepted = 0, branchRejected = 0, centralAccepted = 0, provisional = [];
  let answered = 0, stale = 0, noResponse = 0, staleness = 0, wait = 0;

  for (let t = 1; t <= TURNS; t += 1) {
    const splitNow = t >= s0 && t <= s1;
    // branch write: one loan record per turn, always sent to that side's own primary
    const primaryUp = splitNow === false || t < down;
    const wOk = splitNow === false || w <= 1;   // the minority side can never assemble a majority
    if (primaryUp && wOk) {
      seq += 1; writtenAt[seq] = t; branchAccepted += 1; wait += ack;
      if (splitNow) provisional.push(seq);      // accepted in the minority: rolled back at rejoin
    } else branchRejected += 1;
    if (splitNow && t >= electAt) centralAccepted += 1; // the central side elects its own primary and keeps writing

    // branch read: a local concern is answered by that side's own secondary; a majority concern
    // cannot be confirmed on the minority side, so it goes unanswered
    if (read === "majority" && splitNow) { noResponse += 1; continue; }
    const seen = read === "majority"
      ? writtenAt.findLastIndex((x) => x + ackTurns(MAJORITY) <= t)
      : writtenAt.findLastIndex((x) => x + DELAY[1] <= t);
    answered += 1;
    if (seen < seq) {
      stale += 1;
      if (seen >= 1) staleness = Math.max(staleness, t - writtenAt[seen]);  // not yet counted if there is no record
    }
  }
  return { branchAccepted, branchRejected, rolledBack: provisional.length, centralAccepted,
    answered, stale, noResponse, staleness, wait, ack };
}

// cap/measure.mjs — same cluster, same split, four settings; then the same four settings with NO split
import { run, ackTurns, DELAY, SPLIT, TURNS, MAJORITY } from "./model.mjs";

const s = (x, n) => String(x).padStart(n);
const SETTING = [
  ["w=majority · majority", { w: MAJORITY, read: "majority" }],
  ["w=1 · local (step-down 3)", { w: 1, read: "local", stepDown: 3 }],
  ["w=1 · local (step-down 12)", { w: 1, read: "local", stepDown: 12 }],
  ["w=majority · local", { w: MAJORITY, read: "local" }],
];
const window = SPLIT[1] - SPLIT[0] + 1;
console.log(`${TURNS} turns, member distance ${DELAY.join("/")}. The link is cut on turns ${SPLIT[0]}-${SPLIT[1]}`);
console.log(`(${window} turns): u0 and u1 on the branch side, u2, u3, u4 on the central side.`);
console.log("One loan write and one catalog read arrive at the branch side every turn.\n");
console.log("setting                   | branch write accepted | rejected | rolled back | central write | read answered | stale | no response");
console.log("---------------------------|------------------------|----------|-------------|---------------|---------------|-------|------------");
for (const [name, p] of SETTING) {
  const r = run(p);
  console.log(`${name.padEnd(26)} | ${s(r.branchAccepted, 22)} | ${s(r.branchRejected, 8)} | ${s(r.rolledBack, 11)} | ` +
    `${s(r.centralAccepted, 13)} | ${s(r.answered, 13)} | ${s(r.stale, 5)} | ${s(r.noResponse, 10)}`);
}

console.log("\nsame four settings, with NO split at all:");
console.log("setting                   | ack turns | total wait | staleness window | stale reads | no response");
console.log("---------------------------|-----------|------------|-------------------|-------------|------------");
for (const [name, p] of SETTING) {
  const r = run({ ...p, split: false });
  console.log(`${name.padEnd(26)} | ${s(r.ack, 9)} | ${s(r.wait, 10)} | ${s(r.staleness + " turns", 17)} | ` +
    `${s(`${r.stale}/${r.answered}`, 11)} | ${s(r.noResponse, 10)}`);
}

console.log("\nindependent of the run: the minority side keeps 2 members, majority threshold " +
  `${MAJORITY};`);
console.log("2 < 3 means that side can never assemble a majority under any setting — this is not a setting");
console.log(`outcome, it is the cluster size's. Majority ack turns ${ackTurns(MAJORITY)}, local ack turns ${ackTurns(1)}.`);

40 turns, member distance 0/3/5/6/8. The link is cut on turns 11-26
(16 turns): u0 and u1 on the branch side, u2, u3, u4 on the central side.
One loan write and one catalog read arrive at the branch side every turn.

setting                   | branch write accepted | rejected | rolled back | central write | read answered | stale | no response
---------------------------|------------------------|----------|-------------|---------------|---------------|-------|------------
w=majority · majority      |                     24 |       16 |           0 |            12 |            24 |    24 |         16
w=1 · local (step-down 3)  |                     27 |       13 |           3 |            12 |            40 |    29 |          0
w=1 · local (step-down 12) |                     36 |        4 |          12 |            12 |            40 |    38 |          0
w=majority · local         |                     24 |       16 |           0 |            12 |            40 |    26 |          0

same four settings, with NO split at all:
setting                   | ack turns | total wait | staleness window | stale reads | no response
---------------------------|-----------|------------|-------------------|-------------|------------
w=majority · majority      |        10 |        400 |          10 turns |       40/40 |          0
w=1 · local (step-down 3)  |         0 |          0 |           3 turns |       40/40 |          0
w=1 · local (step-down 12) |         0 |          0 |           3 turns |       40/40 |          0
w=majority · local         |        10 |        400 |           3 turns |       40/40 |          0

independent of the run: the minority side keeps 2 members, majority threshold 3;
2 < 3 means that side can never assemble a majority under any setting — this is not a setting
outcome, it is the cluster size's. Majority ack turns 10, local ack turns 0.

Same Cluster, Four Settings, Four Behaviors

The first table carries this lesson’s argument on its own. All four rows use the same cluster, the same 16-turn split, and the same code; the only thing that differs is the setting, and four different behaviors come out.

Row one chooses consistency: 16 writes on the branch side were rejected, 16 reads went unanswered, and 0 writes were rolled back. Row two chooses availability: no read went unanswered, the branch accepted 3 more writes — and those 3 writes were rolled back at rejoin.

The relationship between the two rows is an exact equality, and it is no coincidence: every acceptance won on the minority side is a write that gets rolled back. 27 − 24 = 3, and in row three, 36 − 24 = 12. Raising the step-down timeout from 3 turns to 12 accepted 9 more writes and rolled back exactly 9 more. Availability here is not a trade-off but a trade: the exchange rate is one to one, and the setting itself does not set the rate, only the volume.

Row four settles the label debate. Under w=majority combined with a local read, the write path behaves like row one — 16 rejections, 0 rolled back — and the read path behaves like row two: 40 answers, 0 unanswered. One store, one cluster, one setting; consistency on writes, service availability on reads. This row cannot be given a single-letter class. The class belongs to the path the operation takes.

The central-write column reads 12 in all four rows, and it closes another misunderstanding. The store did not stop during the split; the central side assembled its majority, elected its own primary, and kept writing. The 16 rejected writes are what the client on the minority side sees, not what the store does. A classification has to say whose vantage point it is taken from.

A Choice Is Made Even Without a Split

The second table gives the run where the link is never cut, and the four rows diverge there too.

The two w=majority settings waited 400 total turns across 40 turns; the two w=1 settings waited 0. Those 400 turns have nothing to do with the split — they were spent, on every write, waiting for a majority acknowledgement to come back while the link was perfectly healthy. Likewise, the staleness window is 10 turns for a majority read and 3 for a local read, and that difference too was measured with no split at all.

Row four stays mixed here too: 400 turns waited on the write path, a 3-turn staleness window on the read path. The setting does not fit a single letter on the non-split branch any more than it did on the split branch.

Setting	Under the split (P branch)	Outside the split (E branch)	Measured
w=majority · majority	consistency	consistency	16 rejected, 16 unanswered; 400 wait turns, 10-turn staleness
w=1 · local, step-down 3	availability	latency	0 unanswered, 3 rolled back; 0 wait, 3-turn staleness
w=1 · local, step-down 12	availability	latency	0 unanswered, 12 rolled back; 0 wait, 3-turn staleness
w=majority · local	consistency on writes, availability on reads	consistency on writes, latency on reads	16 rejected but 0 unanswered; 400 wait, 3-turn staleness

In library operations, this table translates directly into a configuration. The loan-writing operation takes row one’s setting: when the link breaks, the branch cannot lend books, but no loan record is ever later disregarded. The catalog search takes row four’s read side: it keeps answering even when the link breaks, accepting a three-turn staleness. Both decisions are made on the same cluster, over the same collection, with separate requests.

What Is Structural and What Depends on the Setting

Not everything is a setting, and missing that distinction is a second misstatement. The final block’s line is independent of the run: the minority side is left with two members, the majority threshold is three, and because 2 < 3, that side can never assemble a majority under any setting. This is not the result of a policy but of the cluster size and where the split falls. That is what a setting cannot change; what it can change is how long that side keeps accepting writes.

This same distinction lines up with the first lesson’s result: there, in the three-member cluster where two members dropped, no election ever started, and the surviving member’s data currency did not change that. Structural bounds sit above the setting table; the setting table can only produce a decision inside the space that bound allows.

Summary

• The same cluster, the same 16-turn split, and the same code produced four different behaviors under four settings; the class name is a property of the setting and the operation’s path, not the store.
• Every acceptance won on the minority side is a write that gets rolled back: raising the step-down timeout from 3 to 12 turns took accepted writes from 27 to 36 and rolled-back writes from 3 to 12 — a difference of 9 in both columns.
• The w=majority + local read combination chose consistency on the write path (16 rejected, 0 rolled back) and service availability on the read path (40 answered, 0 unanswered); this row cannot be given a single-letter class.
• During the split, the central side accepted 12 writes under all four settings: the store did not stop — what stopped was the service the minority-side client saw.
• A choice was paid for even without any split: the w=majority settings waited 400 turns across 40 turns, the majority read’s staleness window came out at 10 turns, the local read’s at 3.
• There is a bound no setting can change: the minority side is left with two members while the majority threshold is three, and because 2 < 3, that side can never assemble a majority under any setting.

Next Step

Throughout this topic, every decision the cluster made was measured as a setting: how many members would acknowledge, where a read would go, how long a primary keeps accepting writes after losing majority contact. Everything measured shared one assumption that was never stated: that the sender of the request was authorized to make it. In the model, every write that reached the cluster wrote a loan record, every read got an answer; who the request came from was never asked. In a real deployment this is the first question asked, and its answer is a configuration too — one whose default is the most dangerous kind. The next lesson takes up the store’s authentication, role-scope, and encryption settings: what a deployment with authorization turned off is exposed to, what narrowing a role’s scope down to the collection level buys, and what cost transport and at-rest encryption each add.