CAP and PACELC: The Tradeoff That Keeps Confusing People

TL;DR: CAP is an impossibility result: during a network partition, a distributed data store must choose between linearizable consistency and availability^[1]. It does NOT say "pick 2 of 3." PACELC extends the idea: even without a partition, you still trade consistency for latency^[2]. Every database lands somewhere on this spectrum. Use PACELC to force precise design conversations, not to assign bumper-sticker labels.

Learning Objectives#

After this module, you will be able to:

• State CAP precisely and dismantle the "pick 2 of 3" misconception
• Explain the Gilbert-Lynch proof in one paragraph
• Apply PACELC to classify real systems (PC/EC, PA/EL, PC/EL, PA/EC)
• Calculate quorum overlap requirements (R + W > N) and identify when they fail
• Use harvest and yield to reason about graceful degradation
• Push back productively when a colleague says "we picked CA"

Intuition#

Imagine a bank with two branches connected by a phone line. Both branches can see the same account balance. A customer walks into Branch A and withdraws $500. The teller updates the ledger and tries to call Branch B to sync. But the phone line is down.

Now a second customer walks into Branch B and asks for the balance. The Branch B teller has two choices:

1. Refuse to answer until the phone line comes back. The customer waits (or leaves angry). The bank stays correct but becomes unavailable.
2. Answer with the old balance. The customer is served, but the answer is wrong. The bank stays available but becomes inconsistent.

There is no third option while the phone line is down. That is CAP.

The part everyone forgets: even when the phone line works, calling Branch A before every transaction adds delay. A bank that synchronizes on every operation is slow. One that does not is fast but occasionally stale. That is the latency-vs-consistency axis that PACELC adds.

Theory#

CAP: what it actually says#

Eric Brewer conjectured at PODC 2000 that a distributed shared-data system cannot simultaneously guarantee consistency, availability, and partition tolerance^[3]. Gilbert and Lynch formalized and proved this in 2002^[1:1]. The precise statement:

• C (Consistency): every read returns the most recent write or an error. Formally, this means linearizability.
• A (Availability): every request to a non-failed node receives a non-error response.
• P (Partition tolerance): the system continues operating despite arbitrary message loss between nodes.

The critical correction: partitions are not a design choice. Networks partition. Fiber gets cut. Switches fail. BGP misconfigures^[4]. The real question is: when a partition happens, do you sacrifice C or A?

Brewer himself corrected the "2 of 3" framing in his 2012 IEEE retrospective^[5]:

1. Partitions are rare but inevitable. You cannot "give up P" in a distributed system.
2. The choice is not binary or permanent. Different operations, different data, different partitions can get different answers.
3. Design for partition recovery, not just partition response.

The Gilbert-Lynch proof in one paragraph#

Split N nodes into two groups, G1 and G2, with no communication between them. A client writes value v1 to G1. G1 must acknowledge (by availability). A client reads from G2. G2 cannot distinguish "G1 is slow" from "G1 is partitioned" in an asynchronous network. G2 must respond (by availability), but it has not seen v1, so it returns stale data (violating linearizability). The only escape: G2 refuses to respond, violating availability. QED^[1:2][6].

During a partition, G2 cannot distinguish "G1 slow" from "G1 unreachable." Any response violates either consistency or availability.

PACELC: the rest of the story#

Daniel Abadi observed in 2010 that CAP only describes partition behavior, but partitions are rare^[7]. Most of the time, the dominant trade-off is consistency vs. latency: stronger consistency forces more replicas to coordinate per operation, adding round trips.

PACELC reformulates the principle^[2:1]:

• If Partition (P): choose Availability (A) or Consistency (C)
• Else (E): choose Latency (L) or Consistency (C)

Every system gets a four-letter classification:

PACELC forces two decisions: behavior under partition (A or C) and behavior in normal operation (L or C). Most internet-scale systems are PA/EL; most financial systems are PC/EC.

"CP" and "AP" in practice#

CP systems use consensus-based replication (Paxos, Raft, Zab). A cluster of N nodes requires a majority quorum to make progress. During a partition, the minority side stops accepting writes. Users on that side see errors, but they never see stale or divergent data.

• Spanner: Paxos per split + TrueTime. Five nines availability^[9], but minority partitions are unavailable.
• etcd/ZooKeeper/Consul: Raft or Zab quorum. Jepsen's tests of etcd 3.4.3 observed strict serializable behavior for key-value operations^[10].
• MongoDB (majority write concern): primary steps down if it cannot reach majority.

AP systems use leaderless or multi-master replication. Every reachable replica accepts writes; divergences reconcile later via LWW, vector clocks, or CRDTs.

• Cassandra (default): tunable N/R/W. At consistency ONE, both sides of a partition keep serving.
• DynamoDB (default reads): eventually consistent. Strong reads available at 2x cost^[11].
• Riak: pure Dynamo-style. Designed for always-writable semantics.

Quorum math#

Dynamo-style systems expose three parameters: N replicas per key, writes acknowledged by W replicas, reads from R replicas^[13]. The key invariant:

R + W > N guarantees that read and write quorums overlap on at least one replica.

That overlapping replica has the latest write, so the reader can detect it.

When R + W > N, at least one replica participates in both the write quorum and the read quorum, guaranteeing the reader sees the latest write.

Common configurations:

• N=3, R=2, W=2: overlap of 1. Strong single-key reads. Cassandra LOCAL_QUORUM.
• N=3, R=1, W=3: all replicas must ack writes; reads are fast but writes are slow.
• N=5, R=3, W=3: overlap of 1. Tolerates 2 failures for both reads and writes.

Harvest and yield#

Fox and Brewer (1999) proposed two continuous metrics for graceful degradation^[14]:

• Yield: the fraction of requests that receive a response (analogous to availability).
• Harvest: the fraction of data reflected in a response (completeness).

Traditional CAP treats availability as binary. Harvest/yield exposes a spectrum: a search engine can return results from 90% of its shards during a partial failure (high yield, reduced harvest) rather than refusing all queries (zero yield, full harvest). A balance-transfer system cannot trade harvest (a wrong answer breaks the bank); it must trade yield^[14:1].

This maps directly to real design decisions:

• Search/social feeds: serve partial results. Users tolerate incomplete results better than timeouts.
• Financial transactions: reject the request. Users tolerate "try again" better than wrong balances.
• Analytics dashboards: show stale data with a "last updated" timestamp. Bounded staleness is explicit harvest reduction.

Real-World Example#

Redis Sentinel: 56% write loss in 42 seconds.

Redis uses asynchronous primary-to-secondary replication for low latency (PA/EL). Redis Sentinel is a separate fleet of monitor processes that detect primary failure and promote a new primary. This combination creates a textbook split-brain scenario.

In Jepsen's 2013 test of a 5-node Redis Sentinel cluster^[15]:

1. A network partition isolates the primary (node 1) and one secondary (node 2) on the minority side.
2. Clients on the minority side continue writing to the old primary, which acknowledges every write.
3. Sentinels on the majority side (3 of 5) detect the primary as unreachable and promote a secondary to new primary.
4. Clients on the majority side write to the new primary.
5. When the partition heals, Sentinel demotes the old primary. It discards all writes it accepted during the split.

Result: 1,126 of 1,998 acknowledged writes lost, a 56% loss rate in a 42-second partition window^[15:1].

During a partition, the old primary keeps accepting writes while Sentinel promotes a new primary on the majority side. On heal, the old primary's writes are silently discarded.

Root cause: asynchronous replication (chosen for latency) combined with automatic failover (chosen for availability) without consensus on the data path. The failover protocol has quorum, but the replication does not^[16].

What changed: Redis documentation now explicitly warns that "Sentinel + Redis distributed system does not guarantee that acknowledged writes are retained during failures"^[15:2]. Kingsbury's recommendation: use Redis as a cache, not as a primary data store or lock service.

Lesson for designers: if your system uses async replication + automatic failover, you will lose acknowledged writes during partitions. This is not a bug; it is the PA/EL trade-off made concrete. If write loss is unacceptable, use consensus-based replication (Raft, Paxos) or require majority acknowledgment before responding.

Trade-offs#

The four rows are the quadrants of Abadi's 2x2 PACELC taxonomy. They are exhaustive and mutually exclusive by construction, so readers classify a system into exactly one row rather than picking among alternatives.

Our pick: Use PC/EC (Spanner, CockroachDB) for financial data, uniqueness constraints, and anything where a wrong answer costs more than a slow answer. Use PA/EL (DynamoDB, Cassandra) for shopping carts, social feeds, session stores, and analytics where staleness is tolerable and availability drives revenue.

Common Pitfalls#

Exercise#

Problem: You have a Dynamo-style cluster with N=5, R=2, W=3. (a) Does R + W > N hold? (b) Is this configuration strongly consistent for single-key reads? (c) A network partition splits the cluster into {1, 2} and {3, 4, 5}. Can the majority side still accept writes? Can the minority side? What happens to reads on each side?

Key Takeaways#

• CAP says: during a partition, choose C or A. Partitions are inevitable; "CA" is not a real distributed option.
• The "pick 2 of 3" framing is wrong. Brewer corrected it in 2012. The real choice is per-operation behavior under specific failures.
• PACELC adds the missing axis: in normal operation, you trade consistency for latency. This is the trade-off you live with every day.
• R + W > N guarantees quorum overlap for a single key on the same N replicas. Multi-DC LOCAL_QUORUM can violate this silently.
• Async replication + automatic failover = silent write loss during partitions. Redis Sentinel lost 56% of acknowledged writes in a 42-second test^[15:3].
• Harvest and yield turn CAP's binary into a spectrum: serve partial results (search), reject requests (banking), or show stale data with a timestamp (dashboards).
• Use PC/EC for money. Use PA/EL for carts and feeds. Use PACELC to force the conversation, not to assign labels.

Further Reading#

• Brewer, "CAP Twelve Years Later," IEEE Computer, 2012 - Brewer's own correction of the "2 of 3" myth; the definitive framing of CAP as a partition-time choice.
• Gilbert and Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services," 2002 - the original proof; short, constructive, and still the clearest formal statement.
• Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design," IEEE Computer, 2012 - the PACELC paper; read this to understand why latency matters more than partition behavior for daily operations.
• Kleppmann, "Please stop calling databases CP or AP," 2015 - the critique that explains why single-letter labels hide layered reality; essential for nuanced design reviews.
• Kleppmann, "A Critique of the CAP Theorem," arXiv, 2015 - the formal version of the critique; proposes delay-sensitivity as a replacement framework.
• Fox and Brewer, "Harvest, Yield, and Scalable Tolerant Systems," HotOS, 1999 - the conceptual precursor to tunable consistency; introduces the continuous trade-off that CAP's binary hides.
• Bailis and Kingsbury, "The Network is Reliable," CACM, 2014 - empirical catalog of real-world partitions from switch firmware bugs to entire DC disconnects.
• Jepsen analyses - Kingsbury's test results for MongoDB, Cassandra, etcd, Redis, CockroachDB, and more; what databases actually do under partition vs. what marketing claims.
• DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store," SOSP, 2007 - the canonical AP design with N/R/W quorums and shopping-cart union-merge semantics.
• Brewer, "Inside Cloud Spanner and the CAP Theorem," 2017 - the "effectively CA" argument; understand both why Brewer has a point and why Kleppmann disagrees.

Flashcards#

References#