CAP Theorem and Quorums
What CAP really says: during a network partition you choose consistency or availability. A two-node simulation shows each choice, and quorum math (R + W > N) shows how stores tune it.
The CAP theorem says that when a network partition separates replicas, a distributed system must choose between consistency (reject some requests) and availability (answer from possibly stale data). The detail interviewers expect: partitions are not optional, so CA is not a real choice, and quorum stores get fresh reads when R + W > N.
CAP states that when a network partition separates replicas, a system must either reject some requests (keep consistency) or answer from possibly stale or diverging data (keep availability). With N=3 replicas, reads and writes that overlap (R + W > N) see the latest write; W=1, R=1 returned stale data 67% of the time in a simulation.
- The CAP theorem (Gilbert and Lynch, 2002, from a conjecture by Brewer) says a replicated store cannot guarantee both consistency and availability during a network partition.
- A CP system rejects writes it cannot confirm on a majority during a partition, while an AP system accepts them and lets replicas disagree until the partition heals.
- In a quorum store with N replicas, a write needs W acknowledgements and a read asks R replicas; if R + W > N, every read set overlaps every write set.
- In a simulation with N=3 and 10,000 operations, W=1 and R=1 returned stale data 67% of the time, while W=2 and R=2 returned stale data 0% of the time.
- Last-write-wins conflict resolution silently discards one of two concurrent writes; version vectors with application merge or CRDTs avoid losing updates.
- PACELC extends CAP: even without a partition, a distributed system trades latency against consistency.
01What the theorem says
CAP names three properties of a replicated data store. Consistency (C): every read sees the most recent write, as if there were one copy. Availability (A): every request to a working node gets a non-error response. Partition tolerance (P): the system continues to work when the network drops messages between nodes.
The theorem (Gilbert and Lynch, 2002, from a conjecture by Brewer) says you cannot have all three in the presence of a partition. Since real networks do partition, you do not get to opt out of P. The practical statement is: when a partition happens, choose between consistency and availability. When there is no partition, you can have both, and the interesting trade-off becomes latency versus consistency (the PACELC refinement).
02The two choices in a simulation
Take two replicas, A and B, both holding value x. The network between them is cut. A client sends a write of new to A.
A CP system refuses. A cannot confirm that B (or a majority) has the update, so it rejects the write. In the simulation the write returned rejected (cannot reach majority), and reads from A and B both still returned x. The data stays consistent, but the client got an error: availability was given up.
An AP system accepts. A stores the write and answers ok. Reading A then returned new while reading B returned x. The replicas now disagree. Every request got an answer, at the cost of consistency, until the partition heals and the data is reconciled.
03Conflicts after the partition heals
If clients on both sides of the partition wrote to the same item, say A holds red at version 1 and B holds blue at version 2, the system must merge them when connectivity returns. The simplest rule is last-write-wins (LWW) by timestamp or version. In the test, LWW kept blue and silently discarded red. A write that the client was told succeeded has vanished. Clock skew between machines can even make an older write win.
Better options: version vectors to detect that writes were concurrent, then keep both values and let the application merge (a shopping cart can union its items), or use conflict-free replicated data types (CRDTs) whose merge rule is built to be safe. Which one is right depends on whether losing an update is tolerable.
04Quorums: tuning with N, R and W
In a leaderless store such as Dynamo or Cassandra, each item is stored on N replicas. A write is acknowledged after W replicas confirm it, and a read asks R replicas and takes the newest version. If R + W > N, every read set overlaps every write set in at least one replica, so a read always includes at least one replica that acknowledged the latest completed write. This is necessary for fresh reads but not the whole story: sloppy quorums, concurrent writes and partially failed writes can still produce anomalies unless the store adds more machinery.
N = 3
for W, R in [(1, 1), (2, 2), (3, 1), (1, 3)]:
print(W, R, 'strong' if R + W > N else 'may be stale')Only W=1,R=1 is marked possibly stale. To see how stale, I simulated random replica choices for 10,000 operations. With W=1, R=1, the read missed the written replica 67% of the time (the chance that two random single picks out of three differ is 2/3). With W=2, R=2, the sets always overlapped and stale reads were 0%.
The common choice is N=3, W=2, R=2: tolerates one failed replica for both reads and writes, and gives overlap. W=3, R=1 makes writes fail if any replica is down but reads very fast. The trade-off is latency and availability on each side, which you set per operation.
05Strong, eventual and in-between
Linearizability is the strongest model: operations appear to take effect atomically at one point in time, and reads see the latest write. Sequential and causal consistency are weaker but cheaper: causal consistency, for example, ensures a reply is never seen before the post it answers. Eventual consistency promises only that if writes stop, replicas converge.
Many systems offer session guarantees on top, such as read-your-writes (you see your own updates) and monotonic reads (you never go backwards in time). These often give users what they feel as correctness without the cost of global agreement.
06Misreadings of CAP
Common mistakes. "Pick two of three": you cannot pick "CA" for a distributed system, because partitions are not optional. "MongoDB is CP, Cassandra is AP": these labels depend on configuration (read and write concerns, quorum settings) and on failure type, so they are rough summaries. "Availability" in CAP means every non-failed node answers, which is stricter than the usual uptime metric. And CAP says nothing about performance in normal operation: a CP system can still be fast, and an AP system can be consistent most of the time.
Use CAP as a prompt to ask what should happen during a partition for each kind of data: a bank transfer should refuse, a social media like counter can drift.
07Common interview questions
Q: State the CAP theorem.
A: In a distributed system with a network partition, you cannot guarantee both consistency and availability.
Q: Why not CA?
A: Partitions occur in real networks, so a distributed system must tolerate them. CA only describes a single-node system.
Q: CP versus AP?
A: CP rejects or blocks some requests during a partition to stay consistent. AP keeps answering and may return stale or conflicting data.
Q: What is the quorum condition for strong reads?
A: R + W > N, so read and write sets overlap.
Q: How are conflicts resolved after a partition?
A: Last-write-wins (loses data), version vectors with application merge, or CRDTs.
Q: What does PACELC add?
A: Even without a partition, there is a trade-off between latency and consistency.