CAP Theorem
The most cited and most misunderstood theorem in distributed systems. Interviewers test whether you actually understand it or just memorized 'pick two.'
The Concept Explained
CAP is stated over three properties, and the first thing to get right is what each one actually means, because the casual definitions are wrong in ways that make the theorem incoherent.
Consistency here means linearizability, not the C in ACID. Every read returns the most recent completed write, and the system behaves as though there were a single copy of the data. This is a much stronger and much narrower claim than "the data is valid."
Availability means every request to a non-failing node returns a non-error response. Not "the system is mostly up." Every request, every reachable node, a real answer rather than an error or a timeout.
Partition tolerance means the system continues to operate when the network drops or delays messages between nodes arbitrarily.
The theorem, proved by Gilbert and Lynch in 2002 from Brewer's earlier conjecture, says you cannot have all three simultaneously.
The popular summary is "pick two of three," and that summary is where nearly all the confusion comes from.
You do not get to pick two, because partition tolerance is not a choice. Networks partition. Cables are cut, switches fail, routes flap, and garbage collection pauses look identical to a partition from the outside. A distributed system that has not chosen partition tolerance has simply chosen not to handle something that will happen anyway.
Once P is compulsory, the theorem says something much narrower and much more useful: when a partition occurs, you must choose between consistency and availability. That is the whole content of CAP for a practitioner. It is a statement about behaviour during a specific failure, not a taxonomy of databases.
How It Works
The proof intuition takes about thirty seconds and is worth being able to give.
Two nodes hold a replica of the same value. The network between them fails, so no messages get through. A client writes a new value to node A. A different client reads from node B.
Node B has exactly two options. It can return the old value, which is not the most recent write, so consistency is violated. Or it can refuse to answer until it can reach node A, which means a non-failing node returned an error, so availability is violated. There is no third option, because the information physically has not arrived.
That is CAP. Everything else is application of it.
CP and AP Are Behaviours, Not Product Categories
A CP system, during a partition, refuses to serve requests it cannot serve correctly. The minority side of a partition typically stops accepting writes, and often stops serving reads too. It sacrifices availability to guarantee that whatever it does return is correct. This is what quorum systems do: without a majority you cannot make progress, by design.
An AP system, during a partition, keeps serving on both sides. Both sides accept writes, both may return stale data, and the divergence is reconciled after the partition heals. It sacrifices consistency to guarantee an answer.
The important nuance is that these are choices a system makes during a partition, and many real systems are configurable. Cassandra is usually described as AP but with a quorum consistency level it behaves as CP for those operations. The same cluster can be either depending on how a given query is issued, which is why labelling a database with two letters and stopping there is an imprecise answer.
Detecting a partition is itself unreliable, and this is where CAP gets uncomfortable in practice. A node that is slow, garbage collecting, or overloaded is indistinguishable from a node on the far side of a partition. Systems infer partitions from timeouts, so an aggressive timeout under load can trigger partition behaviour with no partition present.
The Part CAP Does Not Cover
CAP describes behaviour during a partition, and partitions are rare. A system spends the overwhelming majority of its life in the normal case, and CAP says nothing at all about that time.
This is the gap PACELC fills.
System Design Implications
PACELC, formulated by Daniel Abadi, extends CAP with the case CAP ignores. Read it as: if there is a Partition, choose between Availability and Consistency; Else, choose between Latency and Consistency.
PACELC: The Partition Case and the Normal Case
During a partition (PAC)
The rare case CAP describes
Normal operation (ELC)
The 99.99% of the time CAP ignores
The Else branch is the one that matters commercially, because it applies to every request rather than to a few minutes a year. Strong consistency in the normal case requires coordination, and coordination costs a round trip. If your replicas are in different regions, that round trip is tens or hundreds of milliseconds on every operation. Choosing consistency in the Else branch is a permanent latency tax, and it is usually a larger practical cost than the partition behaviour everyone argues about.
Classifying systems in PACELC terms is more informative than the two-letter version. Dynamo-style stores such as Cassandra are typically PA/EL: available during partitions, and fast rather than strictly consistent in normal operation. Systems built on consensus, such as those using Raft or Paxos for their replication, tend toward PC/EC: they refuse to serve without a quorum and they pay coordination latency in the normal case too.
How to Use This in a Design
Do not choose CP or AP for a system. Choose it per data type, because the correct answer genuinely differs within one product.
Payments, inventory decrements, and permission checks want consistency. Being unavailable during a partition is bad; double-spending, overselling, or granting revoked access is worse and often unrecoverable. These paths should refuse to operate without a quorum.
Feeds, view counts, presence indicators, and product recommendations want availability. Serving a slightly stale count during a partition costs nothing meaningful, and refusing to render a page because a counter service is unreachable is a self-inflicted outage.
The strongest answers in interviews split the system this way and defend each choice with the cost of being wrong, rather than declaring the whole architecture AP or CP.
If asked whether your design is CP or AP, the best opening is "during a partition, for which data?" It immediately signals that you know CAP is a per-operation behaviour during a specific failure rather than a badge worn by a database.
Tradeoffs and Decision Framework
| Consideration | Choose consistency (CP) | Choose availability (AP) |
|---|---|---|
| Cost of a wrong answer | High: money, inventory, access | Low: counts, feeds, recommendations |
| Cost of an error response | Tolerable | Unacceptable, user-facing |
| Behaviour on the minority side | Rejects requests | Serves and diverges |
| Conflict resolution needed | No, one truth is maintained | Yes: last write wins, vectors, or CRDTs |
| Normal-case latency | Higher, coordination per operation | Lower, answer from nearest replica |
| Typical mechanism | Quorum, consensus, leader | Multi-master, gossip, async replication |
The framework in three questions. First, what happens if two sides of a partition both accept a write to the same key: is the resulting divergence recoverable automatically, recoverable manually, or not recoverable? If not recoverable, you need CP for that path. Second, what does an error cost compared to a stale answer? Third, and separately, how much normal-case latency is coordination worth, since that bill arrives on every request rather than during rare failures.
Answer those three per data type and the architecture falls out. Answer them once for the whole system and you will have over-engineered the trivial paths and under-engineered the critical ones.
Common Mistakes
Saying "pick two of three." Partition tolerance is not optional in a distributed system, so it is not one of the picks. This phrasing is the single most common way to signal surface knowledge.
Confusing CAP's C with ACID's C. CAP consistency is linearizability, a statement about read recency across replicas. ACID consistency is about invariants within a transaction. Different concepts, same word.
Treating availability loosely. CAP availability means every request to every non-failing node gets a real response. It is not "the system has good uptime," and a system can be highly available in the operational sense while being CP in the CAP sense.
Labelling a database CP or AP permanently. Many systems are tunable per operation, and the same cluster behaves differently depending on the consistency level requested.
Ignoring the normal case entirely. Partitions are rare, coordination latency is constant. PACELC's Else branch is where the day-to-day cost lives.
Choosing one behaviour for the entire system. Payments and view counters want opposite answers, and a single global choice gets one of them wrong.
Forgetting that partition detection is guesswork. Timeouts cannot distinguish a partition from a slow node, so partition-handling logic fires during ordinary overload too.
Explain CAP theorem accurately. Why is 'pick two of three' misleading, and what does PACELC add?