What is the CAP Theorem

System design interviews — CAP is table stakes vocabulary. Interviewers will ask why you chose DynamoDB over Spanner, or Cassandra over PostgreSQL. You need to explain what the database sacrifices, not just what it offers.

On-call debugging — When Cassandra returns stale reads after a network blip, or when a ZooKeeper-dependent service stops accepting writes during leader re-election, you're seeing the C vs A trade-off in production. Knowing which side your system sits on tells you immediately what class of failure you're looking at.

Real systems — DynamoDB and Cassandra bias toward AP (available under partition, eventually consistent). HBase, Spanner, and etcd bias toward CP (consistent, may reject requests under partition). PostgreSQL with synchronous replication is CP within a single region. The database readme won't always say this plainly; CAP gives you the vocabulary to read between the lines.

Where the theorem comes from

Eric Brewer conjectured CAP in 2000. Gilbert and Lynch proved it formally in 2002. The proof is elegant and worth understanding in first principles rather than memorised.

Formalising the three properties

Consistency (C) in CAP means linearisability: the system behaves as if there is one copy of the data, and every operation takes effect atomically at a single point in time. This is a specific, strong meaning — not the C in ACID, which is about application invariants.

Availability (A) means every request sent to a non-failed node eventually receives a response — not a timeout, not an error. The response does not have to be the latest value, but it must be some value.

Partition Tolerance (P) means the system continues to operate even if an arbitrary number of messages between nodes are dropped or delayed. A partition is a split in the network: some nodes can no longer talk to others.

Why you can't have all three

Imagine two nodes, N1 and N2, holding a replicated value. A client writes a new value to N1. Before N1 can propagate to N2, the network partitions — N1 and N2 can no longer communicate.

Now a second client reads from N2. You have two choices:

Return the stale value — the system is Available but not Consistent (the read doesn't reflect the write).
Refuse to respond (return an error or block indefinitely) — the system is Consistent (no stale read) but not Available.

There is no third option. The proof formalises this as a contradiction: if you require all three, you can derive a scenario where the system must both return a response and return the correct response, which is impossible when the correct response lives on an unreachable node.

The implication is not that you pick two out of three at design time like a menu. Because partitions will happen in any real network, P is not optional — you must tolerate partitions or accept total system failure. So the real choice is: during a partition, do you stay Available or stay Consistent?

CP systems

A CP system prioritises correctness. During a partition, a CP system will refuse writes (and often reads) rather than risk returning or accepting stale data. HBase, etcd, ZooKeeper, and Google Spanner sit here. Spanner achieves this across datacenters using TrueTime (GPS and atomic clocks) to bound clock uncertainty, making linearisable cross-region transactions practical — at latency cost.

Etcd uses the Raft consensus algorithm. A Raft cluster requires a quorum (majority of nodes) to commit a write. If a network partition isolates the leader from the majority, it steps down. No minority partition will accept new writes. This is CP by design.

AP systems

An AP system prioritises uptime. During a partition, it accepts reads and writes on both sides of the network split, accepting that the two sides will diverge. When the partition heals, the system resolves conflicts — usually via last-write-wins, vector clocks, or application-level merge logic. Cassandra and DynamoDB are canonical AP systems.

DynamoDB's eventual consistency mode allows reads from any replica. A read immediately after a write may not see that write. DynamoDB also offers a strongly-consistent read option — but that read may fail during a partition, sliding the dial back toward CP for that operation.

PACELC: the fuller picture

CAP only speaks to behaviour during a partition. Researchers pointed out that even when the network is healthy, latency and consistency trade off against each other. PACELC extends CAP: if Partition, choose A or C; Else (no partition), choose Latency or Consistency. This captures why Spanner has higher latency than DynamoDB even when both are fully connected — it's paying in milliseconds for synchronisation.

Tunable consistency

Many modern systems don't commit statically to AP or CP — they let you tune quorum parameters at query time. Cassandra's consistency levels range from ONE (fast, stale risk) to QUORUM (majority must agree) to ALL (every replica). Setting reads and writes both to QUORUM with a replication factor of 3 gives you consistency at the cost of availability: any two-node failure kills your quorum. This is the practical manifestation of CAP — you're sliding between poles, not picking a fixed point.

What CAP does not tell you

CAP doesn't say anything about performance, durability, or partial failures. A system can be CP and still lose data if it uses synchronous replication without durable storage. CAP also doesn't distinguish between network partition (split-brain) and node failure — these have different implications for real systems. And linearisability is only one consistency model; there are weaker models (causal consistency, read-your-writes) that fall between C and A on the spectrum, which CAP's binary framing obscures.

Brewer himself wrote in 2012 that the theorem's framing is sometimes misleading, particularly because "2 of 3" suggests you freely choose any pair, when in practice partition tolerance is non-negotiable and the real decisions are more nuanced than a binary flip.