CAP Theorem
What It Does
The CAP Theorem, proposed by Eric Brewer at PODC 2000 and formally proven by Gilbert and Lynch in 2002, states that a distributed data store cannot simultaneously guarantee all three of: Consistency (every read receives the most recent write), Availability (every request receives a response, though not necessarily the most recent write), and Partition Tolerance (the system continues operating despite network partitions dropping messages between nodes).
In a distributed system, network partitions are not optional — they happen due to hardware failure, network congestion, and datacenter isolation. This means partition tolerance is a mandatory requirement, reducing the effective choice to: during a partition, do you favor Consistency (reject requests that might return stale data) or Availability (serve requests even if data may be stale)?
This is the practical framing: CP systems (e.g., HBase, Zookeeper) sacrifice availability during partitions to maintain consistency. AP systems (e.g., Cassandra, CouchDB) sacrifice consistency to remain available. Most relational databases are CA in a single-node deployment but must make explicit choices at the application layer when distributed.
Key Features
- Formal mathematical proof: Gilbert and Lynch (2002) provide a formal proof; this is not empirical observation or folk wisdom.
- Practical reduction: In all real distributed systems, P is non-negotiable, making the design choice binary: C or A during partition events.
- PACELC extension: Daniel Abadi’s PACELC theorem extends CAP to cover normal (non-partition) operation by adding the Latency vs. Consistency trade-off, which is often more operationally relevant than the partition case.
- Not a permanent choice: Systems can implement tunable consistency (Cassandra’s consistency levels, DynamoDB’s eventual vs. strong reads) to make the C/A trade-off configurable per-query rather than per-system.
- Beyond databases: CAP applies to any distributed state store: caches, message queues, coordination services, distributed lock managers.
Use Cases
- Database selection: Choosing between CP databases (PostgreSQL in Patroni, CockroachDB, Zookeeper) for financial or inventory systems requiring strong consistency, vs. AP databases (Cassandra, DynamoDB default mode) for availability-sensitive workloads like user sessions or social feeds.
- Distributed cache design: Deciding whether a distributed cache (Redis Cluster, Hazelcast) must sacrifice availability on partition (CP) or tolerate potentially stale reads (AP).
- Microservices saga design: When decomposing transactions across services, understanding that you cannot have ACID semantics across service boundaries; sagas provide AP-style eventual consistency.
- Conflict resolution strategy: AP systems surface conflicts to the application layer (last-write-wins, vector clocks, CRDTs); choosing an AP database obligates the application to define a merge strategy.
Adoption Level Analysis
Small teams (<20 engineers): CAP is a useful conceptual framework but rarely the primary design constraint. Single-region deployments with managed databases (RDS, Supabase, PlanetScale) abstract most partition handling. Worth understanding to correctly use consistency settings on cloud databases.
Medium orgs (20–200 engineers): Directly relevant when evaluating database technology choices, designing multi-region deployments, or building distributed caches. Engineers should understand PACELC alongside CAP for complete trade-off reasoning.
Enterprise (200+ engineers): Critical design principle for platform and infrastructure teams. Multi-region active-active deployments, global databases (Spanner, CockroachDB, DynamoDB Global Tables) require explicit CAP trade-off decisions at the data model and API contract level.
Alternatives
| Alternative | Key Difference | Prefer when… |
|---|---|---|
| PACELC Theorem | Extends CAP to cover Latency vs. Consistency trade-off during normal (non-partition) operation | Designing systems where latency matters in steady state, not just during failures |
| ACID Properties | Focuses on transaction correctness within a single database instance | Single-node or tightly coupled database deployments where distribution is not the concern |
| BASE (Basically Available, Soft state, Eventually consistent) | Describes the operational reality of AP systems in terms of what they do guarantee | Communicating AP system behavior to stakeholders, not design-time decision making |
| CRDTs (Conflict-free Replicated Data Types) | Data structures that merge concurrently without conflicts, enabling AP semantics without conflict resolution code | AP system where the data domain allows mathematically conflict-free merge operations |
Evidence & Sources
- CAP Theorem — Wikipedia (includes Gilbert & Lynch 2002 proof reference)
- Beyond CAP: Unveiling the PACELC Theorem — DEV Community
- CAP, PACELC, ACID, BASE — ByteByteGo
- Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services — Gilbert & Lynch 2002 (ACM SIGACT)
Notes & Caveats
- CAP is a theorem about what is impossible, not a design recipe. It does not tell you what to build — only what you cannot have. Many engineers misread it as a three-way feature menu.
- The original CAP paper uses binary definitions of consistency (linearizability) and availability (every request returns). Real systems operate on spectrums: tunable consistency levels in Cassandra, read-your-writes consistency in DynamoDB. The binary theorem applies at the extremes.
- PACELC is now considered more practically useful for distributed database selection because most production systems spend almost no time in partition-recovery mode but spend 100% of their time making latency/consistency trade-offs in normal operation.
- “Choose CA” is misleading: in a distributed system, this means “we accept that during a network partition, our system will stop accepting writes to preserve consistency.” Most application operators find this unacceptable without realizing they’ve chosen CP, not CA.