CAP Theorem and PACELC: Consistency Trade-offs, Precisely

What you'll learn: By the end of this lesson you will be able to state the CAP theorem with the definitions Gilbert and Lynch actually used, explain why partition tolerance is not a feature you can decline, describe what a CP and an AP system does during a partition and when nothing is broken, use PACELC to reason about the cost of consistency in normal operation, name the real settings that move a Cassandra, PostgreSQL or MongoDB deployment along that trade-off, and run a Java lab that makes stale reads and refusals visible.

Two librarians work on different floors of one library and share a single card catalogue by intercom. When a book is borrowed, the librarian who lent it calls the other so both catalogues agree. One afternoon the intercom dies. A visitor asks the upstairs librarian whether a book is on the shelf. She can say "I cannot check, come back later" and be sure never to give a wrong answer. Or she can answer from her own catalogue, and risk sending the visitor to an empty shelf.

That is the theorem in small. The overview lesson, CAP, PACELC and consistency models, gives the vocabulary and a menu of consistency models. This lesson goes to the proof, the real tuning settings, a lab and a failure scenario, and assumes you know the basics of replication.

Verified with Java 25, PostgreSQL 18 (18.6 documentation), Apache Cassandra 5.0 documentation (5.0.9 is the latest GA release on its download page) and MongoDB manual 9.0, on 2026-11-07.

The core idea

CAP is a statement about one narrow moment, a network partition, and about two strict properties: atomic consistency and total availability. It says that during that moment you cannot keep both. Everything else people attach to it (the "pick two" slogan, labels for whole databases, claims about speed) goes beyond what was proved.

Three kinds of example run through the lesson, each labelled:

• Minimal example: a three-replica register in Java, the lab in "Build it".
• Realistic example: ShopStream's shopping cart against its stock and payments, in "In practice".
• Failure example: split-brain, where two nodes both believe they are in charge.

What the theorem says

Seth Gilbert and Nancy Lynch published the proof in 2002 ("Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services", ACM SIGACT News). Eric Brewer had put the conjecture forward in a talk at PODC 2000. The paper defines each word formally, and the definitions are narrower than everyday use.

The 2012 follow-up by the same authors ("Perspectives on the CAP Theorem") states it plainly: in a network subject to communication failures, no web service can implement an atomic read/write shared memory that guarantees a response to every request.

The proof in a few sentences

Split the nodes into two groups, G1 and G2, and lose every message between them. A client writes a new value in G1; availability forces G1 to finish the write. Later a client reads in G2. Availability forces G2 to answer, but nothing from G1 can reach it, so it can only return the old value. A read that began after a completed write returned the old value, which breaks atomic consistency.

Figure 1. The impossibility argument as a message sequence. How to read this: the dashed boundary is the lost messages. The write is acknowledged because the system must stay available. The read then has only two possible endings, and both give up one of the two properties.

Two further results matter. Corollary 1.1 says that in an asynchronous network, where an algorithm cannot tell a lost message from a very slow one, you cannot keep consistency even in the executions with no lost message while staying available in all executions. In the partially synchronous model (messages arrive within a known time or are lost), the same impossibility holds with lost messages (Theorem 2), but an algorithm with timeouts can return atomic data whenever all messages arrive and fall back to possibly stale data only when a timeout shows a loss (section 4.3). That is the shape of most real systems: consistent in good times, a decision when a timeout fires.

Why partition tolerance is not optional

The paper shows any two of the three can be had. Consistent and available works without partitions, for example a centralised algorithm on one LAN (section 3.2.2). Consistent and partition tolerant works if you may refuse to answer. Available and partition tolerant works if you may answer with stale data, as web caches do.

So "CA" is not a third choice among equals. It is a design that assumes the network never loses a message, and nodes on a real network cannot make that true by declaring it. The paper models any pattern of message loss as a temporary partition, and the 2012 paper observes that a message delayed long enough may as well be lost. Brewer's 2012 article ("CAP Twelve Years Later: How the Rules Have Changed") adds that there is no global notion of a partition. The practical question is therefore never "CA, CP or AP?" but "what does each operation do when the replicas cannot talk?"

Try it: the partition simulator

The widget below cuts one replica off from the other two so you can compare the behaviours before reading further. It has three replicas, a client on each side of the cut and a result log. In CP mode, writes and reads need a quorum, so the minority side refuses. In AP mode, both sides keep serving and diverge.

Illustrative simulation, not a benchmark.

Suggested run: cut the network, write from the majority side and read from the minority side, first in CP mode and then in AP mode. In the log, note which side refused and which answered.

CP and AP: one partition, two answers

When a partition happens, each operation takes one of two paths. A CP behaviour refuses or waits when it cannot reach enough replicas to be sure of the answer. An AP behaviour answers from whatever it can reach and accepts that the answer may be stale, or that two sides may accept conflicting writes.

Figure 2. The same partition in a three-replica store. How to read this: the red dashed arrows are lost messages. Client A can reach two of three replicas. Client B reaches only replica 3. A CP design refuses client B's writes and reads; an AP design lets client B continue and reconciles later.

One subtlety: the theorem demands that every non-failing node answer, so a majority-based store fails its definition of availability even though most clients are served. Everyday talk uses "available" more loosely; keep the two meanings apart when reading vendor pages.

PACELC: the cost when nothing is broken

Daniel Abadi's paper ("Consistency Tradeoffs in Modern Distributed Database System Design", IEEE Computer, February 2012) notes that people read CAP as limiting a system in normal operation, when it only describes failures. He proposed PACELC, pronounced "pass-elk": if there is a partition (P), how does the system trade availability (A) against consistency (C); else (E), how does it trade latency (L) against consistency (C)?

Figure 3. PACELC splits the choice into two moments. How to read this: the first diamond is the only one CAP talks about. The second branch applies on every request when the data is replicated, which is why Abadi argues it often shapes a database more than CAP does.

His argument for the "else" half is about replication. As soon as data is replicated, a consistency and latency trade-off appears, because there are only three ways to send updates: to all replicas at once, to an agreed master first, or to an arbitrary node first. Waiting for replicas to confirm keeps them consistent but adds round trips, bounded by the slowest replica, especially over a wide-area network. Acknowledging before replicating is fast but allows stale reads.

He also classified the systems of the time. These 2012 labels are history, not statements about current products, which are configurable and have changed:

Treat the letters as a reasoning aid for a configuration, not as a brand label.

Misconceptions, corrected

Brewer's recommended mindset: detect partitions (a timeout is the detector), enter an explicit partition mode that limits some operations, and on recovery converge the state and compensate for mistakes made meanwhile. A partition is effectively a time bound on communication, so a tighter bound means entering partition mode more often, even when the network is only slow.

The knobs you actually have

Real products expose the trade-off as settings. The summary below comes from the pages in the Official documentation list, read on 2026-11-07. Defaults change between versions, so check the page for the version you run.

Cassandra (documentation 5.0)

Cassandra sends every write to all replicas and uses the consistency level to decide how many responses the coordinator waits for:

The page states the overlap rule as W + R > RF, where RF is the replication factor: with RF = 3, QUORUM reads and writes overlap on at least one replica. Hints are best effort; the hints page says they do not guarantee eventual consistency the way anti-entropy repair does, and by default a coordinator generates hints for a failed node for up to 3 hours (max_hint_window). The guarantees page lists lightweight transactions with linearizable consistency (Paxos, giving compare-and-set) and says Cassandra chooses availability and partition tolerance.

PostgreSQL 18

Streaming replication is asynchronous by default. The manual says committed transactions may not have reached the standby if the primary crashes, and the data loss is proportional to the replication delay at failover. Two settings change this:

• synchronous_standby_names lists the standbys commits wait for: FIRST num_sync (...) for priority-based choice, ANY num_sync (...) for quorum-based choice, or a plain list (equivalent to FIRST 1). With no names, synchronous replication is off.
• synchronous_commit (default on) sets how far the standby must get before a commit returns:

It can change per transaction, so a low-value write can choose speed and a write that a replica read must see can choose remote_apply.

# postgresql.conf on a primary (illustrative)
synchronous_standby_names = 'ANY 1 (standby_a, standby_b)'
synchronous_commit = on

With ANY 1 (standby_a, standby_b), a commit needs an acknowledgement from at least one of the two, so one standby may be lost. The manual warns that such commits may never complete if a required synchronous standby crashes, and recommends naming several potential standbys for availability. That is the CP side, chosen on purpose; its minimum cost is the round trip between primary and standby, the "else" half of PACELC made concrete.

MongoDB 9.0

MongoDB splits the settings into a write concern and a read concern:

The maxTimeMS advice is CAP in one line: a linearizable read waits or fails rather than answer from a possibly stale node. Across all three products the pattern is the same: majority-style settings move toward consistency; ONE, local, w: 1 and asynchronous replication move toward latency and availability.

Minimal example: build the quorum register

The smallest working model of the trade-off is one register on N in-memory replicas, with a write quorum W, a read quorum R and a partition injector, in plain Java.

Goal. See a stale read when R + W <= N, a refusal in strict mode during a partition, and a stale answer in sloppy mode during the same partition.

Setup. From the repository's examples/backend folder:

cd examples/backend && ./gradlew :labs:quorum-register:test
./gradlew -q :labs:quorum-register:run

The first command runs the 13 tests. The second prints the scenario table. The code is in examples/backend/labs/quorum-register/src/main/java/buildingai/labs/quorumregister/QuorumRegister.java.

How the model works. A client contacts replicas in a fixed order, home replica first, skipping unreachable ones. A write is applied synchronously to the first W reachable replicas, which is the acknowledgement; the others get it later as a pending delivery, standing in for replication lag and hinted handoff. A read asks the first R reachable replicas and returns the highest version (last-write-wins on a logical timestamp). Read repair is off by default. Strict mode refuses when fewer than W (writes) or R (reads) replicas are reachable. Sloppy mode uses whatever is reachable and fails only when nothing is. The choice lives in one method:

private void requireAvailable(String operation, int reachable, int needed) {
    if (reachable == 0) {
        throw new UnavailableException(name + ": " + operation + " impossible, no replica reachable");
    }
    if (config.mode() == Mode.STRICT && reachable < needed) {
        throw new UnavailableException(name + ": " + operation + " needs " + needed + " replicas, only "
                + reachable + " reachable (strict quorum)");
    }
}

Delete the strict check and the CP behaviour disappears.

Steps.

1. Run the tests. They check that when R + W > N a successful read sees the latest acknowledged write for every N from 1 to 5, every W and R and every placement, including a random history with partitions that come and go, and that for R + W <= N a stale read can be found.
2. Run the demo and compare it with the output below, using the row guide after it.

Expected output, captured from a real run (Java 25.0.3, 2026-11-07):

Quorum register: N replicas, write quorum W, read quorum R. alice starts at replica 0, bob at replica 2.
Column 'replicas after' shows the value@version held by replicas 0, 1, 2 after the step.

#  config               mode   partition   replicas after       step -> outcome
--------------------------------------------------------------------------------------------------------------
1  N=3 W=2 R=2          strict none        [v1@1, v1@1, -]      alice writes v1 -> acked by replicas [0, 1]
1  N=3 W=2 R=2          strict none        [v1@1, v1@1, -]      bob reads -> v1 from replicas [2, 0]  (R+W=4 > N=3: overlap, fresh)
2  N=3 W=1 R=1          strict none        [v1@1, -, -]         alice writes v1 -> acked by replicas [0]
2  N=3 W=1 R=1          strict none        [v1@1, -, -]         bob reads -> (nothing) from replicas [2]  (R+W=2 <= N=3: no overlap, STALE)
2  N=3 W=1 R=1          strict none        [v1@1, v1@1, v1@1]   background replication delivers 2 writes
2  N=3 W=1 R=1          strict none        [v1@1, v1@1, v1@1]   bob reads -> v1 from replicas [2]  (caught up)
3  N=3 W=2 R=2          strict bob:{0,1}   [v1@1, v1@1, -]      bob reads -> UNAVAILABLE
4  N=3 W=2 R=2          sloppy bob:{0,1}   [v1@1, v1@1, -]      bob reads -> (nothing) from replicas [2]
5  N=3 W=2 R=2          strict alice:{1,2} [-, -, -]            alice writes v1 -> UNAVAILABLE
6  N=3 W=2 R=2          sloppy split       [v1@1, -, -]         alice writes v1 -> acked by replicas [0] (W not met)
6  N=3 W=2 R=2          sloppy split       [v1@1, -, -]         bob reads -> (nothing) from replicas [2, 1]  (stale: v1 is only on replica 0)
6  N=3 W=2 R=2          sloppy healed      [v1@1, v1@1, v1@1]   partition heals, hinted writes delivered: 2
6  N=3 W=2 R=2          sloppy healed      [v1@1, v1@1, v1@1]   bob reads -> v1 from replicas [2, 0]
7  N=3 W=1 R=2          strict none        [v1@1, -, -]         carol reads -> v1 from replicas [0, 1]  (read repair off)
8  N=3 W=1 R=2 +repair  strict none        [v1@1, v1@1, -]      carol reads -> v1 from replicas [0, 1]  (read repair on)

Break it. In the demo, change row 1 from Config.strict(3, 2, 2) to Config.strict(3, 1, 1): the fresh read becomes (nothing). Then delete the Mode.STRICT check in requireAvailable; the tests strictModeRefusesWhenTheReadQuorumIsUnreachable and strictModeRefusesWritesAndChangesNothing... fail, which is the cost of choosing availability shown as a failing assertion.

Stretch. Replace the logical timestamp with a vector clock per value and return both versions when two writes were concurrent (siblings), as in the Dynamo paper's shopping cart. Add an anti-entropy sync(i, j) that merges two replicas and show they converge without read repair. Add a second key with W and R per request, as Cassandra's consistency levels do.

What the model leaves out. No concurrent clients, real clocks, vector clocks or siblings, partly applied failed writes or membership changes. A partition is a set of replicas a given client cannot reach. The property tested is "a read after an acknowledged write" in a sequential history, not linearizability under concurrency, so it is not proof that a real store is linearizable.

Failure example: split-brain

Split-brain is the failure where, after a partition, two nodes both believe they are the leader and both accept writes. Each side acknowledges clients, so each side looks healthy, and the histories diverge.

Figure 4. How an automatic failover turns a partition into split-brain. How to read this: the standby cannot tell a dead primary from an unreachable one, which is the indistinguishability at the heart of the CAP proof. Both sides then answer, so availability was kept and consistency was lost.

What breaks: a unit of stock is sold twice, or a payment lands on one history and not the other. Detection: a check that asks every node whether it believes it is the primary and alerts when more than one says yes (in PostgreSQL, pg_is_in_recovery() returns true while a server is a standby, so two servers returning false is a signal), plus business invariants such as stock never negative and balanced ledger entries. Prevention: require a majority for leadership, so only the majority side can elect or keep a leader, and fence the old leader so a deposed primary cannot write. Elections and fencing are in Consensus and leader election; this is why consensus-based systems choose consistency in a partition. MongoDB's documentation shows the other face: with w: 1, a write acknowledged by a primary that then steps down can be rolled back.

Frontend view

The browser meets these trade-offs as optimistic updates and eventual consistency in the interface: an action appears to succeed at once, and the screen must be able to roll back when the server later refuses or merges something else. The Frontend System Design track plans a lesson on optimistic updates and rollback (not published yet, so there is no link). The back-end rule that makes the front end's job possible is the one in this lesson: decide per operation whether a refusal is acceptable, and return an error the interface can act on.

In practice: a shopping cart that stays writable, and stock that must not oversell

This is the realistic example. It is an educational scenario on the course's running example, ShopStream, and nothing in it describes a real company. Every figure is illustrative.

This is a realistic scenario, not a case history.

The situation

ShopStream keeps carts, orders, payments and stock in PostgreSQL (data model), and Stage 4 adds shard primaries with a synchronous standby in another zone. In a partition between zones, a shopper on the minority side cannot add anything to the cart. The team asks whether a cart, a list one shopper edits alone, must be as strict as stock and payments.

Starting architecture

Figure 5. The design under discussion: one path that may diverge, one that must not. How to read this: the top zone is the cart, where an accepted write on either side of a partition is acceptable if it can be merged. The bottom zone is checkout, where one primary decides and the other side refuses.

Options considered

Gilbert and Lynch's 2012 paper describes this same split: the cart may be highly available and occasionally lose a recent update, while check-out, billing and shipping records have to be strongly consistent.

The decision

Option B for carts, strict handling for stock and payments. The cart merge is a union, which never loses an add:

static Set<String> mergeCarts(Set<String> a, Set<String> b) {
    Set<String> merged = new TreeSet<>(a);
    merged.addAll(b);
    return merged;
}

Merging [milk, eggs] and [milk, bread] prints [bread, eggs, milk] (a TreeSet sorts). The cost is visible: a removal on one side is undone by the union. Stock stays on the one-statement conditional update from the data model lesson, and a checkout that cannot reach the authority returns a clear error with a retry path. Payments keep their idempotency keys and ledger from the payments lesson.

Rollout and verification

A rollout would run the cart store beside the old path and compare carts for disagreement. Verification rests on invariants: stock is never negative (a CHECK (stock >= 0) constraint backs the conditional update), ledger entries balance, and every order has a payment record or a cancellation. Metrics: cart merges per hour, checkouts that drop an item at validation, and checkout errors from an unreachable authority.

The 2 a.m. failure

The page reads: two stock shards report themselves as primary. A zone link failed, automatic failover promoted the standby, and the old primary kept answering, the split-brain of Figure 4. The checks: ask each node whether it believes it is primary, compare the highest log positions, and run the stock and ledger queries. The mitigation is to stop writes on the node without a majority, fence it, and reconcile oversold units with refunds or substitutions. The lasting fix is to make promotion a majority decision, not one standby's view of a missed heartbeat, and to name more than one potential synchronous standby.

Architect's notes

• Decide per operation. One row per read and write, one column for what it does without a quorum. "We are AP" is not a design.
• Start strict for money, uniqueness and safety; relax elsewhere. A small strict core is easier to keep than one bolted on later.
• Give data one home when a merge cannot preserve intent, and serve stale reads elsewhere.
• Measure before you promise. The "else" cost is the round trip to the farthest replica you wait for; read it from a staging write.
• Check your version. Defaults for MongoDB write concern, PostgreSQL synchronous_commit and Cassandra hint windows are documented per version.
• Pick a merge rule deliberately. Last-write-wins, siblings and CRDTs fit different data (see IDs, clocks and ordering).

Figure 6. A per-operation decision. How to read this: start at the top for each operation, not for the whole system. Money and uniqueness fall out on the left, mergeable data on the right, and everything else needs one writer.

Common mistakes

• Saying "we chose CA". Over a real network it assumes no partition will happen.
• Labelling a product CP or AP for good. Check the setting per query; Abadi's 2012 labels describe defaults of that time.
• Reading CAP's C as ACID's C.
• Believing R + W > N proves linearizability. It proves overlap only.
• Ignoring the "else". Waiting for replicas costs time on every request.
• Promoting a standby on one missed heartbeat. That produces split-brain.
• Last-write-wins without thought. It silently discards one of two concurrent writes.
• Using w: 1 or asynchronous replication for data that must not be lost.

Key takeaways

• CAP's consistency is linearizability and its availability is a response from every non-failing node; with lost messages you cannot have both.
• The proof rests on one fact: a node cannot tell a lost message from a slow one.
• Partition tolerance is a fact of networks. The choice is per operation: refuse or answer.
• PACELC adds the normal-time choice, latency against consistency.
• Quorums (R + W > N) give overlap, not linearizability; sloppy mode removes even the overlap.
• Cassandra consistency levels, PostgreSQL synchronous_commit and synchronous_standby_names, and MongoDB write and read concerns are the dials.
• Split-brain is what an unguarded failover does to a partition; majority-based leadership and fencing prevent it.
• Keep a small strict core (stock, money, uniqueness); let mergeable data such as carts stay available.

Practice exercises

Exercise 1 (30 min). For each of the lab's rows 1 to 8, write whether the outcome was CP or AP behaviour and what a grocery shopper would see.

Exercise 2 (45 min). For N = 5, list every (W, R) pair from 1 to 5, mark those with R + W > N, and state how many replicas can be unreachable before strict-mode writes and reads refuse.

Exercise 3 (1 hour). Run "Break it", then the stretch "second key with per-request W and R". Note which changes moved the system toward consistency and which toward availability.

Exercise 4 (1 hour). For three operations of a food-delivery app (place order, driver location, wallet balance), state the partition behaviour, a Cassandra, PostgreSQL or MongoDB setting that implements it, and how you would detect a failure.

Exercise 5 (2 hours). Draw the split-brain failure for your own system as a sequence diagram, with the checks that detect it and the rule that stops the old leader writing.

Related reading

• CAP, PACELC and Consistency Models: the overview and the full menu of consistency models.
• Replication: leaders, followers and lag.
• Consensus and Leader Election: how majorities avoid split-brain.
• IDs, Clocks and Ordering: the ordering tools behind merge rules.
• Distributed Transactions: one operation across several stores.
• ShopStream Stage 4: the same ideas on ShopStream's write path.
• Multi-Region and Disaster Recovery: consistency across regions.

Official documentation

• Gilbert and Lynch, Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services (ACM SIGACT News, 2002): the definitions and the proof.
• Gilbert and Lynch, Perspectives on the CAP Theorem (2012).
• Brewer, CAP Twelve Years Later: How the Rules Have Changed (2012).
• Abadi, Consistency Tradeoffs in Modern Distributed Database System Design (IEEE Computer, February 2012): PACELC.
• DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007).
• Apache Cassandra documentation (5.0): Dynamo architecture and tunable consistency, guarantees, hints.
• PostgreSQL 18 documentation: synchronous_commit, synchronous_standby_names, synchronous replication.
• MongoDB manual 9.0: write concern, read concern.