What is the CAP theorem, and what does it really say?

In this article

1. Before you start
2. Why interviewers ask this
3. CAP theorem from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page needs only two ideas.

Why interviewers ask this

The theorem is a quick way to test whether a candidate can reason about failure instead of reciting a slogan. Any design that stores data on more than one machine, such as a cache, a chat system or a payment ledger, eventually meets the question "what happens when the machines cannot talk to each other?"

A weak answer says "you pick two of three, so we pick availability and partition tolerance" and stops. A strong answer says that partitions are not optional, that the real choice is consistency or availability while a partition lasts, and that this choice can differ by operation. A Staff-level answer adds that the theorem is only part of the story: even with no partition, replication trades consistency against latency, which is where the question usually goes next.

CAP theorem from first principles

CAP theorem

The CAP theorem is a result about replicated data systems that says that while the network is partitioned, the system cannot both answer every request and always return the latest written value. Gilbert and Lynch proved Brewer's 2000 conjecture in 2002.

Network partition

A network partition is a failure in which messages between two groups of machines are lost or delayed, so each group keeps running but cannot hear from the other.

In plain words

Picture two bank branches that keep one shared ledger by telephone. Each time one branch records a deposit, it phones the other. Now the phone line goes down. A customer walks into the second branch and asks for the balance. The branch can refuse to answer until the line is back, or it can quote its own, possibly outdated, figure. The analogy breaks in one place: a real database node cannot tell whether the phone is dead or the other branch has closed, because from inside, both look like silence.

In one precise sentence, when the link between replicas fails, each replica must either refuse requests it cannot verify or answer them and risk returning stale data. Gilbert and Lynch (2002) state the three properties and note that it is impossible to achieve all three; they prove it in the asynchronous network model.

Step 1: Name the three properties and the two replicas

Consistency here means linearizability: every read sees the latest write, as if one copy existed. Brewer (2012) describes it as having a single up-to-date copy of the data. Availability means every request to a working node receives a real answer rather than an error or a hang. Partition tolerance means the system keeps operating when the network drops messages between nodes.

Take the smallest case: two replicas, A and B, each holding a copy of a value called x, and a link that copies every write from one to the other. Input: a write. Output: both copies updated. While the link works, the system is consistent and available, and nothing is in tension.

Step 2: A partition cuts the link

A partition cuts the link between A and B. Both machines are still running and both still accept clients, but neither hears from the other. Each side knows only that messages have stopped.

You cannot design this away, because any network between separate machines can lose or delay messages, so a system that spans machines must decide what to do when it happens. That is why the common claim that you can simply choose a design that is consistent and available but not partition tolerant (CA) is not a real option for a replicated system. What changed: the replicas can no longer share writes. The next step shows why that forces a decision.

Step 3: A write and a read during a partition force a choice

During the partition, a client writes a new value of x to replica A. A accepts it. A write reaches one replica and a read hits the other: a second client reads x from replica B. B never received the write.

B has two options. It can return an error or wait until the link heals; the system stays consistent but B is not available. Or it can return its old value; B is available but the answer is stale. A system built to refuse is called consistent under partition (CP); one built to answer is called available under partition (AP).

No third option exists, and the sketch below shows why. The choice applies only while the partition lasts: when no messages are being lost, nothing stops a system from being both consistent and available. Brewer's own correction (Brewer, 2012) is that "by explicitly handling partitions, designers can optimize consistency and availability, thereby achieving some trade-off of all three", rather than losing one for good.

1 · Replicas2 · Partition3 · Write, read, chooseReplay

Step-by-step description

1. Two replicas copy writes to each other.
2. The link between them is cut.
3. The replica that missed the write must err or answer stale.

• Two replicas hold copies of the same data.
• A partition drops messages between them.
• A write reaches one replica and a read hits the other.
• The second replica must return an error or a stale value.

Why there is no third option

Suppose a system stayed both available and consistent during the partition. The write to A succeeded, so the new value is the latest. Replica B must answer the read, because the system is available, and the answer must be the latest value, because the system is consistent. But B has received nothing from A, so it cannot know the new value. The two requirements contradict each other.

This is the heart of the proof by Gilbert and Lynch; the full argument is in their paper. In short, the only way for B to know the new value would be to hear from A, and the partition is exactly the condition under which that message cannot arrive. Waiting forever breaks availability, and guessing breaks consistency, so every design must give up one of the two for the length of the partition.

Worked example

Replication choices are often tuned with quorums. A quorum is a minimum number of replicas that must acknowledge an operation before it counts as done. Take three replicas, N = 3. A write waits for W acknowledgements and a read waits for R. If R plus W is greater than N, every set of replicas that answers a read overlaps every set that acknowledged the latest write, an overlap rule that goes back to Gifford (1979).

The read set therefore contains at least one replica with the latest acknowledged write, and the client keeps the highest version number or timestamp it sees. That alone does not give linearizability: sloppy quorums, concurrent writes and a missing read-repair or write-back step can still return stale or non-linearizable reads. Of the nine combinations of W and R from one to three, six have W plus R above N; these settings are illustrative, and the sums come from a short script.¹

In the constructed two-replica trace, both copies of x start as "old". After a partition, a write sets x to "new" on A. A read at B under a refuse-first policy returns an error; under an answer-first policy it returns "old".¹

Text description of the diagram

• The sum of write acknowledgements and read acknowledgements is 2 for one and one.
• The sum is 4 for two and two, three and one, and one and three.

Quorums connect back to CAP. With three replicas and W = 2, R = 2, a partition that isolates one replica leaves two on the majority side. That side can still read and write, and it can stay consistent if reads also repair stale replicas. The isolated replica cannot reach two acknowledgements, so clients cut off with it get errors. The system is available only on the majority side.

Trade-offs and edge cases

Neither choice is free, and the right one depends on the operation.

Text description of the diagram

• A consistency-first design returns an error or waits on the cut-off side.
• An availability-first design answers from its local copy, so reads can be stale.
• An availability-first design must merge conflicting writes after healing.

A consistency-first design returns an error or waits on the cut-off side, so reads are never stale and healing is simple; it suits balances and locks. An availability-first design answers from its local copy, so reads can be stale and conflicting writes must be merged after healing; it suits feeds and counters. For money, a design discussion should favour refusing over inventing a balance; see how the payment system design applies this.

Four edge cases matter.

• The C is not the database C. CAP's consistency is single-copy consistency, which Brewer (2012) calls a strict subset of the consistency in atomicity, consistency, isolation, durability (ACID).
• Eventual consistency is not automatically better. Eventual consistency is a promise that if writes stop, all replicas converge to the same value. Kleppmann (2015) argues that the common reading, that it beats strong consistency on availability, needs "more careful reasoning" than CAP alone provides.
• CAP is only part of the story. Abadi (2012) argues that the theorem's impact on real database design is more limited than is often perceived, because a trade-off between consistency and latency arises as soon as data is replicated, even with no partition. His formulation, PACELC (if partition, availability or consistency; else, latency or consistency), joins the two. Waiting for far-away replicas also feeds tail latency, the slowest few requests that users notice.
• The choice can differ per operation. One system can refuse writes to a ledger while serving stale reads of a product page.

Named systems show how the labels are used. Abadi (2012) places the default versions of Dynamo, Cassandra and Riak at partition-availability (PA) with else-latency (EL): availability in a partition, else latency. He places MongoDB at PA with else consistency (EC): availability during a partition, else consistency. He places VoltDB and H-Store at partition consistency (PC) with EC: consistency in both cases. Those are the author's classifications as of 2012, not vendor documentation, and products have changed since, so check current documentation before repeating one.

Kleppmann (2015) says such problems cast doubt on CAP as a tool for reasoning about practical systems, so treat a label as a starting point. For a Staff-level point, Brewer (2017) explains how Google's Spanner offers both availability and strong consistency over the wide area and why that is still consistent with CAP: the label records what a system does in a partition, not how often one happens.

For related design work, the distributed cache design shows replication choices in practice, and back-of-the-envelope estimation helps size the replicas.

How to answer it in an interview

The spoken structure: state the choice during a partition, say why partitions are unavoidable, give one example of each side, then mention latency.

Common mistakes

• "We pick CA, consistent and available." (wrong) A replicated system cannot opt out of partitions. (right) "Partitions will happen, so I choose how to behave while one lasts."
• "CAP means we permanently lose one property." (wrong) The trade-off bites only during a partition and can differ per operation. (right) "I decide per operation what to give up while partitioned."
• "CAP's consistency is ACID's consistency." (wrong) CAP's consistency is a strict subset of ACID's, single-copy consistency only. (right) "In CAP, consistency means linearizability, a single up-to-date copy."
• "Eventually consistent databases are always more available." (wrong) Kleppmann says this needs more careful reasoning. (right) "Eventual consistency can improve availability, but the claim depends on the system model."
• "CAP explains every database trade-off." (wrong) Abadi shows latency matters even without partitions. (right) "I also weigh consistency against latency when everything is healthy."

Follow-up questions

Is the C in CAP the same as the C in ACID?

No. CAP's consistency means all clients see one up-to-date copy of the data, as in linearizability. ACID's consistency is about a transaction leaving the database in a valid state.

Can a system be CA?

Only if it never partitions, which a network between separate machines cannot promise. A single-machine database avoids the question because it has no replicas to disagree. For multi-machine systems, think "consistent or available during a partition".

Is an eventually consistent system always more available?

Not automatically. Kleppmann (2015) grants there is some truth in the claim, but shows it needs more careful reasoning than CAP gives, and proposes judging designs by how operation latency depends on network delay.

What is PACELC and why does it matter?

PACELC extends CAP with the case where the network is healthy: even then, replicated data trades consistency against latency, because waiting for far-away replicas takes time. It explains choices that CAP alone cannot.

How do quorums relate to CAP?

Quorums tune where a system sits on the line: when read plus write acknowledgements exceed the replica count, the read set includes a replica with the latest write and the client keeps the highest version, though that alone is not linearizability. The minority side of a partition cannot reach a quorum, so it refuses. The database interview questions and backend interview questions pages cover related follow-ups.

Which side of CAP should a payment system choose?

Choose to refuse rather than guess for the ledger, and accept staler reads for views that do not move money. The concurrency interview questions cover the locking side of the same problem.

Sources

1. Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services — ACM SIGACT News (Gilbert and Lynch), DOI 10.1145/564585.564601, 1 Jun 2002
2. CAP Twelve Years Later: How the Rules Have Changed — IEEE Computer (Brewer), DOI 10.1109/MC.2012.37, 1 Feb 2012
3. A Critique of the CAP Theorem (arXiv 1509.05393) — arXiv (Kleppmann), 17 Sep 2015
4. Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story — IEEE Computer (Abadi), DOI 10.1109/MC.2012.33, 1 Feb 2012
5. Spanner, TrueTime and the CAP Theorem — Google Research (Brewer), 14 Feb 2017
6. Weighted Voting for Replicated Data — ACM SOSP (Gifford), DOI 10.1145/800215.806583, 1 Dec 1979