The CAP theorem says that when a network partition splits a replicated system, the system cannot both stay available (every non-failed node answers every request) and stay linearizable (every read sees the latest completed write, as if there were one copy). Interviewers use it as a filter: candidates who recite "pick any two of three" have memorized a slogan, candidates who say "partitions are not optional, so the real question is what you sacrifice while one is happening" understand distributed systems. For a Backend / AI engineer it is the vocabulary behind choosing between a single-leader PostgreSQL, a quorum store like Cassandra or DynamoDB, and a consensus-backed store like etcd or Spanner.
C Consistency = LINEARIZABILITY. Once a write completes, every later read
(on any node) returns that write or something newer.
NOT the "C" of ACID (which means "constraints hold").
A Availability = every request to a NON-FAILED node gets a (non-error) response.
Not "99.99% uptime" - it is a per-request, all-nodes property.
P Partition = the network may drop or delay arbitrary messages between nodes.
tolerance Not a feature you switch on: if nodes talk over a network,
partitions can happen whether you planned for them or not.The proof idea is short. Put a value on two nodes, cut the link between them, and send a write to one and then a read to the other. The second node has exactly two options: answer with its old value (it stayed available but the read is stale, so it is not linearizable), or refuse / wait (it stayed consistent but is not available). There is no third option, because it cannot learn about the write across a link that is down. Nothing about this depends on the database brand; it is a property of any replicated state over an unreliable network.
Normal operation (no partition): During a partition:
Client --> A ==== B ==== C Client1 --> A ==== B X C <-- Client2
all links up: you can have (side 1) cut (side 2)
consistency AND availability
(cost shows up as LATENCY, The system must pick, per operation:
see PACELC below) CP: minority side refuses / errors
(consistent, less available)
AP: both sides keep answering
(available, may diverge, must
reconcile after healing)"CA" as a third category is mostly a mistake: a system that gives up partition tolerance is either a single node (no network between replicas, so nothing to partition) or a cluster that simply stops being correct or available when the network misbehaves, which is not a design you want to claim. So the honest framing is CP vs AP under partition, and it is often a per-operation or per-configuration decision, not a property of the product. For example, Cassandra with QUORUM reads and writes behaves CP-ish for a key when a majority is reachable and refuses otherwise, while ONE keeps answering on each side. PostgreSQL with a synchronous standby generally blocks commits if the standby becomes unreachable (favouring consistency), whereas asynchronous replication keeps accepting writes on the primary and can lose them on failover.
Three replicas A, B, C. Partition: {A,B} | {C}. Register value is "v0".
CP (majority quorum needed):
write "v1" at A -> A,B form a majority (2 of 3) -> accepted
write "v2" at C -> C alone is a minority -> REJECTED / times out
read at C -> cannot confirm freshness -> REJECTED / times out
after healing: C catches up from A,B. One history, no conflict.
AP (every side answers from local state):
write "v1" at A -> accepted on {A,B}
write "v2" at C -> accepted on {C} (two divergent histories!)
read at A -> v1, read at C -> v2 (not linearizable)
after healing: replicas must RECONCILE
- last-write-wins by timestamp: simple, but silently drops one write
- version vectors / siblings: keep both, ask app to merge
- CRDTs: data types designed so merges are automaticThe costs are asymmetric and that is the interview answer. CP pays with errors and timeouts for some users during the partition, but every accepted write is part of a single history you can reason about. AP pays with divergence: users on both sides are happy, but you now own a reconciliation problem, and any invariant that spans replicas (unique username, non-negative balance, stock count) can be violated in ways no merge function can undo. Choose by asking which is cheaper for this data: a refused request, or a wrong one.
PACELC: if Partition -> choose Availability or Consistency (this is CAP)
Else (normal) -> choose Latency or Consistency
Why the "else" branch exists: to keep replicas consistent you must wait for
them. Waiting costs round trips.
sync replication to a replica in another region:
commit latency ~= local work + 1 cross-region round trip (consistent, slower)
async replication:
commit latency ~= local work only (fast, replica can lag)
Typical labels people use (configuration-dependent, treat as tendencies):
Dynamo-style / Cassandra defaults : PA/EL (available under partition, low latency normally)
Spanner, etcd, ZooKeeper : PC/EC (consistency in both branches; you pay in latency)
single-leader RDBMS + async replica: reads from replica lean latency-first (EL)PACELC matters because partitions are rare while latency is every request. Most of the time your replicated database is not partitioned, and the decision that shapes user experience is whether a write waits for other replicas (or a read consults a quorum) before returning. This is why "eventual consistency" is usually sold as a latency optimization as much as an availability one. Note the labels above are simplifications: a product can move along both axes with settings such as Cassandra consistency levels, PostgreSQL synchronous_commit, or DynamoDB strongly-consistent reads.
# Python 3 (no dependencies): a toy 3-replica register with a {A,B} | {C} partition.
# Real output is shown below, produced by running this script.
# Three replicas of one register. A partition splits {A,B} from {C}.
# CP-style: a write/read needs a majority (2 of 3) reachable, else it is refused.
# AP-style: every side keeps answering from its local copy.
class Node:
def __init__(self, name):
self.name, self.value, self.ts = name, "v0", 0
nodes = {n: Node(n) for n in "ABC"}
partition = [{"A", "B"}, {"C"}] # network split
def reachable(frm):
return next(side for side in partition if frm in side)
def cp_write(frm, value, ts):
side = reachable(frm)
if len(side) < 2: # no majority -> refuse
return f"CP write at {frm}: REFUSED (only {len(side)}/3 nodes reachable)"
for n in side:
nodes[n].value, nodes[n].ts = value, ts
return f"CP write at {frm}: ok, applied on {sorted(side)}"
def cp_read(frm):
side = reachable(frm)
if len(side) < 2:
return f"CP read at {frm}: REFUSED (no majority)"
best = max((nodes[n] for n in side), key=lambda x: x.ts)
return f"CP read at {frm}: {best.value}"
def ap_write(frm, value, ts):
for n in reachable(frm): # only the local side sees it
nodes[n].value, nodes[n].ts = value, ts
return f"AP write at {frm}: ok, applied on {sorted(reachable(frm))}"
def ap_read(frm):
return f"AP read at {frm}: {nodes[frm].value}"
print("--- CP behaviour during partition ---")
print(cp_write("A", "v1", 1))
print(cp_write("C", "v2", 2))
print(cp_read("A"))
print(cp_read("C"))
print("--- AP behaviour during partition ---")
print(ap_write("A", "v1", 10))
print(ap_write("C", "v2", 11))
print(ap_read("A"))
print(ap_read("C"))
print("--- partition heals, last-write-wins merge ---")
newest = max(nodes.values(), key=lambda x: x.ts)
for n in nodes.values():
n.value, n.ts = newest.value, newest.ts
print({n.name: n.value for n in nodes.values()})
print("client that wrote v1 at A was told 'ok' but v1 is now silently gone")
# Output:
--- CP behaviour during partition ---
CP write at A: ok, applied on ['A', 'B']
CP write at C: REFUSED (only 1/3 nodes reachable)
CP read at A: v1
CP read at C: REFUSED (no majority)
--- AP behaviour during partition ---
AP write at A: ok, applied on ['A', 'B']
AP write at C: ok, applied on ['C']
AP read at A: v1
AP read at C: v2
--- partition heals, last-write-wins merge ---
{'A': 'v2', 'B': 'v2', 'C': 'v2'}
client that wrote v1 at A was told 'ok' but v1 is now silently gone
The last line of the output is the point of the demo: under the AP policy both clients received "ok", yet after last-write-wins healing one acknowledged write vanished. That is the price of never refusing a request, and it is why AP designs need either idempotent, commutative data types or an application-level merge.
Q: Explain the CAP theorem.
A: For a replicated data store, if the network partitions, you cannot have both linearizable reads/writes (C) and every non-failed node answering every request (A). Since partitions cannot be ruled out on a real network, the design decision is what to give up while partitioned: CP systems reject or delay requests on the side that cannot reach a quorum, AP systems answer everywhere and reconcile later. The trade-off is refused requests versus possibly stale or conflicting data, and the right side depends on the data (a bank balance vs a like counter).
Q: What happens during a network partition?
A: Nodes on different sides cannot exchange messages, and neither can distinguish "the other side is down" from "the link is down". A CP system keeps serving only the side that has a majority (or the leader) and makes the minority side error or block; when the network heals, the minority catches up from the majority. An AP system keeps accepting reads and writes on both sides, so histories diverge and, after healing, it must reconcile using last-write-wins, version vectors, or CRDTs, accepting that some writes may be lost or need application-level merging.
Follow-up: Is CAP's "C" the same as ACID's "C"?
A: No. ACID's consistency means a transaction moves the database from one valid state to another (constraints, foreign keys, invariants hold). CAP's consistency is linearizability: operations appear to take effect atomically at some point between invocation and response, in a single global order that respects real time. A single-node database can be ACID-consistent and the concept of CAP does not even apply; a distributed store can be linearizable per key and still have no multi-row constraints.
Follow-up: Can a system be "CA"?
A: Only in the degenerate sense. A single-node database has no replicas to disagree, so it has C and A until the node dies, but it is not distributed. A multi-node system that claims CA has just not defined what it does when the network splits, which in practice means it either blocks (losing A) or diverges (losing C). Saying "CA" in an interview usually signals a misunderstanding; saying "P is not optional, so CP or AP" is the accurate answer.
Follow-up: Why is CAP not enough to compare databases, and what is PACELC?
A: CAP only describes the rare partitioned case, while latency-versus-consistency trade-offs are present on every request. PACELC extends it: if Partition, choose A or C; Else, choose Latency or Consistency. Two systems that are both "AP" can differ sharply in normal-case behaviour (one waits for a quorum, the other acks after a single replica), and PACELC exposes that difference. It remains a simplified model, and many products can be tuned to different points.
Follow-up: Cassandra is called AP. Can you get consistent reads from it?
A: Generally yes, with tunable consistency: reading and writing at QUORUM gives overlapping majorities when R + W > N and no sloppy quorum is involved, so reads normally see the latest acknowledged write. But that is a per-request choice, it costs latency, it can fail when a majority is unreachable (behaving CP-like), and it is still not full linearizability in every corner case (concurrent writes, clock-based timestamps). So "Cassandra is AP" is a default tendency, not a universal label.
In a design interview, avoid announcing "we choose AP" for the whole system; walk the data instead. Money movement, inventory reservation, unique-handle registration and leader election want CP semantics: run them on a single-leader relational store or a consensus-backed store and accept that a partitioned minority returns errors, then design the client retry and the user-facing degraded state. Feeds, view counters, shopping-cart contents, presence and recommendation caches can be AP: accept writes in every region, resolve conflicts with merge rules or CRDTs, and let read replicas be slightly stale. Multi-region designs add the PACELC dimension: synchronous cross-region replication makes every write pay a WAN round trip, so many systems keep a single writer region for strongly consistent data and replicate asynchronously elsewhere, accepting a bounded data-loss window on regional failover. For AI backends, the same split shows up when a vector index or embedding cache replica lags the source-of-truth Postgres row: retrieval may briefly return stale chunks, which is usually acceptable, whereas billing and access-control checks should read from the authoritative store.
Choosing CP buys a single, explainable history and the ability to keep cross-record invariants, and costs availability on the minority side of a partition plus higher normal-case latency, since coordination requires round trips. Choosing AP buys uptime and low latency everywhere, and costs you divergence, reconciliation logic, and the loss of any invariant that needs a global view; last-write-wins in particular can silently discard acknowledged writes. Both are the wrong choice when applied blindly: CP for a social "like" count wastes user experience on a guarantee nobody needs, and AP for account balances or inventory turns a network blip into oversold stock or double spending. Also remember that the theorem is narrow (single-object linearizability, worst-case partition), so many real systems use weaker-but-useful models, such as causal or read-your-writes consistency, that CAP does not distinguish.