CAP Theorem
CAP is the most quoted — and most misunderstood — theorem in distributed systems. A distributed system can provide at most two of three guarantees: Consistency, Availability, Partition tolerance.
How it works
CAP is the most quoted — and most misunderstood — theorem in distributed systems. Eric Brewer conjectured in 2000, Gilbert and Lynch proved in 2002, that a distributed system can provide at most two of three guarantees: Consistency, Availability, Partition tolerance. The practical takeaway is sharper than the slogan: because partitions are inevitable on real networks, you are really choosing between C and A when a partition occurs. You cannot have all three.
Consistency (linearizability): every read sees the most recent write, as if there were a single copy. Availability: every non-failed node returns a response (not an error) for every request. Partition tolerance: the system continues to operate despite network partitions (dropped or delayed messages between nodes).
The common framing 'pick two' is misleading because Partition tolerance is not optional on a real network — partitions will happen, and your system must handle them. So the real choice is: when a partition occurs, do you (a) refuse to serve requests you cannot prove are correct (CP — sacrifice availability), or (b) serve requests with the data you have, accepting it may be stale (AP — sacrifice strong consistency)? Both are valid; the choice depends on the workload.
CAP does NOT say 'you cannot have consistency and availability at the same time.' It says you cannot have both during a partition. When the network is healthy (no partition), a well-designed system can be both strongly consistent and highly available. PACELC is a more precise formulation: if there is a Partition (P), choose between A and C; Else (E), choose between L (latency) and C.
CP systems: Google Spanner, HBase, MongoDB with majority write concern, any system using synchronous replication with quorum. They reject writes during partition rather than risk divergence. AP systems: Cassandra, DynamoDB, CouchDB, Riak — they accept writes on any reachable node and reconcile later (eventual consistency). CA systems: a single PostgreSQL instance. Not distributed, so no partition to tolerate — but also no fault tolerance.
What does CAP theorem actually guarantee about a distributed system?
Pick one answer.
You are designing a social media feed storage. Writes are user posts; reads are feed fetches. Which CAP trade-off makes sense?
Pick one answer.
The 'pick two' slogan is wrong. The popular framing — 'CAP says pick two of three: C, A, or P' — is misleading because P is not optional on a real network. Network partitions will happen: cables get cut, routers fail, switches reboot, configs get pushed wrong. If your system cannot tolerate partitions, it will fail every time the network hiccups.
The real theorem is sharper: during a partition, you must choose between C and A. You can have both when the network is healthy. This is why PACELC is a better model:
- P (if Partition): choose between A (availability) and C (consistency).
- E (Else — normal operation): choose between L (latency) and C (consistency).
Even when the network is healthy, strong consistency has a latency cost: you must coordinate (a quorum round, a Paxos round, a 2PC commit) before you can ACK. That coordination adds round-trips, which adds latency. So every distributed write implicitly chooses: do you pay the latency for strong consistency (CP), or do you ACK early and accept eventual consistency (AP)?
Cassandra (AP) vs Spanner (CP) — two design philosophies.
Cassandra was designed at Facebook for inbox search — a workload that needed to scale to billions of rows, survive any single node failure, and accept writes at very high throughput. The team chose AP: every node accepts writes, conflicts are reconciled later (last-write-wins by default, or custom conflict resolution), and the system is eventually consistent. Reads can be at ONE (any replica, may be stale), QUORUM (majority, strongly consistent if writes are also QUORUM), or ALL. The trade-off: writes never block on coordination, throughput scales linearly with nodes, but reads may return stale data unless you pay for QUORUM.
Spanner was designed at Google for AdWords billing — a workload where every dollar of ad spend must be correctly attributed, even across datacenters. The team chose CP: writes go through a Paxos leader, the leader synchronously replicates to a quorum across datacenters, and the write ACKs only after the quorum confirms. Spanner uses TrueTime (Google's GPS-synced atomic clocks) to give every transaction a globally-meaningful commit timestamp, enabling external consistency (linearizability across datacenters). The trade-off: writes have cross-datacenter latency (typically 10-100ms depending on regions), and during a partition, the minority side rejects writes.
The choice wasn't 'Cassandra is better' or 'Spanner is better' — it was 'which failure costs more for this workload?' Facebook inbox search: staleness is fine, throughput is critical → AP. Google billing: correctness is critical, can afford latency → CP. Same trade-off, opposite choices, both right for their workloads.
CAP only addresses what happens during a partition. But even when the network is healthy, strong consistency has a latency cost: you must coordinate (Paxos round, quorum write, 2PC) before ACKing. PACELC, introduced by Abadi in 2010, makes this explicit: if there is a Partition, choose between A and C; Else (normal operation), choose between L (latency) and C. Example systems: Spanner is PA/EL (sacrifices consistency both during partition and normally for latency? No — Spanner is PC/EC: prioritizes consistency in both cases, accepting higher latency). Cassandra is PA/EL: sacrifices consistency during partitions (PA) and also sacrifices consistency for latency normally (EL) — that's why Cassandra ONE reads are so fast. DynamoDB is PA/EL by default but tunable to PC/EC per request. The PACELC model captures that 'low latency' and 'strong consistency' are on opposite ends of a spectrum, even without partitions.
Cassandra's default consistency level is ONE for both reads and writes — read from one replica, ACK after one replica acknowledges the write. In PACELC terms, what is Cassandra?
Pick one answer.
Singapore-to-US network latency is ~180ms one-way. A synchronous cross-region write (CP) would ACK in ~360ms minimum. An asynchronous cross-region write (AP) ACKs in <50ms but the US region may not yet have the write.
You're designing a multi-region payment system. Each region processes payments locally for low latency. A user in Singapore pays $100; the Singapore region ACKs within 50ms. The user immediately checks their balance from a US session. What CAP choice should the system make, and what does the user see?
Engineering mental model
Mental model. Think of CAP Theorem as a deliberate boundary in a system. The boundary exists because something becomes harder to manage when everything is done in one place: latency, scale, failure isolation, consistency, cost, or team ownership. The useful question is not “what does CAP Theorem mean?” but “what pressure makes this boundary worth introducing, and what new failure mode does it create?”
Before choosing CAP Theorem, name the workload, the critical user path, the dominant bottleneck, the failure you are trying to absorb, and the trade-off you are willing to accept. If you cannot name those five things, the design is probably premature.
// Pseudocode
request = receive()
result = cap_theorem(request)
return result
// Production questions:
// 1. What happens on timeout?
// 2. Can this operation be retried safely?
// 3. What is the bottleneck?Back-of-the-envelope reasoning
Numerical lens: write down traffic, payload size, read/write ratio, peak multiplier and durability target before choosing a component. The numbers should justify the architecture.
Interactive thought experiment: CAP Theorem
Change the variables below and predict what breaks first in CAP Theorem. The production lab can later reuse these same inputs.
Change one variable at a time. Predict the failure mode first, then move the slider and see whether your mental model matches the simplified system response.
If you are stuck on CAP Theorem, start by drawing the request path and marking every network hop, stateful component, queue, cache and failure boundary. Then estimate where the system will saturate.
You increase traffic by 10× in a system using CAP Theorem. What should you inspect first?
Pick one answer.
Which statement is the safest engineering habit when using CAP Theorem?
Pick one answer.
You have dashboards for traffic, latency, errors and saturation. You can change the architecture, but every change has operational cost.
Production scenario: your system uses CAP Theorem, traffic suddenly spikes, and p99 latency doubles. What is your first move?
Interview drill
Answer this without notes: When would you choose CAP Theorem, and when would you intentionally avoid it? Mention at least one bottleneck it addresses, one failure mode it introduces, and one alternative. Then quantify the workload you are designing for.
A useful engineering lens for CAP Theorem: define the problem it solves, the simpler design that fails first, the constraint that forces you to introduce this concept, and the new failure modes the concept creates.
Numerical sanity check
Back-of-the-envelope reasoning beats fake precision. State your traffic, payload, concurrency and growth assumptions explicitly, then calculate enough to know whether the current architecture is orders of magnitude away from the target.
Do not optimize for a memorized definition. Reason from the workload and failure mode.
Imagine the simplest version of a system using CAP Theorem. What breaks first as traffic grows by 10×, and what would you change before reaching 100×?
Pick one answer.
What you gain, what you pay
- +Gives a clear vocabulary for the consistency-availability trade-off.
- +Helps you choose the right database class for each workload.
- +Forces explicit reasoning about partition behavior.
- −Frequently misquoted as 'pick two' when P is not optional.
- −Binary C vs A is too coarse — real systems are tunable (quorum sizes, consistency levels).
- −Does not address latency, which is often the real cost of strong consistency.
How this breaks in production
- Split-brain — network partition causes two primaries, divergent writes, data loss on heal.
- Stale reads — AP system serves outdated data that violates business invariants.
- Write unavailability — CP system rejects writes during partition, blocking users.
Don't fall into these traps
- •Quoting CAP as 'pick two of three' without acknowledging partitions are inevitable.
- •Assuming 'eventual consistency' means 'eventually correct' — it means eventually converged, which can still be wrong.
- •Choosing AP for everything. Some data (payments, inventory) demands CP.
- •Forgetting that CAP is about partition behavior, not normal operation.
Real systems using this
How real systems implement this
- Cassandra — AP system — accepts writes on any reachable node, reconciles via read-repair and anti-entropy.
- Google Spanner — CP system — synchronous replication with Paxos consensus, rejects writes during partition.
Practice saying it out loud
- Q1Explain CAP theorem. What does it really say?
- Q2Design a distributed counter (likes on a post). CP or AP? Why?
- Q3Your bank's ledger system must never lose a transaction. CP or AP? What are the implications?
- Q4PACELC extends CAP. Explain the difference.
Further reading & references
Core explanations are original NO CAP material. External references are provided for deeper study and standards.
What next?
Mark as understood once the mental model clicks.
Next recommended
Availability Patterns — Failover, Replication, Redundancy