CAP Theorem (Correct Framing)

The most misquoted result in system design

The folklore version of CAP, "pick 2 of Consistency, Availability, Partition-tolerance," is wrong in a way that will sink an interview. The correct statement, from Gilbert and Lynch's proof of Brewer's conjecture, is much narrower: when a network partition occurs, a system must choose between consistency and availability. That is it. CAP says nothing about normal operation, and it is not a permanent three-way menu.

What the letters actually mean

• C (Consistency) in CAP is linearizability: there is a single, up-to-date copy of the data, and every read sees the most recent completed write in real-time order. Far stronger than "the database doesn't corrupt data." It means no stale reads, ever.
• A (Availability) means every request to a non-failing node gets a non-error response, eventually. A node that returns "try again later" or refuses the write is not available in the CAP sense, even though the process is up.
• P (Partition tolerance) means the system keeps operating when the network drops or delays messages between nodes.

Here is why "pick 2" is nonsense: P is not optional. Networks partition. Cables get cut, switches reboot, a cross-region link saturates. You do not get to choose a world without partitions, so you cannot "give up P" to keep C and A. That means CA is not a real operating point for any system that spans more than one machine. A single-node database is trivially "CA" only because it has no network to partition, and calling it CA is the tell that someone learned CAP from a slide, not the proof.

The real decision, during a partition

Two nodes that cannot talk each get a write. They cannot both accept it and stay consistent, because their copies would diverge. So:

• A CP system sacrifices availability during the partition: the minority side (or both sides) refuses writes it cannot safely coordinate, returning errors, to guarantee it never serves or accepts inconsistent data. Examples: ZooKeeper, etcd, HBase, a leader-based store where the minority steps down.
• An AP system sacrifices consistency: both sides accept the write and reconcile later (last-writer-wins, CRDTs, or surfacing siblings). Examples: DynamoDB, Cassandra, Riak in their default modes.

Interview nuance: the strongest candidates immediately add that real systems are not globally CP or AP. Consistency is usually tunable per operation or per key. Cassandra lets you pick consistency level ONE (AP-ish) or QUORUM/ALL (CP-ish) on each query. DynamoDB offers eventually consistent reads (cheap) or strongly consistent reads (a leader round trip). So "is X CP or AP?" is often the wrong question; the right one is "what does X do to this operation during a partition?"

             partition!
   client -> [ node1 ] --X-- [ node2 ] <- client
                 |                 |
   CP: node2 (minority) refuses -> availability lost, C kept
   AP: both accept, reconcile later -> A kept, C lost
   CA: not an option; P is a fact of nature

Recap: CAP is a forced choice only during a partition between linearizable consistency and availability, P is non-negotiable so CA is not a real operating point, C means linearizability and A means every non-failing node answers, and most production systems are tunable per operation rather than globally CP or AP.