System Design · Module 5

Consistency Models: Linearizability, CAP, and PACELC

CAP proves an impossibility that only applies during a network partition; it says nothing about the far more common case where the network is fine. PACELC fixes that by making the every-day latency-versus-consistency trade a first-class, separate decision. After this module you can classify any storage system in this course — Bigtable, Dynamo, Spanner, ZooKeeper, PNUTS — as PA/EL, PC/EC, or PC/EL, and predict its behavior both during and absent a partition.

Course 35 min read 11 sources As of 2026-09-17 Prerequisite: Module 3, Module 4
PACELC decision tree with Dynamo, Spanner, and PNUTS placed on it Is there a partition right now? yes (P) no (E, else) Availability (A) or Consistency (C)? Latency (L) or Consistency (C)? A C L C PA/EL PC/EL PC/EL PC/EC Dynamo Cassandra, Riak always writeable PNUTS record-level mastering async replicate, CP on partition Spanner Megastore, VoltDB/H-Store TrueTime + 2PC over Paxos Two independent axes: what a system gives up during a partition (P), and what it gives up the rest of the time (E, "else") PA/EC is empirically near-absent — trading availability away during a partition but latency away absent one has little motivation
Figure 1. PACELC asks two separate questions instead of CAP's one: during a partition (P), does the system choose availability (A) or consistency (C); absent a partition (E, "else"), does it choose latency (L) or consistency (C)45. Dynamo is PA/EL by explicit design target7; Spanner is PC/EC, paying TrueTime commit-wait and cross-group consensus on every write whether or not anything is partitioned6; PNUTS defaults to PC/EL — it trades consistency for latency in normal operation but reverts to protecting consistency, not availability, once a partition actually occurs8.

1. Linearizability: the guarantee CAP's "C" actually means

Every discussion of CAP and PACELC leans on a word — "consistency" — that means something different in every other context you have encountered it. It is not ACID consistency (Module 4's invariant-preservation property) and it is not the "eventual consistency" marketing term. The consistency in CAP is linearizability, a precise correctness condition for a single object shared by concurrent processes, defined by Herlihy and Wing in 1990 specifically so it could be reasoned about with the same techniques used for sequential programs1.

1.1 The formal definition: L1 and L2

Herlihy and Wing model a concurrent system as a history: a sequence of operation invocation and response events, each tagged with a process1. A history induces a partial order \(<_H\) on operations: \(e_0 <_H e_1\) if the response of \(e_0\) precedes the invocation of \(e_1\)1 — this is the "real-time" precedence the rest of this section keeps referring to. A history \(H\) is linearizable if it can be extended, by appending zero or more pending responses, to a history \(H'\) such that two conditions hold1:

  • L1: complete(\(H'\)) is equivalent to some legal sequential history \(S\) — i.e., there exists some valid reordering of the completed operations that respects the object's own sequential semantics.
  • L2: \(<_H \subseteq <_S\) — that reordering does not violate any real-time ordering already present in \(H\): if operation A finished (in real time) before operation B started, S must not place B before A.

Read informally, this says exactly what the intuitive story about linearizability always says — "each operation appears to take effect instantaneously at some point between its invocation and its response"1 — but L1/L2 is the version you can actually prove things about. The paper's own FIFO-queue and register examples are worth internalizing because CAP's proof (§2) reuses exactly this apparatus: a history where B reads the value 1 after A already read a 1 that B itself wrote is not acceptable, because to be consistent with real-time order, B's write of 1 must be placed before A's read of 1 in any legal serialization, yet C's later write of 0 (concurrent with B's write) must still come after A's read — over-constraining the reordering until no legal sequential history satisfies both conditions1.

Two properties of linearizability matter for everything that follows in this module. It is local: a system composed of several linearizable objects is itself linearizable, so you can reason about one key at a time1. And it is nonblocking in the sense that a pending invocation is never required to wait for a later operation to be issued before it can be linearized — "processes invoking totally-defined operations are never forced to wait," which the authors note makes it "an appropriate condition for systems for which real-time response is critical"1. Neither property is optional scaffolding; both are exactly what a distributed implementation has to reproduce to call itself linearizable, and both are what start to break the moment you replicate the object across machines that cannot instantaneously agree on order.

1.2 Why it is a different axis from the serializability Module 4 covered

Module 4 covered isolation levels — read committed, snapshot isolation, serializable — as properties of multi-operation transactions touching possibly many objects, concerned with which anomalies (dirty reads, write skew, phantoms) a given level still permits. Linearizability is orthogonal: it is a property of individual operations on a single object, concerned only with whether those operations respect real-time order. A system can be serializable (transactions behave as if run one at a time, in some order) without being linearizable (that order can disagree with real, wall-clock arrival order) — this is exactly why Module 4's isolation ladder and this module's consistency ladder are two different papers' worth of vocabulary, not one relabeled. A single-key read in a linearizable store is the strongest possible guarantee for that one key: whatever the most recent completed write was, in real time, a subsequent read must see it or something newer. This is the guarantee Gilbert and Lynch chose to formalize CAP's "C" around, and the reason: it is the guarantee that is hardest to keep during a partition, so it makes the strongest, cleanest theorem2.

Two operation histories on a register, one linearizable and one not History H₁ — linearizable t W(0) A R(0) B B's read starts after A's write finished — real-time order forces R to see 0. It does. Legal. History H₂ — not linearizable t W(1) A R(0) B B's read starts after A's write of 1 finished, but returns the stale value 0. No sequential reordering can satisfy L2: A's write must precede B's read (real-time), yet B's read result (0) requires the opposite. Not linearizable — the shape of a stale-replica read after a partition heals.
Figure 2. A linearizable history (top) versus one that violates real-time order (bottom), following Herlihy and Wing's history-and-partial-order apparatus1. The bottom pattern — a read that starts after a write's real-time completion but returns the pre-write value — is exactly the anomaly a replica lagging behind a leader, or a client reading from the wrong side of a healed partition, produces.

2. The CAP theorem: what Gilbert and Lynch actually proved

Eric Brewer conjectured, in an invited talk at PODC 2000, that a web service cannot simultaneously provide consistency, availability, and partition tolerance2. Gilbert and Lynch's 2002 note gave that conjecture a formal model and a proof2. The proof is short, and it is worth walking through directly, because almost every misunderstanding of CAP traces back to skipping it and working from the "2 of 3" slogan instead.

2.1 The formal model: three definitions, precisely stated

Gilbert and Lynch define their three terms as narrowly as possible, on purpose2:

  • Consistency is atomic consistency, which they note is equivalent to linearizability2 — Section 1's L1/L2, applied to a read/write register: "there must exist a total order on all operations such that each operation looks as if it were completed at a single instant," with the property that "any read operation that begins after a write operation completes must return that value, or the result of a later write operation"2.
  • Availability means "every request received by a non-failing node in the system must result in a response"2 — eventually, with no bound on how long, which the authors call a weak definition in isolation but a strong one once partition tolerance is also required, "since even when severe network failures occur, every request must terminate"2.
  • Partition tolerance is modeled by allowing the network to lose arbitrarily many messages between two disjoint, non-empty node sets, with "any pattern of message loss" reducible to this model2.

Notice what is not in these definitions: nothing about latency, nothing about how the system behaves when the network is fine, and nothing weaker than 100% availability — Brewer's original talk allowed "almost all" requests to succeed, but Gilbert and Lynch simplify to 100% because allowing probabilistic availability does not change the result under arbitrary failures2. Every one of PACELC's later refinements (Section 4) comes from restoring one of these deliberately narrowed corners.

2.2 The impossibility proof, sketched

Theorem 1 states it plainly: "It is impossible in the asynchronous network model to implement a read/write data object that guarantees... availability [and] atomic consistency... in all fair executions (including those in which messages are lost)"2. The proof is a contradiction built on a partition into two groups \(G_1\) and \(G_2\)2:

  1. Let \(\alpha_1\) be an execution prefix in which a single write (of a value \(\neq v_0\)) happens in \(G_1\) and completes — by the availability requirement, it must complete, since no messages from \(G_1\) reach \(G_2\) during this prefix and vice versa.
  2. Let \(\alpha_2\) be a separate execution prefix in which a single read happens in \(G_2\), with no write having occurred in \(G_2\) — by availability, this read also completes, and because no write has occurred in this prefix, it must return the initial value \(v_0\).
  3. Concatenate \(\alpha_1\) then \(\alpha_2\) into one execution \(\alpha\). To the nodes in \(G_2\), \(\alpha\) is indistinguishable from \(\alpha_2\) alone, because every message from \(G_1\) to \(G_2\) is lost in both. So the read in \(\alpha\) still returns \(v_0\) — even though, in real time, it started after \(\alpha_1\)'s write had already completed.
  4. That is a direct violation of atomic consistency's real-time requirement (Section 1.1's L2): a read that starts after a write's completion returned the pre-write value. Contradiction — no such algorithm exists2.

The proof depends on nothing about clocks, quorums, or specific algorithms — it depends only on the fact that in the asynchronous model, a node in \(G_2\) has no way to distinguish "the message from \(G_1\) was lost" from "the message from \(G_1\) hasn't arrived yet, but will." That is precisely why a system with an unbounded number of possible network delays cannot use a timeout to safely tell the two cases apart, and why Corollary 1.1 extends the result even to executions where messages are merely delayed, not actually dropped2.

2.3 The three pairwise-achievable systems

Because the theorem only rules out all three simultaneously, Gilbert and Lynch also show each pair is separately easy2:

  • CP (consistent, partition-tolerant, not always available): a single designated node holds the value; if it becomes unreachable, requests to it simply do not get a response. "Many distributed databases provide this type of guarantee, especially algorithms based on distributed locking or quorums"2.
  • CA (consistent, available, not partition-tolerant): the same centralized algorithm works fine as long as no partition actually happens — "systems that run on intranets and LANs are an example"2. This is the quadrant traditional single-datacenter relational databases occupy: they are not proven wrong by CAP, they simply never faced the partition CAP is about.
  • AP (available, partition-tolerant, not consistent): if there are no consistency requirements at all, the trivial service that always answers with the last value it has, or even the initial value \(v_0\), is available and partition-tolerant2. Real AP systems, obviously, do much better than the trivial case — Dynamo's whole design (Section 7) is the engineering required to make "available, partition-tolerant, not linearizable" still useful.

The theorem's actual content, stated precisely, is this: if a partition occurs, then a system relying on linearizable reads/writes must choose between answering (and risking inconsistency) or refusing to answer (and losing availability) for the affected data. It says nothing at all about what a system should do the other 99.9%+ of the time when the network has not partitioned — and that silence is exactly Section 3's subject.

3. CAP's blind spot: what the theorem is silent about

Twelve years after his conjecture, Brewer published a retrospective making the same point this module is building toward: the "2 of 3" framing "was always misleading because it tended to oversimplify the tensions among properties," and "CAP prohibits only a tiny part of the design space: perfect availability and consistency in the presence of partitions, which are rare"3. Practitioners who read CAP as license to design their steady-state system around whichever letter they dropped were reading it for a claim it never made.

3.1 Why "2 of 3" is a misreading

Brewer gives three specific reasons the binary framing breaks down3:

  • Partitions are rare, so there is little reason to forfeit C or A when the system is not partitioned. The theorem is a statement about a contingency, not a permanent posture.
  • The choice between C and A can happen many times within the same system, at fine granularity — "not only can subsystems make different choices, but the choice can change according to the operation or the specific data or user involved"3. A store that refuses writes to an unreachable shard while continuing to serve reads from a healthy one is not cleanly "CP" or "AP"; it is both, at different granularity.
  • All three properties are more continuous than binary. Availability is a percentage, not a bit; consistency has "many levels... including disagreement within the system about whether a partition exists" at all3 — a claim that maps directly onto Module 11's SLO vocabulary two modules ahead.

Brewer's own recommended discipline is to treat a partition as a first-class event with three explicit phases: detect the start of a partition, enter an explicit partition mode that may limit some operations, and initiate recovery when communication is restored, which must both merge the states that diverged on each side and "compensate for any mistakes made during the partition"3. His own diagram of this process — consistent state \(S\), diverging into inconsistent \(S_1\)/\(S_2\) once partition mode begins, merging back into consistent \(S'\) once recovery completes3 — is the template every AP system in this course quietly implements: Dynamo's vector clocks (Module 3) are exactly the bookkeeping needed to make the \(S_1\)/\(S_2\) merge in that diagram well-defined instead of a guess.

3.2 Two systems, both "CP," behaving differently absent a partition

Here is the blind spot made concrete. Classify a system as CP if, when a minority of replicas becomes unreachable, that minority refuses to serve linearizable reads or writes rather than risk returning a stale or divergent answer. By that test, Spanner and ZooKeeper are both CP: a Spanner Paxos group that has lost its majority cannot commit a write (or serve an up-to-date read) on the affected data6, and ZooKeeper's write path is explicitly linearizable via its Zab atomic-broadcast protocol, which likewise requires a majority810. During an actual partition, an outside observer watching only the minority side cannot tell these two systems apart: both simply stop answering for the affected keys.

Absent a partition, they could not be more different. Spanner assigns every read-write transaction a commit timestamp and then makes the coordinator wait — commit-wait, detailed in Section 5 — until that timestamp is definitely in the past, guaranteeing external consistency on every single write, all the time, not only when something is wrong6. ZooKeeper takes the opposite stance on the read path specifically: "We show for the target workloads, 2:1 to 100:1 read to write ratio, that ZooKeeper can handle tens to hundreds of thousands of transactions per second," which is only possible because "reads are served locally by any server and are not linearized"8 — a client can read a value from a follower that a write has already superseded elsewhere, deliberately, to keep read latency at the cost of a single local hop rather than a quorum round trip. CAP's binary label calls both systems "CP." PACELC's second axis tells you Spanner is PC/EC (pays for consistency always) while ZooKeeper's read path is closer to PC/EL (pays for consistency only on writes, trades it for latency on reads) — the distinction the first theorem cannot express at all.

Spanner and ZooKeeper both classified CP by CAP, diverging under PACELC's else-branch During a partition — CAP sees these as identical Spanner, minority Paxos group no quorum → write/strong-read refused ZooKeeper, minority side no Zab quorum → write refused both: CP Absent a partition — PACELC's else-branch tells them apart Spanner: every write 2PC across Paxos groups + TrueTime commit-wait every read: externally consistent EC — pays latency always ZooKeeper: reads served locally by any replica not linearized (writes still are) tens-hundreds of thousands ops/sec EL on reads — trades C for latency
Figure 3. Spanner and ZooKeeper are indistinguishable under CAP's binary test during a partition — both refuse service to a minority side rather than risk an inconsistent answer68. Absent a partition, PACELC's else-branch separates them: Spanner pays cross-group consensus plus TrueTime commit-wait on every operation to stay externally consistent at all times6; ZooKeeper deliberately serves reads from any single replica, unlinearized, to sustain the 2:1-to-100:1 read-heavy throughput its target workloads need8.

4. PACELC: the framework that fills the gap

Daniel Abadi named the gap in a 2010 blog post — "if there is a partition (P) how does the system tradeoff between availability and consistency (A and C); else (E) when the system is running as normal in the absence of partitions, how does the system tradeoff between latency (L) and consistency (C)?"4 — and formalized it two years later in a peer-reviewed article5. The acronym is pronounced "pass-elk"5, and Figure 1 already showed its shape: two independent binary choices, not one three-way impossibility.

4.1 The formal definition and why it needed a second axis

Abadi's central argument is that CAP has been blamed for a design decision it never made: "it is wrong to assume that DDBSs that reduce consistency in the absence of any partitions are doing so due to CAP-based decision-making. In fact, CAP allows the system to make the complete set of ACID... guarantees alongside high availability when there are no partitions. Therefore, the theorem does not completely justify the default configuration of DDBSs that reduce consistency"5. The real reason systems like Dynamo, Cassandra, and PNUTS reduce consistency even when nothing is partitioned is a separate, always-present tradeoff: "this tradeoff exists even when there are no network partitions, and is thus completely separate from the tradeoffs CAP describes"5 — the consistency/latency tradeoff, which Abadi treats as arguably more influential on real DDBS design than CAP itself, "because it has a more direct effect on the systems' baseline operations," whereas a network partition is comparatively rare5.

4.2 Where the else-branch tradeoff actually comes from

The mechanism is replication, and Abadi walks through exactly three ways to send an update to multiple replicas, each with its own latency cost5:

  1. Send updates to all replicas at the same time. Done synchronously (wait for every replica to acknowledge before returning), this "increase[s] latency due to the requirement to pass messages between... entities and the fact that latency is limited by the slowest entity"5 — and over a WAN, that slowest entity can be a continent away. Done asynchronously with no ordering agreement, replicas can diverge outright unless updates happen to be commutative.
  2. Send updates to an agreed-upon master node first. The master resolves the order, then propagates. If replication onward is synchronous, you get consistency but every write pays at least one extra network hop to reach the master, and reads that must reach the master to avoid staleness inherit that same round trip even from a nearby replica — "even if there is a replica close to the read-request initiator, the system must still route the request to the master node, which potentially could be physically much farther away"5. If replication onward is asynchronous, reads can be served from any replica for lower latency, at the cost of possibly stale answers.
  3. Send updates to whichever node the client happens to reach first, then propagate — the most decentralized option, and the one most exposed to conflicting concurrent updates initiated at two different locations simultaneously, which is exactly Dynamo's normal case (Section 7).

Abadi's conclusion from walking every combination: "for data replication over a WAN, there is no way around the consistency/latency tradeoff"5. This is why the else-branch is not a footnote to CAP — it is a second, independent theorem-shaped constraint that applies to every geographically replicated system, whether or not it has ever seen a partition.

4.3 Classifying real systems

Abadi classifies the well-known DDBSs of 2012 directly, and every system named below already appears somewhere in this course:

Table 1. System classification under PACELC, per Abadi's 2012 formal treatment5 and the primary papers for each system36789.
SystemPartition (P)Else (E)ClassWhy
Dynamo, Cassandra, RiakavailabilitylatencyPA/ELalways-writeable design target7; tunable R+W, typically < N
VoltDB/H-Store, MegastoreconsistencyconsistencyPC/ECfully ACID; pay availability and latency costs to get it5
Bigtable, HBaseconsistencyconsistencyPC/ECsingle-master-per-tablet, Chubby quorum required to elect it9
SpannerconsistencyconsistencyPC/EC2PC over Paxos groups plus TrueTime commit-wait on every write6
PNUTSconsistencylatencyPC/ELasync cross-region replication for latency; refuses writes to an unreachable master rather than resolve conflicting masters5
MongoDB (default)availabilityconsistencyPA/ECelects a new master on failure (A), but old/new master states can briefly diverge and must reconcile via rollback — an unusual quadrant5
ZooKeeper (writes / reads)consistencyconsistency / latencyPC/EC & PC/ELZab-linearized writes require quorum; reads served locally, unlinearized8

The empirically missing quadrant is PA/EC — give up availability during a partition and latency absent one, for no consistency benefit at all. Abadi notes MongoDB's default configuration is the closest real example to a non-obvious quadrant (PA/EC), precisely because "giving up Cs in PACELC makes the design simpler; once a system is configured to handle inconsistencies, it makes sense to give up consistency for both availability and lower latency" — meaning most systems that give up one C tend to give up the other too, which is exactly Abadi's original 2010 observation restated45. Sections 5 and 6 now take Spanner's and PNUTS's rows in Table 1 and show the actual mechanism behind each classification.

5. Spanner's answer: TrueTime and externally consistent commit-wait

Module 4 already introduced Spanner's two-phase commit over Paxos groups as the mechanism behind general cross-row transactions6. This section covers the piece that makes those transactions externally consistent — Spanner's own, stronger term for a linearizability guarantee that spans the whole database, not just one object — rather than merely serializable: "if the start of a transaction \(T_2\) occurs after the commit of a transaction \(T_1\), then the commit timestamp of \(T_2\) must be greater than the commit timestamp of \(T_1\)"6. Enforcing that invariant across machines that do not share a clock is what TrueTime is for.

5.1 The TrueTime API: an interval, not an instant

A normal clock API returns a single timestamp and hides its own error. TrueTime does the opposite: TT.now() returns a TTinterval — a pair \([\mathit{earliest}, \mathit{latest}]\) — guaranteed to bracket the true absolute time at which the call happened6. Formally, for an invocation \(tt = TT.now()\), Spanner guarantees \(tt.earliest \le t_{abs}(e_{now}) \le tt.latest\)6. Two convenience wrappers, TT.after(t) and TT.before(t), answer "has \(t\) definitely passed" and "has \(t\) definitely not yet arrived"6.

The width of that interval is driven by \(\epsilon\), the instantaneous error bound (half the interval's width), which Spanner keeps small using two independent physical time references — GPS receivers and atomic clocks — specifically because they fail in uncorrelated ways: "GPS reference-source vulnerabilities include antenna and receiver failures, local radio interference... Atomic clocks can fail in ways uncorrelated to GPS... and over long periods of time can drift significantly due to frequency error"6. A set of time master machines per datacenter hold these references (most with dedicated GPS antennas; the rest, called Armageddon masters, hold atomic clocks alone), and every machine's local timeslave daemon polls a cross-checked sample of masters every 30 seconds, applying Marzullo's algorithm to reject outliers6. Between polls, \(\epsilon\) grows: "\(\epsilon\) is typically a sawtooth function of time, varying from about 1 to 7 ms over each poll interval... \(\bar\epsilon\) is therefore 4 ms most of the time," with the sawtooth's 0-to-6ms climb coming from a conservatively applied worst-case local clock drift rate of 200 microseconds per second of elapsed time, and the remaining roughly 1ms from communication delay to the masters themselves6.

5.2 Commit-wait: the arithmetic

TrueTime alone only tells you an interval containing the truth. Turning that into an ordering guarantee requires one more rule, which Spanner calls commit wait: "the coordinator leader ensures that clients cannot see any data committed by \(T_i\) until \(TT.after(s_i)\) is true," where \(s_i\) is the transaction's assigned commit timestamp6. The proof that this preserves external consistency is a four-line chain6:

$$s_1 < t_{abs}(e_1^{commit}) \quad\text{(commit wait)}$$ $$t_{abs}(e_1^{commit}) < t_{abs}(e_2^{start}) \quad\text{(assumption: }T_2\text{ starts after }T_1\text{ commits)}$$ $$t_{abs}(e_2^{start}) \le t_{abs}(e_2^{server}) \quad\text{(causality)}$$ $$t_{abs}(e_2^{server}) \le s_2 \quad\text{(start rule: coordinator assigns }s_2 \ge TT.now().latest\text{ at that moment)}$$ $$\Rightarrow s_1 < s_2 \quad\text{(transitivity)}$$

The practical consequence: because the coordinator picks \(s_i\) from \(TT.now().latest\) and then must wait until it is certain \(s_i\) is in the past, "the expected wait is typically overlapped with Paxos communication" but is "at least \(2 \bar\epsilon\)"6. With \(\bar\epsilon \approx 4\)ms, that puts commit-wait at roughly 8ms on a healthy cluster — consistent with the paper's own headline claim that TrueTime "keeps uncertainty small (generally less than 10ms)"6. The paper's own microbenchmark corroborates the order of magnitude directly: on a single-replica configuration with commit wait disabled (labeled "1D" in the paper's Table 3), write latency measures 9.4ms; with commit wait enabled on one real replica, write latency rises to 14.4ms — a roughly 5ms difference attributable to commit-wait, in the same range as the \(2\bar\epsilon \approx 8\)ms estimate6.

TrueTime uncertainty interval shrinking and triggering commit-wait release t commit request TT.now() at commit: [earliest, latest], ε ≈ 4-7ms s₁ = latest interval narrows as time advances toward "latest" commit-wait ≥ 2ɛ̄ TT.after(s₁) true release commit ɛ̄ ≈ 4ms typical (sawtooth 1-7ms between 30-second polls) ⇒ commit-wait ≈ 8ms, matching Spanner's measured ~5ms 1-replica overhead and its <10ms design target
Figure 4. A Spanner coordinator assigns commit timestamp \(s_1\) at \(TT.now().latest\), then blocks until \(TT.after(s_1)\) is true — waiting out the shrinking uncertainty interval before letting any client observe the commit6. With average error bound \(\bar\epsilon \approx 4\)ms, commit-wait is at least \(2\bar\epsilon \approx 8\)ms6, which is why Spanner's design target is "generally less than 10ms" and its measured single-replica write overhead is about 5ms6.

5.3 Why Spanner pays the EC cost even absent a partition

Nothing about commit-wait depends on whether any Paxos group is currently partitioned. Every read-write transaction pays it, on every healthy commit, because the guarantee being sold is external consistency for the whole database, not merely "consistency during trouble." That is the concrete referent behind Table 1's PC/EC classification for Spanner: partitioned, it chooses consistency over availability exactly like Gilbert and Lynch's CP quadrant predicts2; unpartitioned, it still chooses consistency over the lowest possible latency, because the commit-wait rule and the cross-group two-phase commit round trip are structural, not conditional on failure. The measured cost is not hidden or accidental — Spanner's own evaluation reports it directly, and the paper is explicit that the target market is applications for which this cost is worth paying, not a universal recommendation.

6. PNUTS's answer: record-level mastering, PC/EL by design

PNUTS is the system Abadi cites as the clearest evidence that reduced consistency in normal operation is a latency decision, not a CAP-forced one: "PNUTS offers the clearest evidence that CAP is not a major reason for reduced consistency levels in these systems"5. Yahoo built it to back web applications with strict response-time SLAs across geographically dispersed users, where "the database portion of a web request is only 50-100 milliseconds," a budget synchronous cross-continent replication cannot meet8.

6.1 Per-record timeline consistency and the read API ladder

PNUTS's core design decision is to make "all high latency operations asynchronous, and to support record-level mastering. Synchronously writing to multiple copies around the world can take hundreds of milliseconds or more... Asynchrony allows us to satisfy this budget despite geographic distribution, and record-level mastering allows most requests, including writes, to be satisfied locally"8. Concretely: one replica of a given record — not the whole table, a single record — is designated its master, and all writes to that record are forwarded there; the master assigns each write a monotonically increasing sequence number (generation and version), then publishes the update asynchronously to a pub/sub system (the Yahoo Message Broker) for delivery to other regions8. Every replica applies updates to a given record strictly in that record's published order — per-record timeline consistency — so "a read of any replica will return a consistent version from this timeline, and replicas always move forward in the timeline"8, even though different replicas may be at different points along it.

PNUTS exposes that staleness explicitly through a ladder of read calls rather than hiding it behind one "consistency level" knob:

Table 2. PNUTS's read/write API, ordered from lowest latency to strongest guarantee8.
CallGuaranteeLatency position
Read-anya valid but possibly stale version from the record's historylowest — any replica, no check
Read-critical(v)a version ≥ the given version v (e.g. the version you just wrote)higher if local replica is behind
Read-latestthe most recent version that has committed anywherehighest read latency of the three
Writerouted to the record's master; ACID for that single writelocal if requester is near the master, else a WAN hop
Test-and-set-write(v)write succeeds only if current version equals v (optimistic concurrency)same as write; serializes concurrent increments

The read-any call is the deliberate, named escape hatch for the latency/consistency tradeoff: it "provides a way for the application to explicitly indicate, on a per-read basis, that performance matters more than consistency"8 — PACELC's else-branch, exposed as an API parameter rather than a global system setting.

6.2 Why the default configuration is CP during a partition but EL absent one

PNUTS's own measurement of its production workload found extremely high write locality: "a one week trace of updates to 9.8 million user records in Yahoo!'s user database showed that on average, 85 percent of the writes to a given record originated in the same datacenter"8 — which is exactly the empirical fact that justifies mastering by record rather than by table or by partition: most records rarely need their master to move at all. But mastership assignment is adaptive, not static: "the replica receiving the majority of write requests for a particular record becomes the master for that record"8, and a record's ownership migrates when the write load shifts, tracked in a hidden metadata field.

Now place PNUTS on Table 1's grid using its own default behavior. Absent a partition, PNUTS chooses latency over consistency: reads default to the ladder above, and even read-latest only chases the most recent committed version, not a synchronously-agreed one — this is the EL half. During an actual partition that makes a record's master region unreachable, PNUTS does not attempt to elect a new master and risk two masters accepting conflicting writes; per Abadi's classification, "the PNUTS default configuration is actually CP: in the case of a partition, the system chooses consistency over availability to avoid the problem of resolving conflicting updates initiated at different master nodes"5 — writes to that record simply fail until the partition heals, even though reads (which can still be served from any non-master replica) remain available. That combination — availability sacrificed for writes specifically, consistency never further compromised — is why PNUTS is PC/EL rather than PA/EL: unlike Dynamo, it never accepts a write it cannot place correctly on the one true per-record timeline.

7. Dynamo revisited through PACELC

Modules 3 and 4 already covered Dynamo's mechanism in depth: consistent hashing with virtual nodes, vector clocks for reconciling concurrent writes, quorum-parameterized reads and writes, and its explicit refusal to offer isolation or cross-key transactions7. PACELC gives that mechanism a second, independent axis to sit on, which the mechanism-level treatment did not need to separate out.

Dynamo exposes its else-branch tradeoff as three tunable integers per table: \(N\) (replicas), \(R\) (replicas that must respond to a read), \(W\) (replicas that must acknowledge a write)7. Configuring \(R + W > N\) buys quorum overlap and therefore stronger read-your-writes-style consistency, at the cost of waiting on more replicas per operation; configuring \(R + W \le N\), Amazon's actual common case, lowers latency at the cost of a read potentially missing the most recent write57. That is the else-branch decision, made independently of any partition, purely to hit a 99.9th-percentile latency SLA7.

The partition-branch decision is a separate mechanism entirely: sloppy quorums and hinted handoff. When enough of a key's designated \(N\) replicas are unreachable, Dynamo routes the write to other, non-designated healthy nodes instead of blocking, then hands the data off to the correct replica once it recovers7. Nothing about \(R\), \(W\), or \(N\) prevents this — the availability-over-consistency choice during a partition and the latency-over-consistency choice absent one are implemented by entirely different pieces of Dynamo's design, which is itself evidence that PACELC's two axes are not merely a notational convenience: a real system's engineering literally forks into two separate mechanisms along exactly that boundary.

Where experts disagree

Modules 3 and 4 already showed that Spanner and Dynamo encode opposite bets about which failure is worse. PACELC does not resolve that disagreement — it sharpens it, by forcing each side to state a position on two questions instead of one, and by adding a third position, PNUTS, that neither pure camp anticipated: sacrifice availability during a partition (like Spanner) while still sacrificing consistency for latency the rest of the time (like Dynamo). The disagreement below restates Module 3's positions in PACELC's vocabulary and asks which of the three quadrants actually represents in the field's practice, not just in theory.

PC/EC is the only defensible default: pay for consistency everywhere

Spanner's design team6, and the fully-ACID camp (VoltDB/H-Store, Megastore) Abadi groups with it5

If an application cannot enumerate every invariant that weak consistency might silently violate, the only safe default is to violate none of them, ever — during a partition or not. Spanner's own commit-wait mechanism (Section 5.2) is the concrete cost of this position: roughly 8ms of deliberate, unconditional waiting on every write, justified because the alternative is asking every application team to reason correctly about which reads might be stale by how much, forever. Bigtable's designers effectively conceded this position from the other direction: application teams kept building Megastore on top of Bigtable specifically for its stronger consistency "despite its relatively low performance"4, evidence that real engineers, given the choice, often pay for EC even when nothing forces them to.

  • One mental model for every read and write, at every layer, forever — no per-call decision about which staleness is tolerable.
  • External consistency composes: a system built this way never needs a later audit to discover an invariant it silently violated under load.
  • Every write pays commit-wait and a cross-group consensus round trip unconditionally, even for data that never needed the guarantee (a page view counter, a UI preference).
  • PC/EC's availability cost is not hypothetical: a genuinely partitioned minority group is unavailable for both reads and writes on its data, full stop.

PA/EL is correct for the workloads that actually dominate a large service's request volume

Dynamo's design team at Amazon7, and the Dynamo-lineage systems (Cassandra, Riak, Voldemort) that inherited the model

Most operations against most keys in a large consumer service are not funds transfers; they are session state, shopping-cart contents, presence, and view counters, where "an add-to-cart operation can never be forgotten or rejected"7 and a merge function is a completely adequate answer to "what happens when two writers disagree." Paying Spanner's unconditional EC tax on every one of those operations, at Amazon's or Cassandra's request volumes, is waste with no corresponding correctness benefit — the PA/EL choice on both axes is not a compromise forced by scale, it is the economically correct answer for this class of data, made twice (once for P, once for E) because both times the answer to "is strict consistency worth the cost here" is the same no.

  • The R+W<N tuning that buys low latency absent a partition and the sloppy-quorum/hinted-handoff mechanism that buys availability during one are separate, independently justified engineering decisions (Section 7) — not one blanket sacrifice.
  • SLAs measured at the 99.9th percentile7 are met by construction, because no operation ever waits on a slow or unreachable quorum member beyond R or W.
  • Every genuine cross-key invariant is now the application's permanent responsibility, with no in-storage escalation path.
  • PA/EL is a bet about the workload, not a law — apply it to a ledger and the "merge function" the store hands you back is not a coherent answer to a double-spend.

PC/EL is underrated: most services want strict correctness only when it is cheap to give

PNUTS's design team at Yahoo!8, implicitly endorsed by Abadi's own preference for the framework that lets a system say this explicitly5

Both prior positions treat the P-axis and E-axis choice as coupled — pick strong or weak and apply it everywhere. PNUTS's record-level mastering shows they need not be: give every record exactly one master so that, absent a partition, the vast majority of writes (85% by PNUTS's own measurement8) are already local and cheap, and reads can explicitly opt into read-any for latency when an application says staleness is fine. But when a partition actually strands a record's master, do not improvise a second master and risk an unresolvable conflict — simply refuse the write. This gets Dynamo's everyday latency behavior without ever accepting Dynamo's central cost: an application-visible divergent version that something must reconcile later.

  • Never produces a conflicting-write anomaly that requires reconciliation logic in the application, unlike PA/EL — every record has exactly one order of updates, always8.
  • Read-any/read-critical/read-latest exposes the latency/consistency choice per call, so an application is never forced into one system-wide answer8.
  • A record's write availability during a partition is exactly as fragile as Spanner's — worse, in one sense, since a single unreachable region can strand a record with no automatic failover at all8.
  • Mastership migration and per-record metadata add real operational complexity that a stateless, symmetric design like Dynamo's avoids entirely7.
Assessment

None of the three quadrants is a universal answer, and the industry's actual trajectory across this course's sources is evidence for a workload-by-workload split rather than a winner. The deciding question is not "how much scale" but "does this data have exactly one natural owner most of the time, and does a merge function exist for the cases where it doesn't." A funds transfer, a unique-username registration, or a globally-numbered schema change has no natural per-record owner and no acceptable merge — Spanner's PC/EC is correct there, and the roughly 8ms commit-wait tax (Section 5.2) is cheap next to the cost of a reconciliation bug in a ledger. A shopping cart, a view counter, or session state has an obvious, cheap merge function for the rare conflict case — Dynamo's PA/EL is correct there, and paying for global consensus on every write would be waste with no offsetting benefit. Data with a natural single owner most of the time, but no acceptable automatic merge when that owner is unreachable — a user's own profile record, a page's edit history — is PNUTS's PC/EL case, and it is underused in practice mostly because record-level mastership is genuinely more operationally complex to build than either of the other two models, not because it is theoretically worse. What would settle a specific system's classification is not more benchmarking of the three designs against each other in the abstract, but writing down, per table, whether a conflict has a well-defined merge (favors PA/EL), a well-defined single owner (favors PC/EL), or neither (favors PC/EC) — exactly the audit Module 4's disagreement section already recommended, now extended to state which of PACELC's two axes each answer actually constrains.

What is changing

Brewer's 2012 retrospective already pointed at where the field's energy has gone since CAP's proof: not toward relitigating the theorem, but toward making a partition's consequences explicit and automatically reversible rather than ad hoc. His own examples — Bayou's replicated calendar coloring tentative entries during disconnection, Google Docs restricting operations to commutative edits during a partition so state converges automatically on recovery, and Marc Shapiro's commutative replicated data types (CRDTs), which "provably converge after a partition" by construction3 — are the applied answer to a question CAP and PACELC only pose: given that a system has chosen A during a partition, how do you make the eventual reconciliation mechanical instead of bespoke. CRDTs are now the standard reference point for any AP system's conflict-resolution layer, in a way vector clocks alone (Module 3) were not, precisely because a CRDT's convergence guarantee is proven once, generically, rather than re-argued per data type.

The consistency/latency literature Abadi's paper opened has also kept moving past the three-option replication taxonomy in Section 4.2: causal consistency and session/read-your-writes guarantees sit between PNUTS's read-any and read-latest calls, offering a cheaper middle rung than "chase the master" without giving up ordering guarantees a pure read-any call drops. Separately, the field's own reference synthesis is itself mid-revision: the second edition of Designing Data-Intensive Applications, published February 2026, restructures how replication, partitioning, and consistency are presented as one continuous spectrum rather than a small set of named levels11 — a framing this module's PA/EL–PC/EC–PC/EL grid is compatible with but does not depend on. What has not changed since 2002 is the proof itself: no system has found a loophole in Gilbert and Lynch's asynchronous-model result, because none exists within that model2; what keeps changing is how much of the resulting cost engineers are willing to make automatic rather than manual.

References

  1. paperHerlihy, M.P., Wing, J.M. Linearizability: A Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems 12(3), July 1990, pp. 463-492. https://cs.brown.edu/people/mph/HerlihyW90/p463-herlihy.pdf. Accessed 2026-09-17. Used for: formal L1/L2 definition of linearizability (§2.2), history/partial-order model (§2.1), locality and nonblocking properties (§3.1), FIFO-queue and register examples (§1.2).
  2. paperGilbert, S., Lynch, N. Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. ACM SIGACT News 33(2), June 2002, pp. 51-59. https://www.cs.princeton.edu/courses/archive/spr22/cos418/papers/cap.pdf. Accessed 2026-09-17. Used for: formal definitions of atomic consistency, availability, and partition tolerance (§2.1-2.3), Theorem 1 impossibility proof (§3.1), Corollary 1.1, the three pairwise-achievable systems CA/CP/AP (§3.2).
  3. paperBrewer, E. CAP Twelve Years Later: How the "Rules" Have Changed. IEEE Computer 45(2), February 2012, pp. 23-29. https://sites.cs.ucsb.edu/~rich/class/cs293b-cloud/papers/brewer-cap.pdf. Accessed 2026-09-17. Used for: "2 of 3 is misleading" critique, partitions-are-rare argument, three-step partition-mode/detect/recover process and Figure 1 state diagram, Chubby/Megastore wide-area Paxos example, PNUTS/Facebook master-locality contrast, CRDT convergence discussion (What is changing).
  4. blogAbadi, D.J. Problems with CAP, and Yahoo's little known NoSQL system. DBMS Musings, 23 Apr 2010. http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html. Accessed 2026-09-17. Used for: original PACELC statement and informal PA/EL, PC/EC, PC/EL definitions.
  5. paperAbadi, D.J. Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story. IEEE Computer 45(2), February 2012, pp. 37-42. http://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf. Accessed 2026-09-17. Used for: formal PACELC definition (§PACELC), CAP-is-for-failures argument, three replication mechanisms and the consistency/latency tradeoff derivation (§Data Replication, §Tradeoff Examples), system classification table (Dynamo/Cassandra/Riak=PA/EL, VoltDB/H-Store/Megastore/Bigtable=PC/EC, PNUTS=PC/EL, MongoDB=PA/EC).
  6. paperCorbett, J.C., Dean, J., Epstein, M., et al. Spanner: Google's Globally-Distributed Database. OSDI 2012. https://research.google.com/archive/spanner-osdi2012.pdf. Accessed 2026-09-17. Used for: external-consistency invariant (§2), TrueTime API and Table 1 (§3), time-master/timeslave architecture and epsilon sawtooth (§3), commit-wait rule and four-line proof (§4.1.2), Table 3 microbenchmarks (§5.1).
  7. paperDeCandia, G., Hastorun, D., Jampani, M., et al. Dynamo: Amazon's Highly Available Key-value Store. SOSP 2007. https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf. Accessed 2026-09-17. Used for: always-writeable design target (§2.3), N/R/W quorum tunability (§4.2), sloppy quorums and hinted handoff (§4.5), 99.9th-percentile SLA framing (§2.2).
  8. paperCooper, B.F., Ramakrishnan, R., Srivastava, U., Silberstein, A., Bohannon, P., Jacobsen, H.A., Puz, N., Weaver, D., Yerneni, R. PNUTS: Yahoo!'s Hosted Data Serving Platform. Proceedings of the VLDB Endowment 1(2), VLDB 2008, pp. 1277-1288. https://people.mpi-sws.org/~druschel/courses/ds/papers/cooper-pnuts.pdf. Accessed 2026-09-17. Used for: record-level mastering and per-record timeline consistency (§2.2), read-any/read-critical/read-latest/write/test-and-set-write API (§2.2), 50-100ms latency budget and asynchronous-replication rationale (§1), 85% write-locality measurement and adaptive mastership (§3.2.2), architecture (§3, Fig. 1).
  9. paperChang, F., Dean, J., Ghemawat, S., Hsieh, W.C., Wallach, D.A., Burrows, M., Chandra, T., Fikes, A., Gruber, R.E. Bigtable: A Distributed Storage System for Structured Data. OSDI 2006. https://www.usenix.org/legacy/event/osdi06/tech/chang/chang.pdf. Accessed 2026-09-17. Used for: Chubby lock service, five-replica Paxos quorum for master election (§4), PC/EC classification basis (Table 1).
  10. paperHunt, P., Konar, M., Junqueira, F.P., Reed, B. ZooKeeper: Wait-free Coordination for Internet-scale Systems. USENIX ATC 2010. https://www.usenix.org/legacy/event/atc10/tech/full_papers/Hunt.pdf. Accessed 2026-09-17. Used for: Zab-based linearizable writes vs. unlinearized local reads (§1, Abstract), 2:1-100:1 read/write target ratio and throughput (Abstract) — the CAP-blind-spot contrast with Spanner (§3.2).
  11. textbookKleppmann, M., Riccomini, C. Designing Data-Intensive Applications. 2nd ed., O'Reilly Media, 2026. https://www.oreilly.com/library/view/designing-data-intensive-applications/9781098119058/. Accessed 2026-09-17. Used for: general framing of consistency models as a continuous spectrum (What is changing) — no specific chapter cited, since the publisher's table-of-contents page returned HTTP 403 to automated fetch.