Introduction to CAP Theorem

The CAP theorem falls out of one physical fact: when the network between replicas breaks, a node that receives a request has only two moves — answer from its own possibly-stale copy, or refuse to answer until it can confirm it is current. It cannot do both, because it has no way to reach the other side to reconcile. That single forced choice — return a maybe-wrong answer (stay Available) or withhold the answer (stay Consistent) — is the entire theorem. Everything else is vocabulary.

The three properties, precisely

• Consistency (C) — every read returns the result of the most recent completed write, from whichever replica it hits. This is linearizability: the cluster behaves as if there were a single copy of the data. Note this is not the C in ACID. ACID-C means a transaction never violates declared invariants (constraints, foreign keys). CAP-C is purely about replicas agreeing on the latest value.

• Availability (A) — every request to a non-failed node gets a non-error response in bounded time. It may be stale, but the node never hangs and never returns "try later."

• Partition Tolerance (P) — the system keeps operating when the network drops or delays messages between nodes, splitting the cluster into groups that cannot talk to each other.

What the theorem actually says (and the line to unlearn)

The popular phrasing — "a distributed system can only guarantee two of the three at any given time" — is misleading and worth discarding. In real deployments, network partitions are not optional: cables cut, switches reboot, GC pauses and long TCP timeouts all look like partitions. So P is not a property you choose — it is a hazard you must survive. That collapses the trilemma into a single conditional:

When a partition occurs, you must sacrifice either C or A. When there is no partition, you can have both.

So CAP is not a standing "pick 2 of 3" tax you pay all the time. It is a rule that only bites during a partition, and then it forces exactly one decision: C or A. A well-run system is fully consistent and fully available on a healthy network; CAP only describes its behavior in the failure window.

A traced example: two replicas, one broken link

Two replicas N1 and N2 both hold key x = 1. A client writes x = 2 to N1. At that instant the link between N1 and N2 fails, and a second client issues read x — but its request lands on N2, which never received the update. Follow the timeline:

At t=3, N2 is stuck. It knows it may be stale but cannot reach N1 to check. Its only two options are the two faces of CAP:

• CP choice — N2 refuses: returns an error or blocks until the partition heals. No client ever sees a stale x = 1, so consistency holds — but N2 gave up availability.

• AP choice — N2 answers x = 1. The client got a fast response, so availability holds — but it read a value that is already stale, so consistency is violated.

There is no third door. The write on N1 and the read on N2 cannot be reconciled while the link is down, so the node must trade one guarantee for the other.

Pitfalls

• Treating "pick 2 of 3" as a permanent budget. A CP system is not perpetually unavailable and an AP system is not perpetually inconsistent. Both are fine on a healthy network. The trade-off only manifests during the partition window — which is exactly when engineers who memorized the wrong slogan are surprised.

• Believing you can pick CA. "CA" only describes a single-node system or one that assumes partitions never happen. The moment you have more than one machine on a real network, P is mandatory, so a genuine "CA" distributed system does not exist. Vendors who claim it are quietly assuming partitions away.

• Confusing CAP-C with ACID-C. A database can be ACID-compliant (transactions preserve invariants) and still be an AP system that returns stale reads across replicas. Interviewers probe this exact gap.

• Ignoring the latency dimension. CAP is silent on the healthy case, but there you still pay for consistency: keeping replicas linearizable means every write waits for acknowledgment from other nodes. This is what PACELC adds — else (no partition), you trade Latency vs Consistency. CAP alone will fool you into thinking strong consistency is free when the network is up.

• Silent partitions from slow nodes. A GC pause or a saturated NIC is indistinguishable from a cut cable to the rest of the cluster. Systems partition far more often than "the datacenter link went down" suggests, so the C-or-A decision fires more than teams expect.

When to choose CP vs AP

Since P is forced, the real design decision is: during a partition, do I prefer a wrong-but-fast answer (AP) or no-answer-but-correct (CP)? Decide by the cost of serving stale data.

Choose CP (sacrifice availability during partitions) when a stale or conflicting answer is dangerous. Signals: money movement, inventory decrements, unique-username reservation, leader election, config that must be globally agreed. You would rather return an error than double-spend a balance. Cost: writes (and often reads) fail or block on the minority side of a partition, so your effective uptime drops exactly when the network is unhealthy. Examples: etcd, ZooKeeper, HBase, and Spanner's write path (all use a quorum/consensus protocol that refuses progress without a majority).

Choose AP (sacrifice consistency during partitions) when staleness is tolerable and downtime is not. Signals: shopping carts, social feeds, view counts, DNS, session stores, product catalogs. Showing a like-count that is a few seconds behind is harmless; showing a spinner loses the user. Cost: you must handle conflicting concurrent writes — via last-write-wins (can silently drop data), vector clocks, or CRDTs (extra machinery and reasoning). Examples: Cassandra, DynamoDB, Riak (tunable, but AP-leaning).

Named alternative — quorum tuning instead of a hard CP/AP label. Dynamo-style stores let you set R + W per operation. With N=3, choosing W=3,R=1 buys strong-ish consistency at the price of write availability (any one node down blocks writes); W=1,R=1 buys maximum availability but stale reads. So "CP vs AP" is often a dial per operation, not a database-wide identity: use strict quorums (W+R>N) for the few operations that need correctness, relax them for the many that need speed.

Crisp rule: choose CP when a wrong answer costs more than no answer; choose AP when no answer costs more than a slightly-wrong one; and reach for tunable quorums when different operations in the same system sit on opposite sides of that line.

Takeaways

• CAP is a conditional, not a permanent tax: it only forces a C-or-A choice during a partition; on a healthy network you get both.
• P is not optional on a real multi-node network, so "CA" distributed systems don't exist — the genuine decision is CP vs AP.
• The deciding question is the cost of stale data: prefer CP when a wrong answer is worse than an error, AP when an error is worse than staleness.
• CAP-C (replica agreement / linearizability) is unrelated to ACID-C (invariant preservation) — a system can have one without the other.

Sources: E. Brewer, "Towards Robust Distributed Systems" (PODC 2000 keynote) and "CAP Twelve Years Later: How the Rules Have Changed" (IEEE Computer, 2012); Gilbert & Lynch's formal proof, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services" (2002); Daniel Abadi's PACELC formulation (2012); DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store" (SOSP 2007). Re-authored and deepened for this guide.