The CAP Theorem

The CAP theorem, formalized by Eric Brewer in 2000 and proven by Seth Gilbert and Nancy Lynch in 2002, states that a distributed data system can provide at most two of the following three guarantees simultaneously: Consistency (every read receives the most recent write or an error), Availability (every request receives a non-error response, without guaranteeing it contains the most recent write), and Partition Tolerance (the system continues to operate despite arbitrary message loss or delay between nodes). Because real networks fail — cables get cut, switches misbehave, data centers lose connectivity — partition tolerance is not optional in a distributed system; it is a fact of life you must design around. The practical consequence is that CAP is really a choice between C and A only during an actual network partition, not a permanent architectural label you slap on a system.

A single-node database can trivially be both consistent and available because there is no network between replicas to partition. The moment you replicate data across two or more nodes to survive failures or reduce latency, you have created a distributed system, and distributed systems experience partitions — this is an empirical fact about networks, not a design choice. So the real question CAP forces you to answer is not 'do I want P?' but 'when a partition happens, do I sacrifice C or A?' Systems that pick CP (like a majority-quorum configuration of etcd or ZooKeeper) will refuse to serve reads or writes on the minority side of a partition rather than return stale or conflicting data. Systems that pick AP (like Cassandra or DynamoDB in their default configurations) will keep answering requests on both sides of the partition, accepting that some responses may be stale or that conflicting writes will need to be reconciled later.

Choosing CP means every acknowledged write is durable and every read reflects the latest acknowledged write, but during a partition some nodes must stop responding to preserve that guarantee — this is the right tradeoff for systems like leader-election services, distributed locks, or financial ledgers where a stale or wrong answer is worse than no answer. Choosing AP means the system remains responsive to every request even during a partition, accepting eventual consistency and the need for conflict resolution (last-write-wins, vector clocks, or CRDTs) — appropriate for systems like shopping carts, social media feeds, or presence indicators where availability and low latency matter more than perfect freshness. Most production systems are not purely CP or AP everywhere; they make the CP/AP choice per subsystem or even per operation, since a single application often has both strongly consistent needs (billing) and eventually-consistent-tolerant needs (view counts).

Daniel Abadi's PACELC extension notes that CAP only describes behavior during a Partition (P), where you choose Availability or Consistency (A or C); but Else (E), when the system is running normally, you still face a tradeoff between Latency (L) and Consistency (C). A system can be described more completely as PA/EL (favor availability during partitions, favor latency normally — e.g. Cassandra) or PC/EC (favor consistency during partitions and normally — e.g. many traditional relational replication setups). This framing is more actionable for engineers because network partitions are rare events, while the latency-consistency tradeoff is something every synchronous replication decision makes on every single request.