CAP & PACELC — the Actual Trade-Offs

Learning goal: Explain CAP and PACELC accurately (not the design review cliché), classify real databases against them, and pick a consistency model given a workload.

Why this session exists

A completed write and a later read are enough to expose the CAP trade-off. Brewer proposed the conjecture; Gilbert and Lynch proved it under explicit definitions in 2002. PACELC adds a second question: what coordination costs do we choose even when communication works? We will reason about operations and histories before applying labels to database configurations.

You will be able to

• State CAP precisely using a completed-write/later-read history and nonfailed-node availability.

• Explain PACELC and when coordination adds latency even without a partition.

• Classify configured DynamoDB, Cosmos DB, Cassandra, MongoDB, Spanner and PostgreSQL operations, not product names.

• Pick a consistency level (linearizable / bounded staleness / session / eventual) for a given workload.

Prerequisites

• S042 · Transactions & ACID — you know what atomicity + isolation mean.
• S062 · Load balancers — health checks + failover mental model.
• S063 · Caching — TTL + staleness trade-offs at small scale.

Original resource trail and reading purpose

These exact original URLs preserve optional preparation, not mandatory homework or source acceptance. Video titles and creator names are historical finding labels; identity, content, availability and runtime were not verified. The former 25-minute preparation total, individual durations and 1.25× playback advice are not promises that the material has been watched or will fit your session.

• “CAP Theorem Explained” — historical ByteByteGo label: optional intuition pointer, not an endorsement of a cartoon's definitions.
• “CAP Theorem and PACELC — What They Mean and Why They Matter” — historical Hussein Nasser label: optional comparison/classification pointer. PACELC is a framework, not a second theorem of the same form as CAP.
• “Containers From Scratch • Liz Rice • GOTO 2018” — historical GOTO label: retained as an explicitly mismatched original pointer, not attributed to the author of Designing Data-Intensive Applications or credited as consistency-spectrum teaching. Use the consistency references instead; no claim about the video's actual contents is made.
• Julian Browne's CAP article: optional explanatory perspective, not a substitute for Gilbert–Lynch's formal quantifiers; its old praise has not been re-endorsed.
• Abadi's PACELC paper pointer: optional database-design reading. The source evidence below uses Abadi's saved 2010 explanation; this PDF's identity, page count and reachability were not independently rechecked.
• Jepsen consistency models: optional vocabulary/chart reference for the range of models, not permission to place every model on one total-order ladder.

Follow intuition → diagram/history → bounded model → failure analysis → recall. The original 90-minute slot and phase labels are adjustable study estimates; they are not measured runtimes, a guarantee of mastery, or evidence that all 130 series lessons are currently reviewed.

(a) Intuition · 5 min

Two ATMs start with the same $1,000 balance and cannot communicate. Each receives a $600 withdrawal. Approving both overdraws by $200. To enforce a no-overdraft invariant with unrestricted withdrawals, at least one request must be refused or delayed. The bank need not refuse both: it can authorize only a reachable leader, or preallocate $500 of withdrawal rights to each side, in which case neither side can approve this particular $600 request.

This analogy is about an application invariant, not the theorem's definition of consistency. Escrow rights can preserve that invariant while permitting some operations locally; they do not implement an always-available linearizable register for arbitrary reads and writes. CAP's sharper argument is the next section's unseen completed write.

Safety says a forbidden history never occurs; liveness says an operation eventually completes under stated conditions. Linearizability is safety. CAP availability requires eventual successful service for requests at every nonfailed node even in all fair partitioned executions covered by the model. Fairness does not force a lost cross-partition message to arrive; it rules out blaming the algorithm's lack of progress merely on a nonfailed participant never being scheduled. A majority can continue serving while an isolated minority stops: safety is retained, but theorem-level availability is not. An uptime SLO can still look good if almost all client traffic reaches that majority.

CAP, precisely — Brewer + Gilbert-Lynch

Consider two replicas that cannot exchange messages. A write completes at A. A subsequent read at B must eventually return a result even if the partition never heals, if the algorithm promises availability to every request at nonfailed nodes. B cannot distinguish that execution from one where the write never happened. Returning the old value violates linearizability in the first execution; waiting/rejecting sacrifices availability. This indistinguishability argument is the point of CAP, not a general “pick two products” diagram.

Availability in the theorem is eventual completion of requests at nonfailed nodes, not a latency percentile or uptime percentage. Linearizability respects real-time order of nonoverlapping operations, not necessarily physical simultaneous replication. PACELC is a useful classification framework for partition behavior and normal-operation latency/consistency trade-offs; it does not prove that every strong read needs two or three network round trips. Classify a concrete operation, region topology, consistency setting and failure scenario. A database name alone is insufficient, particularly when a vendor offers different modes.

The gap CAP leaves — what happens when there's NO partition?

PACELC — the classification that adds normal operation

Daniel Abadi described PACELC in 2010 and published its database-design treatment in 2012: PA/EL or PA/EC or PC/EL or PC/EC. In the case of a Partition, choose Availability or Consistency. Else (no partition), choose Latency or Consistency. The point: an unvalidated read from an asynchronously updated replica can be stale even in normal operation. Replica location alone does not prove staleness or consistency. Coordination can add latency; the exact operation, topology and protocol determine the cost, even when the network is fine.

A quick history so the ideas make sense

Brewer's 2000 conjecture motivated Gilbert and Lynch's 2002 proof; the distinction matters because a slogan is not the formal definition. Amazon's Dynamo (2007) describes an availability-oriented replicated key-value design with version reconciliation, not the current DynamoDB service contract. Abadi's 2010 PACELC explanation explicitly asks about latency outside partitions. The 2012 Spanner paper combines replication, transactions and bounded clock uncertainty; it does not remove communication costs. These milestones explain why a modern consistency menu is richer than a permanent CP/AP badge.

CAP — the classic diagram (and its trap)

A partition prevents communication between groups, but clients may still reach both. Follow one completed write and a later read at the isolated peer. Availability requires a response there; linearizability requires respect for the completed write. The peer cannot infer the unseen write from silence.

The theorem describes an execution and precise guarantees, not a permanent CP/AP label attached to a database name. Under an explicit no-partition assumption a system can offer both; real multi-node designs must decide what happens when that assumption fails. Even a single machine has other availability failure modes.

PACELC — the fuller picture

Read the notation as two decisions, not a score. PA/EL describes an availability-oriented partition policy plus a normal path that permits stale local observations to avoid coordination. PC/EC describes refusing operations that cannot preserve the chosen consistency contract and paying its normal coordination cost. PA/EC and PC/EL are useful questions too: does the system weaken its promise only on a fault, or restrict partitioned writes while allowing stale ordinary reads? The answers must name separate read and write APIs; neither combination proves a universal guarantee for the whole product.

Suppose local processing is 2 ms and the required remote durable acknowledgment adds 80 ms on a sequential write path. Under those illustrative assumptions, synchronous acknowledgment takes about 82 ms before client-network overhead; asynchronous local acknowledgment takes about 2 ms but the remote copy can lag. Pipelining can increase throughput without removing the individual request's dependency. A safely leased leader may answer a read without a fresh remote round trip. Thus PACELC predicts a design pressure, not a mandatory number of network trips or a vendor benchmark.

For three replicas with a two-replica commit rule, a 2|1 split can leave the majority writable. The minority must not return success for operations requiring that quorum. Even after connectivity returns, elections, catch-up and fencing determine when service resumes; merely healing the cable is not a recovery protocol.

The consistency spectrum (Jepsen's chart, simplified)

Linearizability respects real-time order of nonoverlapping operations. Bounded staleness restricts allowed lag in time or versions. Session guarantees constrain one client's observations, including read-your-writes and monotonic reads. Eventual convergence permits temporary divergence but requires convergence under its progress assumptions. These dimensions are not one universal ranked ladder.

Check scope: one key or several, one transaction or independent operations, one region or several. A consensus-backed component does not make every API read linearizable; the read-validation protocol and exposed API contract still matter. DynamoDB and other products offer specific modes whose documentation must be read before classification. No universal two- or three-round-trip minimum follows from the word “strong.”

A classification cheat sheet

The primary sources linked below support these configured operation contracts, rather than whole-product CAP labels:

The Cosmos DB management documentation checked on 2026-10-07 describes a preview ReadConsistencyStrategy in Java SDK v4.69+ and .NET SDK v3.46+, supported in direct mode only, that can request supported stronger read strategies without changing the account default. Do not transfer the traditional override restriction to that API or infer that changing a read strategy changes cross-region write durability.

Choosing for a workload. A profile editor needs read-your-writes across its own save/refresh flow. Carry the session token through the application tier; a new device without that context is a new case to design. A dashboard can tolerate a specified 30-second freshness bound only if the storage or application enforces it—eventual consistency alone is insufficient. An inventory reservation needs an atomic conditional decrement or transaction, not a strong read followed by an unconditional write. An approximate view counter may use eventual convergence if duplicate/lost-event handling is specified separately.

(c) Hands-on · 25 min

We'll build a restricted sequential Python illustration of the two partition policies: a two-node replicated store where you can toggle a partition, choose CP or AP behaviour, and watch reads/writes behave accordingly. No servers, concurrent clients, durable storage, elections or automatic recovery: the code supports the example, not the theorem.

"""s070_cap_sim.py — a 100-line simulator to make CAP concrete.
 
Two nodes, one key. A client writes to Node A; Node A tries to replicate to Node B.
You control:
  * partition on/off  (drop messages between A and B)
  * mode: 'CP' (reject before mutation when partitioned) or 'AP' (accept and diverge)
 
Run:  python s070_cap_sim.py
"""
from __future__ import annotations
from dataclasses import dataclass, field
from typing import Optional
import time
 
 
@dataclass
class Node:
    name: str
    store: dict[str, str] = field(default_factory=dict)
 
 
@dataclass
class Cluster:
    a: Node
    b: Node
    partitioned: bool = False
    mode: str = "CP"           # "CP" or "AP"
    replication_delay_ms: int = 10
 
    # ---- write path ----
    def write(self, key: str, value: str) -> tuple[bool, str]:
        """Client always writes to node A. A tries to replicate to B."""
        if self.partitioned:
            if self.mode == "CP":
                # Reject BEFORE mutation: preserve any previously committed value.
                return False, "REJECTED (partition, CP: won't accept without replica ack)"
            else:  # AP
                self.a.store[key] = value
                # Availability: accept, replicas will diverge
                return True, "ACCEPTED on A (partition, AP: will reconcile later)"
        # Sequential toy: no concurrent reads during this operation.
        self.a.store[key] = value
        # Normal path: replicate to B
        time.sleep(self.replication_delay_ms / 1000)
        self.b.store[key] = value
        return True, "ACCEPTED (replicated to B)"
 
    # ---- read path ----
    def read(self, key: str, from_node: str = "a") -> tuple[Optional[str], str]:
        node = self.a if from_node == "a" else self.b
        val = node.store.get(key)
        return val, f"read from {node.name.upper()}"
 
 
def print_state(c: Cluster) -> None:
    print(f"  A={c.a.store}  B={c.b.store}  partition={c.partitioned}  mode={c.mode}")
 
 
def main() -> None:
    c = Cluster(a=Node("a"), b=Node("b"))
 
    print("\n=== SCENARIO 1: normal write, replication OK ===")
    ok, msg = c.write("balance", "1000")
    print(f"write balance=1000 → {ok} · {msg}")
    print_state(c)
 
    print("\n=== SCENARIO 2: partition + CP mode ===")
    c.partitioned = True
    c.mode = "CP"
    ok, msg = c.write("balance", "1200")
    print(f"write balance=1200 → {ok} · {msg}")
    print_state(c)
    print("  Read from A:", c.read("balance", "a"))
    print("  Read from B:", c.read("balance", "b"))
    print("  Correct: system refused inconsistent write; both nodes still show old value.")
 
    print("\n=== SCENARIO 3: partition + AP mode (concurrent divergent writes) ===")
    c.mode = "AP"
    ok, msg = c.write("balance", "800")           # A accepts
    print(f"client-1 writes balance=800 on A → {ok} · {msg}")
    # Meanwhile a client hits B directly (simulate)
    c.b.store["balance"] = "1500"
    print("client-2 writes balance=1500 directly on B (available side)")
    print_state(c)
    print("  Read from A:", c.read("balance", "a"))
    print("  Read from B:", c.read("balance", "b"))
    print("  DIVERGENCE — same key, two values. Standard AP behaviour during partition.")
 
    print("\n=== SCENARIO 4: partition heals, we need conflict resolution ===")
    c.partitioned = False
    # Simplest strategy: last-write-wins by an imaginary timestamp
    print("  Applying LWW reconciliation (choose one)...")
    winner = c.b.store["balance"]                  # pretend B's write was later
    c.a.store["balance"] = winner
    print_state(c)
    print("  Note: LWW SILENTLY LOSES client-1's write. This is the ‘lost update’ pitfall of AP.")
    print("  Real systems use vector clocks / CRDTs / application-level merge to do better.")
 
    print("\n=== SCENARIO 5: PACELC — even without partition, replica reads may be stale ===")
    c.a.store["balance"] = "2000"
    print("write balance=2000 to A (no partition)")
    print("  IMMEDIATE read from A:", c.read("balance", "a"))
    print("  IMMEDIATE read from B (before replication):", c.read("balance", "b"),
          "← STALE — replication is async")
    time.sleep(c.replication_delay_ms / 1000)
    c.b.store["balance"] = "2000"                   # replication catches up
    print("  After replication delay, read from B:", c.read("balance", "b"))
 
 
if __name__ == "__main__":
    main()

What each block does

Anatomy of the simulator

Cluster.write · partitioned check

The fork in the road. If partitioned + CP → refuse before mutating either replica. If partitioned + AP → accept locally and diverge. This is one sequential illustrative policy, not a proof or a fault-tolerant implementation.

Scenario 2 · CP under partition

System stays consistent by rejecting the write. Correctness preserved; availability sacrificed.

Scenario 3 · AP under partition

The script serially demonstrates two independently accepted assignments on disconnected copies. It has no concurrent scheduler: its printed ‘concurrent’ label describes the intended distributed scenario, not a concurrency test. These local successes demonstrate the availability-oriented choice, not a proof of availability for every execution.

Scenario 4 · reconciliation lost update

The script chooses B by fiat: it does not record or compare timestamps, so its printed LWW label is only a stand-in for an ordering policy. A real LWW register needs an explicit total-order/tie rule and can discard one independent assignment. Vector clocks identify concurrency; suitable CRDTs or application merges define reconciliation. These are different mechanisms, not progressively better versions of one guarantee.

Scenario 5 · PACELC in action

Even without a partition, the async replication window means node B's read is stale until the explicit replication step (the sleep is illustrative, not a real-time guarantee). That's the L (latency) vs C (consistency) trade even when nothing is broken.

What to observe

1. Scenario 2: system refuses the write and both nodes stay at the pre-partition value. This is CP.
2. Scenario 3: both nodes accept different writes; a later read on the other replica can violate the real-time register contract. This is AP.
3. Scenario 4: naïve LWW reconciliation loses a legitimate write. The fixture discards one assignment; a real design must specify its reconciliation rule rather than rely on a product label.
4. Scenario 5: even in the happy path with no partition, reading from a replica returns stale data during the replication window. This is the E (Else) side of PACELC — you trade Latency for Consistency.

Extension: route a read to the single writer in this toy. Add the method below inside Cluster and repeat scenario 5. It returns A's 2000 rather than B's 1500, under the restricted assumption that A is the only authoritative writer and has not failed. Scenario 3 intentionally violated that assumption by writing directly to B. Do not call this a general strong-read implementation or a simulation of DynamoDB's internal routing.

def read(self, key, from_node="a", strong=False):
    node = self.a if strong else (self.a if from_node == "a" else self.b)
    return node.store.get(key), f"read from {node.name.upper()} (single_writer={strong})"

Exercise and answer: Initialize balance to 1000, partition, and reject 1200. Both stores must remain 1000; rejecting a write by deleting the key would itself corrupt committed state. In AP mode, accept 800 on A while B still returns 1000: the stale read after acknowledgment supplies the counterexample. Reconciliation chooses application semantics; LWW discards one competing assignment, vector clocks detect concurrency, and CRDTs merge only the operations their type defines. None magically restores every business intention.

(d) Production reality · 15 min

Common conceptual failure modes

• Confusing database C with ACID C. CAP's C is a history/ordering property. ACID consistency means preserving declared application invariants; a correctly allocated escrow inventory is a counterexample to treating the two as synonyms.
• Treating rejection as success. A server returning a timeout or an error may be reachable but is not serving the requested register operation under the theorem's availability definition.
• Assuming a quorum proves everything. Quorum intersection is a set fact; safe version selection, election, durability and read protocols are additional requirements.
• Budgeting away failover loss. Two durable copies protect only the stated failure domains. Synchronous copies in one region do not promise survival if that entire region disappears. An asynchronous remote copy may be missing acknowledged writes.
• Using a clock as consensus. A bounded timestamp uncertainty can support a protocol; a timestamp alone does not prove that a remote write was durable or that an old leader is fenced.

Historical incident pointers, not verified incident claims

The original AWS event link, Jepsen MongoDB 3.6.4 analysis and Spanner research landing page are retained as optional incident/research discovery pointers; their current destinations and complete contents were not rechecked here. Do not infer a five-hour AP-caused outage, a MongoDB 3.4 default change, or a universal seven-millisecond Spanner commit from the old annotations. The reviewed replacement mechanisms are control-plane dependency failure, acknowledgment/rollback scope and replication plus commit-wait costs; exact historical claims need their own source adjudication.

For a hypothetical control-plane failure, a healthy data replica can still be unreachable through an application if its routing metadata points to an obsolete owner. Retrying every failure can then overload the metadata service. Inspect the routing/version contract, refresh behavior and retry budget separately from the database's read concern; neither an AP label nor a CP label establishes this causal chain for the linked AWS incident.

Where this shows up in the rest of the plan

Replication supplies the acknowledgment and promotion mechanics. Consistency models tests actual histories. Sharding adds object-placement and cross-key scope; multi-region recovery puts failure-domain and latency assumptions into a runbook. Consensus (Paxos/Raft) supplies protocol rules behind some strong operations; the term “CP” is not the algorithm. A feed system can tolerate stale displays while its account or payment subsystem requires atomic mutations: choose per operation, not one label for the whole feed application.

(e) Recall + stretch · 10 min

1. State CAP precisely. No read/write object in the asynchronous partition model can guarantee both atomic consistency (linearizability) and completion of every request at nonfailed nodes in all the covered executions. A no-partition assumption permits both; it is an assumption to document, not protection against a real partition.
2. What does PACELC add? The latency/consistency trade-off in ordinary operation. An 80 ms acknowledgment dependency can matter every day even if a partition is rare; it is not a universal cost of every strong read.
3. Classify Cassandra, Spanner and DynamoDB. Cassandra ONE and QUORUM differ in availability and response requirements, with LWT a separate protocol. Spanner's external-consistency contract may sacrifice progress when required quorums are unreachable. DynamoDB table strong reads, eventual reads, MREC and MRSC global tables must be classified separately.
4. Linearizable versus eventual? Linearizable operations admit a legal sequential ordering that respects nonoverlap in real time; overlapping operations can be ordered either way if the object specification allows it. Eventual convergence promises eventual agreement under delivery/progress assumptions after updates stop, not a fixed deadline.
5. Does reading from a primary always suffice? No. An obsolete primary can be stale; authorization to serve, application/replay position and the read protocol matter. The toy extension assumes these away.
6. Does TrueTime make Spanner latency just clock uncertainty? No. Commit wait is one part of a protocol that still replicates and may coordinate transactions across participants. No fixed seven-millisecond claim applies to every deployment or operation.

Four original recall questions, answered explicitly

Why is “CA” not a third partition policy? A system can provide both availability and linearizability under a no-partition assumption. That is a conditional contract, not a claim that every single-node system is available or that every multi-node system fails catastrophically. Once executions with arbitrary message loss are included, the theorem prevents promising both for every request at nonfailed nodes.

Which level serves a read-your-writes profile? A session contract with a correctly propagated token can prevent that client's read from preceding its own acknowledged update. Carry the context across stateless application servers; a second device needs token transfer or a separately chosen freshness/strong-read rule. Session consistency does not set a universal “few seconds” bound for other users.

How are divergent assignments reconciled? LWW selects one using a deterministic order; clock skew and ties need explicit handling. Vector clocks can distinguish causally ordered versions from concurrent siblings, but detecting a conflict does not merge business intent. A suitable CRDT merges its defined operations under delivery assumptions; application-level merge supplies domain-specific rules. Convergence alone does not prevent an overdraft.

Do DynamoDB strong reads and Spanner strong operations mean the same scope? No. DynamoDB's table/LSI read flag covers the documented read, not GSIs or streams, and does not expose an internal primary/AZ routing promise. Global-table MREC and MRSC are separate contracts. Spanner's external consistency concerns its specified transaction/isolation and strong-read APIs. Compare object/transaction scope, region mode and failure behavior, not the adjective alone.

Checkout exercise and worked answer

Design a cart, stock display, reservation, payment and order-history flow. State what survives a 2|1 partition.

Answer: Use session guarantees for cart edits, and an explicitly tolerated stale stock display. Reserve stock through a conditional decrement with stock >= quantity and a stable reservation ID; retrying that reservation must not reserve twice. A two-replica quorum can let the majority continue; the minority rejects reservations rather than oversells. A single-key linearizable read then separate write is not sufficient: both buyers can read 1 before either decrements. Use an atomic conditional mutation.

A card provider is outside the database transaction. Commit an order/payment intent locally, call the provider with an idempotency key, and reconcile uncertain outcomes with its status API; compensation is a business workflow, not an atomic transaction across the card network. Show order history from a replica that has applied the user's commit token, or explicitly display pending state. Bounded staleness alone does not ensure immediate read-your-writes.

Explain-out-loud test

Explain the unseen-write argument, the 82 ms versus 2 ms example, and the conditional stock reservation. A correct answer names the operation, acknowledgment boundary, failure domain and progress condition—not just a vendor label.

What comes next

Continue with replication to distinguish acknowledgment, replay and failover authority.

Hub: The 6-Month Learning Plan

Sources and review boundary

Full-body review renewed 2026-10-10, replaying the saved 2026-10-07 primary passages and their raw/canonical hashes. Mutable documentation is accepted only at that saved evidence boundary, not represented as freshly fetched current service behavior. Numerical examples are explicit teaching assumptions. The bounded Python examples were run locally; no cloud/distributed deployment, PostgreSQL cluster, broker, object store, load benchmark or regional drill was executed. Compilation and diagram parsing do not establish deployed-system correctness.

• Gilbert and Lynch CAP proof, 2002 — CAP excludes simultaneous availability and atomic consistency in the asynchronous partition model.; CAP availability is eventual response at every nonfailed node, not a latency percentile.
• Abadi, PACELC, 2010 explanation — PACELC adds latency/consistency trade-offs without partitions.
• Dynamo Read — DynamoDB strong reads have table/LSI scope and do not cover GSIs/streams.; DynamoDB eventual reads cost half as much on the same read-size basis.
• Dynamo Global — Current DynamoDB global tables distinguish MREC and MRSC.
• Mongo Linear — MongoDB linearizable read concern observes successful prior majority writes.; MongoDB linearizable-read guarantee requires single-document identification.
• Azure Cosmos DB consistency levels — Cosmos session reads carry a token and require a sufficiently advanced replica.
• Cosmos Override — Traditional Cosmos overrides and the newer ReadConsistencyStrategy have different strengthening rules.; The newer read-strategy feature is preview and direct-mode-only.
• Cass Guarantees — Cassandra lightweight transactions have a different consistency contract from ordinary writes.
• Spanner — Spanner external consistency applies to its default/serializable isolation contract.
• Spanner Paper — Spanner replication uses Paxos groups in the 2012 design.; Spanner commit wait is part of its external-order protocol.
• Pg Sync — remote_apply waits for replay/visibility on configured synchronous standbys.; A synchronous_commit value alone does not configure synchronous standby replication.
• PostgreSQL 16 warm standby — Asynchronous WAL shipping exposes acknowledged-state loss if the primary copy is destroyed before shipping.
• Linear Paper — Linearizable operations take effect within their own call/return intervals.