The CAP theorem says that when a network fault splits replicated data into groups that cannot talk, each request must either get an answer that might be stale (giving up consistency) or get no answer (giving up availability). PACELC adds the other half: else, on a healthy network, every replicated read or write still trades latency against consistency. Together they explain why one part of your design waits and another answers fast.
Picture it first: two booking counters and a dead phone line
A small station has two booking counters, East and West, sharing one ledger of berths for the evening train. After every sale, the clerk phones the other counter so both copies match. One berth is left.
At 4 pm the phone line goes dead. One passenger asks East for the last berth; a minute later another asks West. Each clerk has two options:
- Sell anyway. Both passengers get a ticket, and when the line returns the clerks find one berth sold twice. The station stayed open (available), but the ledgers disagreed (inconsistent).
- Stop selling until the line is back. Nobody is double-booked, but passengers are turned away (consistent, not available).
No third option lets both counters keep selling without ever disagreeing, because neither clerk can learn what the other did. That is the CAP theorem.
Now take a normal day. A clerk who phones the other counter before confirming each sale never double-books, but is always slower than one who sells first and phones afterwards. That is PACELC’s “else”: even with no fault, coordination costs time.
Map it back: the counters are replicas, the phone line is the network, the ledger is replicated data (a seat map, a wallet balance, a cart), and the passengers are clients who will not wait forever.
The three letters, precisely
A little history first. Eric Brewer stated CAP as a conjecture in his keynote at the 2000 PODC symposium; Seth Gilbert and Nancy Lynch proved it in 2002, and their definitions are the ones that count. Daniel Abadi proposed PACELC in a 2010 blog post and set it out in IEEE Computer in 2012.
Because CAP is a theorem, its words have exact meanings. Most confusion comes from using the everyday ones.
C is linearizability. The system must behave as if there were a single copy of the data. Once a write is acknowledged to anyone, every read that starts afterwards, on any node, returns that value or a newer one. It is a recency guarantee for one object (a key or register), and it is not the C in ACID.
A means every non-failing node answers. Every request that reaches a live node must eventually get a non-error response. “Most requests succeed” is not enough, and neither is “some node answered”. Oddly, there is no deadline: a reply after two minutes still counts.
P means the network may lose messages. The system must keep its promises even when any number of messages between nodes are dropped or delayed. A very slow message looks exactly like a lost one, so this describes every real network; it is not a feature you choose.
Four misreadings come up again and again:
- “Pick any two.” You cannot pick “no partitions”. The real menu is: when a partition happens, give up C or give up A.
- “CP means the system is down.” Only the side that cannot reach enough replicas refuses requests. Everyone else carries on.
- “AP means no consistency.” AP gives up linearizability during a partition, and usually still offers eventual consistency or read-your-writes.
- “Consistency means data integrity.” CAP says nothing about foreign keys or multi-row transactions. It is about one object and how fresh a read is.
Why you can’t have all three during a partition
The proof is short enough to say out loud. Take two servers, G1 and G2, both storing x = 0.
- A partition starts. Every message between G1 and G2 is lost.
- Client A writes x = 1 to G1. Availability says G1 must reply, and it cannot wait for G2 forever, so it acknowledges the write.
- Client B then reads x from G2. G2 has not failed, so it must answer too.
- G2 has heard nothing. Its world looks exactly like one where nobody wrote anything, so it must behave the same way in both.
- If G2 answers 0, a read that started after the write missed it: consistency is broken. If G2 waits or errors, availability is broken.
There is a subtler point in step 2. A server cannot tell a cut link from a slow one, so a system that promises to always answer will sometimes answer wrongly even when no partition exists.
So think of CAP as a timeout decision. When a replica waits on another and the timer fires, it must either cancel (lose A for that request) or proceed without confirmation (risk C). Retrying only postpones the choice, and a tight timeout makes the system treat “slow” as “partitioned” more often.
CP vs AP: what each choice looks like in practice
CP: refuse rather than diverge
A CP system commits a write only when a majority of replicas agree. During a partition, the majority side keeps working; the minority side returns errors or blocks until it can reach the others.
- etcd runs reads and writes through the Raft consensus protocol and is linearizable by default.
- ZooKeeper needs a majority to process writes, so its minority side cannot accept them.
- Spanner replicates through Paxos groups; if a group’s leader cannot hold a quorum, its updates stall. Brewer calls it “technically CP”.
You gain one copy of the truth: invariants such as “a berth is sold once” hold even if nobody wrote them down. You pay with errors for clients stuck on the minority side, a write pause of about one election timeout while a new leader is elected, and 2f + 1 replicas to survive f failures (3 replicas tolerate 1 failure, 5 tolerate 2).
AP: answer now, reconcile later
An AP system lets every reachable replica accept reads and writes. The two sides drift apart and are merged once the network heals.
- Dynamo (the 2007 design) was built to be “always writeable”: rejecting an add-to-cart was judged worse than fixing a conflict later.
- Cassandra at consistency level ONE answers as long as any one replica is reachable.
- DynamoDB global tables in their default multi-Region eventual mode accept writes in every Region and typically replicate them within a second.
You gain an answer for every user on both sides. You pay with conflicts. Last-write-wins is simple but silently drops a write. Version vectors plus an application merge keep both, as in Dynamo’s cart, where an added item is never lost but a deleted one can reappear. And you must know your invariants up front, because the database no longer protects them.
Labels describe a configuration, not a product
Most stores let you choose per request: Cassandra takes a consistency level per query, DynamoDB a ConsistentRead flag per read, and etcd lets a read skip consensus. Martin Kleppmann’s 2015 essay “Please stop calling databases CP or AP” goes further: many popular setups meet neither strict definition. A single-leader database with asynchronous read replicas cannot take writes on the leader’s far side (not CAP-available), and its replica reads can be stale (not CAP-consistent). Say “this operation, with this setting, behaves CP”, not “this database is CP”.
PACELC: the trade-off that exists even without failures
CAP only covers partitions, which are rare, yet many databases serve stale reads on perfectly normal days. The reason is the cost CAP leaves out: latency.
PACELC (say “pass-elk”) states both halves: if there is a Partition, choose Availability or Consistency; Else, choose Latency or Consistency.
The else trade-off exists because availability forces replication, and replication forces a choice. A write can wait for other replicas before it is acknowledged (consistent, slower) or be acknowledged first and copied later (fast, but replicas lag). Reads face the same fork: ask the leader or a quorum, or ask the nearest copy. Inside one data centre the gap is a millisecond or two; across regions no trick removes it.
Physics sets the floor. Light in fibre travels about 200,000 km per second, so every 1,000 km adds roughly 10 ms of round trip. Mumbai to Singapore is about 3,900 km in a straight line, so at least 40 ms per round trip, and real fibre routes are longer.
This is why PACELC often explains real designs better than CAP. Dynamo-style stores serve web pages where even 100 ms of extra delay drives users away, so they skip coordination on the normal path (EL); having written reconciliation code anyway, they also stay writeable during partitions (PA). The halves can differ, too: PNUTS, an older geo-distributed store, served reads from local replicas (EL) but made a record read-only when its home replica was unreachable (PC).
Skipping the wait also opens a durability window: if the local site dies before the write reaches another region, the write is gone.
Classifying real systems
Read the table as “typical configuration, per operation”, not a permanent label. Abadi’s 2012 paper classifies the Dynamo-style stores, MongoDB and PNUTS directly; the other rows apply the same two questions to each system’s documentation.
| System and setup | During a partition | Else (normal operation) | PACELC | What changes the answer |
|---|---|---|---|---|
| Dynamo-style store (Cassandra, Riak) at ONE or low R and W | Any reachable replica answers | Fastest replica answers; may be stale | PA/EL (Abadi) | QUORUM reads and writes: minority side fails, reads are fresher, closer to PC/EC |
| DynamoDB, single Region | Hidden inside the service | Default reads are eventually consistent | EL for default reads | ConsistentRead gives EC reads at twice the cost; global secondary index reads are always eventual |
| DynamoDB global tables, default eventual mode | Each Region keeps accepting writes and catches up later | Local acknowledgement; replicated typically within a second | PA/EL | Strong mode replicates to another Region before acknowledging, so an isolated Region cannot complete writes: PC/EC |
| etcd | Majority side stays available; minority side does not | Reads and writes go through Raft | PC/EC | Serializable reads are served locally: EL for those reads |
| ZooKeeper | Minority side cannot write | Reads come from the connected server and can lag | PC, with EL reads | sync before a read makes it current |
| Spanner | A Paxos group without a quorum stalls | Writes wait for a majority | PC/EC | Snapshot reads at a past timestamp can use a nearby replica |
| Single-leader SQL with async replicas | Only the leader’s side can write | Replica reads are fast but can lag | PC/EL, the same shape as PNUTS | Send every read to the leader for EC |
| MongoDB replica set | The majority elects a new primary; writes the old primary had not replicated are set aside for rollback | Reads and writes go to the primary | PA/EC (Abadi, 2012) | With majority write concern plus majority or linearizable reads it behaves close to PC/EC; secondary reads make it EL |
Tunable consistency and quorums
Quorums are the most common way to slide along the C-versus-L line. Three numbers describe them:
- N: replicas that store each key.
- W: replicas that must acknowledge a write.
- R: replicas that must reply to a read.
If R + W > N, every read set overlaps every write set in at least one replica. So each read reaches at least one replica holding the latest acknowledged write, and the reader keeps the newest version it receives.
Here is how the common settings compare for N = 3 and N = 5:
| N, W, R | R + W > N? |
Writes survive | Reads survive | Feel |
|---|---|---|---|---|
| 3, 1, 1 | No (2) | 2 replicas down | 2 replicas down | Fastest; stale reads are normal |
| 3, 2, 2 | Yes (4) | 1 down | 1 down | Balanced; the Dynamo paper’s most common setting |
| 3, 3, 1 | Yes (4) | 0 down | 2 down | Fast reads, fragile writes |
| 3, 1, 3 | Yes (4) | 2 down | 0 down | Fast writes, fragile reads |
| 5, 3, 3 | Yes (6) | 2 down | 2 down | Survives a node in maintenance plus a crash |
A quorum operation is only as fast as the slowest replica it must hear from, so every extra replica you wait for trades latency for freshness or fault tolerance.
Cassandra wraps this in named consistency levels: ONE, QUORUM (a majority, so 2 of 3), ALL, and LOCAL_QUORUM, a majority inside the caller’s data centre only. LOCAL_QUORUM is the usual multi-region compromise: a user homed in Mumbai reads their own writes without a round trip to Europe.
R + W > N is not a linearizability guarantee
Overlap means a read reaches a fresh replica, not that the system acts like one copy. Sloppy quorums can count stand-in nodes outside the usual N, a write that fails after reaching one replica can appear in some reads but not others, and last-write-wins with skewed clocks can discard the newer value. For operations that truly need linearizability, such as claiming a username or selling the last unit, use a consensus-backed compare-and-set.
Going deeper: misconceptions and failure modes
“CA” is not a real option for a distributed system
A single-node database is trivially consistent and available, but it is not distributed, and it dies with its one machine. Once data lives on two machines, a partition can happen whether you planned for it or not, and a system that “does not tolerate partitions” still stops answering on at least one side. That is CP in disguise.
The honest version of “CA” is probabilistic. Writing about Spanner in 2017, Brewer called it technically CP but “effectively CA”: on a private network with redundant paths, network problems caused under 8% of its incidents, and availability beats five nines (99.999%), so most callers simply assume it is up.
The C in CAP is not the C in ACID
ACID consistency means a transaction keeps the data valid: unique keys stay unique, a wallet balance never goes below zero. CAP consistency means a read sees the latest acknowledged write of one object. They are independent. A database can offer serializable transactions without being linearizable (common with snapshot-based concurrency control), and a linearizable key-value store can still let you break a rule that spans two keys.
Partitions are rare, but they have a long tail
A partition is not just a cut cable. It can be a misconfigured switch, a one-way link where traffic flows in only one direction, or a long garbage-collection pause that makes a healthy node look dead. Brewer’s 2017 note recalls that the original paper on Google’s Chubby lock service mentioned nine outages of 30 seconds or more in 700 days, six of them network-related. Write down your partition plan, even if it is “refuse writes for this key range”.
CAP availability is stricter than your SLA, and looser
An SLA such as “99.95% of requests succeed within 1 second” can be met by a CP system if the load balancer steers traffic away from the minority side. An AP system that answers after two minutes is CAP-available but useless. When you say “available”, say which meaning you intend.
Split brain
The worst failure is a CP system that accidentally behaves like AP. An old leader is cut off, does not notice, and keeps accepting writes while the majority elects a new one; one side’s writes are later lost or rolled back. The defences: majority quorums for every write, leader leases that expire before a new leader can be elected, and fencing tokens (a number that grows with each leader term) so storage rejects a stale leader.
Plan the recovery, not just the choice
Partition-aware systems work in three steps: detect the partition, enter a partition mode that limits risky operations, and recover by merging histories and compensating for mistakes. A payment-style flow should record the intent and show “pending” rather than debit money it cannot confirm.
Choosing in a design interview
Ask one question per operation: what does a wrong answer cost, compared with no answer? If a wrong answer creates or destroys money or double-sells something scarce, choose C. If an error hurts more than a few seconds of staleness, choose A and plan the merge.
| Feature | Cost of a stale or wrong answer | Cost of no answer | Choose |
|---|---|---|---|
| UPI-style ledger or wallet debit | Money created or lost | User retries; payment shows “pending” | CP, PC/EC |
| Tatkal berth allocation | Two passengers, one berth | User retries within seconds | CP for the seat hold |
| Train search and availability counts | Shows 12 left when 10 remain | Nobody can browse during the 10 am rush | AP/EL, re-check at booking |
| Likes and view counters | Off by a few for seconds | Like button errors | AP/EL |
| Social feed | A post appears seconds late | Blank feed | AP/EL |
| Delivery partner’s live location | Pin is 3 seconds old | Map freezes | AP/EL |
| Leader election, locks, config | Two leaders; corrupted data | Cannot change leader for a while | CP (etcd or ZooKeeper) |
| Shopping cart | A deleted item reappears | Customer cannot add to cart | AP with a merge |
In the interview
Mix the choices inside one design and say so. In a tatkal-style booking flow, search and availability counts are AP/EL from caches, the seat hold and the payment are CP, and the confirmation SMS is asynchronous and retried. Interviewers listen for “for this operation”, not one label for the whole system.
Cheat sheet
| Term | Remember it as |
|---|---|
| C (CAP) | Linearizable: acts like one copy; reads that start after an acknowledged write see it |
| A (CAP) | Every live node answers every request; no deadline, no errors |
| P | The network can drop or delay messages; not optional |
| CAP | During a partition, choose C or A per operation |
| PACELC | If partition: A or C; else: latency or consistency |
| CP behaviour | Majority side works, minority side errors; 2f + 1 replicas survive f failures |
| AP behaviour | Everyone answers; replicas diverge; merge with LWW, version vectors or CRDTs |
| Quorum rule | R + W > N makes read and write sets overlap; the slowest replica you wait for sets latency |
| Common defaults | Dynamo-style PA/EL; etcd and Spanner PC/EC; one leader plus async replicas PC/EL |
| Physics | About 10 ms of round trip per 1,000 km of fibre |
How to say it in the interview
“CAP says that during a network partition, a replicated system must choose, per request, between answering with possibly stale data and refusing to answer. Partitions aren’t optional, so it’s really C versus A, and only while the partition lasts. PACELC adds that on normal days I’m still trading latency against consistency, because every replica I wait for costs a round trip. Here, the booking ledger is PC/EC: majority writes, and the minority side returns a retryable error. Availability counts and the feed are PA/EL: nearest replica, a few seconds stale. Across regions, I’d home each user’s writes in one region and use local quorums.”
Why not just choose CA? You cannot choose to have no partitions. A system that ignores them still has to stop or diverge when one happens, so “CA” really means “CP, and we hope partitions are rare”.
Is Cassandra AP? At ONE, yes: PA/EL. With QUORUM reads and writes, the minority side fails those requests and reads see the latest acknowledged write, much closer to PC/EC. The label belongs to the consistency level, not the product.
Does R + W > N give you linearizability?
Not by itself. Sloppy quorums, partially failed writes and clock-based conflict resolution can still produce non-linearizable results. Use consensus for operations that truly need it.
How can Spanner be consistent and highly available? It is CP: a group without a majority stalls. But partitions on its redundant private network are so rare that measured availability exceeds five nines. Technically CP, effectively CA.
What happens to writes accepted on both sides in an AP system? They conflict when the partition heals. Resolve them with last-write-wins (simple, loses data), version vectors plus an application merge (keeps both, more code), or CRDTs (self-merging counters and sets).
Where to go next
- Strong vs eventual consistency: the levels between linearizable and “eventually”, and their costs.
- Quorums and leaderless replication: sloppy quorums, hinted handoff and read repair.
- Data replication: leader-based and leaderless replication, and where lag comes from.
- Consensus and leader election: how Raft and Paxos give CP systems one history.
- Clocks, ordering and conflict resolution: version vectors, last-write-wins and CRDTs.
- Cassandra and DynamoDB: tunable consistency in production.
- Multi-region and active-active: PACELC across thousands of kilometres.
- Contention and double booking: “one berth, many buyers” patterns.
References and further reading
- Perspectives on the CAP Theorem (Gilbert and Lynch, IEEE Computer, 2012)groups.csail.mit.eduThe authors of the original 2002 proof restate the theorem and its two-server proof sketch, and frame it as safety versus liveness.
- CAP Twelve Years Later: How the “Rules” Have Changed (Brewer, IEEE Computer, 2012)infoq.comWhy “two of three” misleads, the timeout as the partition decision, and how to detect, operate through and recover from partitions.
- Consistency Tradeoffs in Modern Distributed Database System Design (Abadi, IEEE Computer, 2012)cs.umd.eduThe PACELC paper: why replication forces a latency-versus-consistency trade-off, with PA/EL, PC/EC and PC/EL examples.
- Please stop calling databases CP or AP (Kleppmann, 2015)martin.kleppmann.comThe precise CAP definitions, and why many real systems are neither CAP-consistent nor CAP-available.
- Spanner, TrueTime and the CAP Theorem (Brewer, 2017)static.googleusercontent.comHow a globally consistent database is “technically CP” yet “effectively CA”, with incident and availability data, including the Chubby outage figures.
- Dynamo: Amazon’s Highly Available Key-value Store (DeCandia et al., SOSP 2007)allthingsdistributed.comThe classic always-writeable design: N, R and W, sloppy quorums, hinted handoff and application-level merges.
- Apache Cassandra documentation: Dynamo architecture and tunable consistencycassandra.apache.orgConsistency levels (ONE, QUORUM, LOCAL_QUORUM, ALL) and how they map to R + W > RF.
- Amazon DynamoDB Developer Guide: Read consistencydocs.aws.amazon.comEventually versus strongly consistent reads, their relative cost, and the two consistency modes for multi-Region global tables.
- etcd API guaranteesetcd.ioA consensus-backed store that is linearizable by default and offers faster serializable reads as an opt-in.
- etcd failure modesetcd.ioWhat a CP system does in practice: the majority side stays available, the minority side does not, and writes pause during leader election.