CAP Theorem
Imagine a bank runs two data centers, one in New York and one in Tokyo. Each holds a replica of every account balance. A network cable is cut, isolating the two data centers from each other. Customers in both cities keep swiping cards. Should the New York replica keep approving withdrawals? That risks a double-spend if Tokyo also approves one against the same account. Or should it refuse all transactions until the link is repaired? That risks angry customers and lost business. This is not a hypothetical corner case. Network partitions happen routinely in real infrastructure. They arise from switch failures, undersea cable cuts, or garbage-collection pauses. Such pauses can make a healthy node look dead. The CAP theorem gives a precise answer to what is and is not possible in this situation. CAP matters because it names a tradeoff that system designers make. They make it consciously or not, every time they build a replicated service. Databases like MongoDB, HBase, and traditional relational clusters lean toward consistency. They accept the cost of availability during partitions. Systems like Cassandra, DynamoDB, and Riak lean toward availability instead. They accept the cost of temporary inconsistency. Neither choice is a bug. Each is a defensible engineering decision once the tradeoff is understood. Without CAP as shared vocabulary, teams argue past each other. They debate "correctness" and "uptime" without realizing they are optimizing different, mutually exclusive objectives. The theorem is often stated sloppily as "pick two of three." This invites confusion because network partitions are not optional. They will happen in any real distributed system. So partition tolerance is not really a choice to forgo. The precise and useful reading is different. When a partition occurs, a system must choose between consistency and availability. This choice holds for the duration of that partition. This article makes that precision explicit. It walks through the formal model behind the theorem. It gives a constructive proof sketch. It also shows how the tradeoff plays out in real systems and real code paths. This article builds on Linearizability and Replication and Consistency Models to define exactly what "C" and "A" mean. It revisits the FLP Impossibility Result to place CAP within the broader landscape of distributed-computing impossibility results. It foreshadows how practitioners route around the tradeoff using Eventual Consistency and coordinated protocols like Distributed Transactions and Two-Phase Commit.
- CAP says a replicated system cannot simultaneously guarantee strong Consistency, total Availability, and tolerate network Partitions — during a partition you must sacrifice C or A.
- "Consistency" in CAP means linearizability: every operation appears to take effect atomically at some point between its invocation and response.
- "Availability" means every request to a non-failed node receives a (non-error) response, without waiting for the partition to heal.
- Partition tolerance is not optional in practice — real networks drop, delay, and reorder messages — so CAP is really a forced choice between CP and AP during partitions.
- The theorem only constrains behavior during a partition; outside partitions, systems can and do offer both C and A.
- CAP is a close cousin of the FLP Impossibility Result: both formalize the price of coordination under uncertain message delivery, and both motivate weaker consistency models used in practice.
When a network partition splits a replicated system, you must choose between answering every request (availability) and answering only with the latest confirmed value (consistency) — you cannot have both.
The idea
The CAP theorem, formalized by Seth Gilbert and Nancy Lynch in 2002 (conjectured earlier by Eric Brewer in 2000), concerns any distributed data store that replicates data across multiple nodes connected by an asynchronous network. It defines three properties precisely. Consistency here means linearizability: there exists a total order of all operations, consistent with real-time invocation and response order, such that every read returns the value written by the most recent write in that order. This is a strong guarantee — it is what a single, un-replicated server gives you for free, and the challenge is preserving it once data is copied to multiple machines. Availability means every request that arrives at a non-crashed node must eventually receive a response, and that response cannot be an error signaling "I don't know" — a node cannot simply refuse to answer because it is unsure of the current state. Partition tolerance means the system continues to operate even though the network may arbitrarily drop or delay messages between nodes, including losing every message between two groups of nodes for an unbounded period. The precise theorem statement is: no algorithm running on an asynchronous network can simultaneously guarantee linearizable consistency and total availability in the presence of network partitions. The proof is by contradiction and is short enough to reconstruct from first principles, which is done below. The crucial subtlety, frequently lost in the popular "pick two of three" slogan, is that partition tolerance is not a knob you can turn off. In any network spanning more than one physical link, a partition can happen — a cable can be cut, a switch can fail, a firewall rule can misfire. A system that "chooses" to not tolerate partitions is really choosing to become completely unavailable (or incorrect) the moment one occurs, which is itself a CP or an unsafe outcome, not a third option. So the honest framing is: given that partitions will occur, decide in advance whether the system will remain CP (consistent but possibly unavailable) or AP (available but possibly inconsistent) during those partitions. It helps to separate CAP from two adjacent ideas it is often confused with. First, CAP is a worst-case, adversarial-network result — it says nothing about what happens on an ordinary day when the network is healthy; on such days a well-designed system can and should offer both strong consistency and high availability, and most of engineering effort goes into making partitions rare and short rather than into abandoning one side of CAP permanently. Second, CAP is a close relative of the FLP Impossibility Result, which shows that no deterministic consensus protocol can guarantee both safety and termination (liveness) in an asynchronous network if even one process may crash — CAP can be viewed as a data-replication-flavored corollary of the same underlying fact: asynchronous networks make it impossible to distinguish "the other side is slow" from "the other side is unreachable," and any protocol that must decide before that ambiguity resolves must occasionally sacrifice either correctness or termination.
How it works
The cleanest way to internalize CAP is to walk through the proof itself, because the proof is the mechanism — it exhibits exactly the algorithmic dilemma a designer faces and shows why no clever protocol can escape it.
Setup. Consider a data store with two nodes, `G1` and `G2`, each holding a replica of a single register initialized to value `v0`. A client `C1` can send a write to `G1`; a client `C2` can send a read to `G2`. The network between `G1` and `G2` can be partitioned, meaning every message sent from one to the other is lost (or arbitrarily delayed beyond any timeout the algorithm might use).
Proof by contradiction. ``` ASSUME: an algorithm A exists that is both linearizable (C) and total-available (A), even during a partition. STEP 1 (create a partition): Cut all communication between G1 and G2. (Allowed, because A claims to tolerate partitions.) STEP 2 (perform a write on one side): C1 sends WRITE(v1) to G1. Because A is available, G1 must respond -- it cannot block waiting for G2, since messages to G2 never arrive. G1 responds "write acknowledged." STEP 3 (perform a read on the other side): C2 sends READ() to G2. Because A is available, G2 must respond -- it cannot block waiting to hear from G1. G2 has received no message from G1 (partition active), so the only value G2 can possibly return is v0. STEP 4 (derive contradiction): The real-time order of operations is: WRITE(v1) completes at G1 -- before -- READ() begins at G2 Linearizability requires READ() to return v1 (the most recently completed write). But G2 returned v0. CONTRADICTION: A is not linearizable after all. CONCLUDE: no algorithm can be simultaneously linearizable (C) and total-available (A) while tolerating partitions (P). ``` This argument generalizes beyond two nodes and a single register: the same construction works for any system with at least two nodes that can be separated by a partition, because the adversary only needs to isolate some client from some up-to-date replica. The proof is constructive in the sense that it doesn't just assert impossibility abstractly — it hands you the exact failing execution trace, which is exactly the scenario every CP/AP design decision in real systems is built to handle explicitly.
The design fork. Given this impossibility, a system designer facing an active partition has exactly two disciplined choices, formalized below as two idealized strategies a coordinator can run. ``` function HANDLE_REQUEST_CP(request, localReplicaState, partitionDetected): if partitionDetected and cannotConfirmLatestValue(localReplicaState): return ERROR("unavailable: cannot guarantee consistency") else: result = applyLinearizably(request, localReplicaState) return result function HANDLE_REQUEST_AP(request, localReplicaState, partitionDetected): // Always answer, even if this replica might be stale. result = applyLocally(request, localReplicaState) recordForLaterReconciliation(request) // e.g. vector clock, CRDT merge return result ``` `HANDLE_REQUEST_CP` is what a CP system (e.g., a ZooKeeper ensemble, or an HBase region server cut off from its master) does: on detecting it cannot safely confirm it holds the latest state, it declines to answer rather than risk returning stale or conflicting data. `HANDLE_REQUEST_AP` is what an AP system (e.g., a Cassandra node with consistency level `ONE`, or a DynamoDB replica) does: it always answers using local state and defers reconciliation of any conflicting writes to a later merge step, typically using version vectors, last-writer-wins timestamps, or conflict-free replicated data types.
Complexity & correctness
CAP is not an algorithm to analyze for running time; it is an impossibility result, so "complexity" here means understanding the cost structure of each side of the tradeoff, and "correctness" means understanding why the proof above is airtight and where its assumptions bind.
Why the proof is airtight. The argument uses only three ingredients: (1) the definition of linearizability, which fixes what a correct read must return given the real-time ordering of a completed write; (2) the definition of total availability, which forbids a node from blocking or erroring out on a request; and (3) the adversary's power to withhold every message across a cut for an arbitrary duration, which is exactly what "the network partitions" means. Given these three, the derivation is a direct logical chain with no gap: availability forces both `G1` and `G2` to answer without communicating, and the two answers they are forced to give are demonstrably inconsistent with linearizability's requirement. No cleverer protocol — no amount of retries, timeouts, quorum tricks, or vector clocks — can close this gap, because the adversary is defined to be able to delay messages past any finite timeout the protocol might use. This is why CAP is a theorem, not a rule of thumb: it holds for every algorithm, not just the ones we've thought to try.
Relationship to FLP. The FLP Impossibility Result shows that deterministic consensus is impossible to guarantee in bounded time on an asynchronous network with even one crash failure, because a protocol cannot distinguish a crashed process from an extremely slow one. CAP's proof leans on the same indistinguishability: `G2` cannot tell whether `G1` is unreachable because of a partition or because it crashed, or simply because its message is delayed. Both theorems are proved by adversarial scheduling arguments over asynchronous message delivery, and both conclude that some desirable property (termination in FLP's case, joint C+A in CAP's case) must be sacrificed. A useful mental model: FLP is about agreeing on one value across many processes; CAP is about serving reads and writes on replicated copies of a value. CAP can be seen as inheriting FLP's impossibility once you notice that maintaining linearizable replicas requires something equivalent to solving consensus on the order of operations.
Cost tradeoffs in practice.
- A CP system pays an availability cost: during a partition, the minority side (or, in a leaderless design, any side that cannot reach a majority quorum) must reject requests, producing visible downtime or errors proportional to the partition's duration.
- An AP system pays a consistency cost: during a partition, both sides keep answering, so conflicting writes can occur, and after the partition heals the system must run a reconciliation step (e.g., merging via a CRDT, applying last-writer-wins, or surfacing conflicts to the application) whose cost and correctness depend entirely on the merge semantics chosen — some merges are lossless and commutative (CRDTs), others silently drop updates (naive last-writer-wins).
- Both families pay a "no free lunch" latency cost even absent partitions: strict linearizability generally requires waiting for acknowledgment from a quorum or leader, which costs a network round trip; this cost exists independent of CAP but compounds with it, and is the subject of the related PACELC refinement (if Partitioned, choose A or C; Else, even with no partition, choose Latency or Consistency).
Honesty about scope. CAP concerns exactly the moment of an active partition; it says nothing about steady-state behavior, and it says nothing about how bad the inconsistency or unavailability must be — those quantitative questions are answered by specific protocols and consistency models (e.g., quorum systems, Eventual Consistency, session guarantees), which trade off staleness bounds and availability windows in ways CAP itself does not specify.
Worked example
Trace a concrete key-value store, `orders["order-42"]`, replicated on three nodes `N1, N2, N3` in a cluster split by a partition into `{N1, N2}` and `{N3}`.
| Time | Event | CP system (e.g., quorum-based, requires majority) | AP system (e.g., Cassandra-style, `ONE` consistency) | |
|---|---|---|---|---|
| t0 | State: `order-42 = "pending"` on all 3 nodes | consistent | consistent | |
| t1 | Partition occurs: `{N1,N2}` \ | `{N3}` | detected by both sides via missed heartbeats | detected, but no action taken |
| t2 | Client X writes `order-42 = "shipped"` to N1 | N1,N2 form majority (2 of 3) → write succeeds, acknowledged | N1 accepts locally, acknowledged immediately | |
| t3 | Client Y reads `order-42` from N3 | N3 alone cannot form a majority → returns `UNAVAILABLE` error | N3 has no update → returns stale `"pending"` | |
| t4 | Client Z writes `order-42 = "cancelled"` to N3 | N3 alone cannot form a majority → write rejected | N3 accepts locally, acknowledged immediately | |
| t5 | Partition heals | no conflict existed — only one write was ever accepted | conflict: `N1/N2` say `"shipped"`, `N3` says `"cancelled"` | |
| t6 | Reconciliation | none needed | must resolve conflict — e.g., last-writer-wins by timestamp, or escalate to a human/business rule |
The table makes the tradeoff concrete: the CP system never lies, but client Z's write is simply lost/rejected during the partition, and client Y receives an outright error instead of an order status. The AP system never refuses a request, but it manufactures a genuine conflicting-writes problem — two clients believe they "won" — that must be resolved after the fact, and the resolution policy (last-writer-wins here) may silently discard the cancellation, which is a business decision disguised as a technical merge rule. Neither behavior is a bug; each is the direct, provable consequence of the choice made at design time, exactly as the proof in the previous section predicts.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| "Pick two of three" taken literally, treating P as optional | Popular slogan drops the nuance that real networks always risk partitioning | Understand CAP as a forced CP-vs-AP choice during partitions, not a permanent three-way menu |
| Assuming CAP constrains behavior at all times | Confusing a worst-case impossibility result with an always-on rule | Recognize CAP only bites during an active partition; design for both C and A in the common case |
| Treating "C" in CAP as ACID consistency | Overloaded term; ACID's "C" means constraint-preserving, CAP's "C" means linearizability | Always clarify: CAP-C = linearizability of reads/writes, not schema/referential integrity |
| Believing a single-node database "solves" CAP | No replication means no partition can occur between replicas | Recognize CAP only applies to replicated systems; a single node trivially offers both C and A until it crashes |
| Ignoring latency tradeoffs outside partitions | CAP says nothing about the common, partition-free case, so teams stop analyzing there | Consult the PACELC extension: even without partitions, systems trade latency against consistency |
| Assuming AP systems are "eventually" perfectly consistent with no work | Conflict resolution is not automatic magic | Explicitly choose and test a merge strategy (CRDT, vector clocks, LWW) and understand its failure modes |
Pioneers & history
Origins · 1 minEric A. Brewer and how this was discovered
Brewer's original conjecture was informal, presented as a practical observation from operating internet-scale systems: as scale grows, network partitions become inevitable, and designers must choose how their systems degrade. He later clarified (2012) that the "2 of 3" framing oversimplifies the theorem and that in practice systems make finer-grained, per-operation tradeoffs rather than a single global choice.
Nancy Lynch, co-author of the formal proof, is also a foundational figure behind the FLP Impossibility Result (with Michael Fischer and Michael Paterson, 1985), making her work the connective thread between the two most-cited impossibility results in distributed computing — both born from the same insight that asynchrony plus failures erases the ability to reliably distinguish "slow" from "dead."
Where this matters
CAP shapes the default consistency model of nearly every widely used distributed database and coordination service. CP-leaning systems include ZooKeeper and etcd, which deliberately sacrifice availability during a loss of quorum because they exist specifically to hand out locks, leader-election results, and configuration that must never be wrong — a stale lock is far more dangerous than a temporarily unavailable one. Traditional replicated relational databases configured with synchronous replication (e.g., PostgreSQL with synchronous standby, Google Spanner's TrueTime-based commits) similarly favor consistency, accepting increased commit latency and occasional unavailability to guarantee linearizable or externally-consistent transactions. AP-leaning systems include Cassandra, Amazon DynamoDB, and Riak, built for services (shopping carts, social media feeds, sensor telemetry) where an approximate or slightly stale answer is far better than an error page, and where conflict resolution via version vectors or CRDTs is an acceptable cost for always-on availability. Content delivery networks and DNS are implicitly AP: a CDN edge node serving a cached, possibly stale asset during an origin outage is choosing availability over freshness, exactly the CAP tradeoff applied to caching. Multi-region cloud architectures — the New York/Tokyo bank example from the opening — must make an explicit CAP decision per data type: account balances typically demand CP guarantees (better to freeze transactions than double-spend), while user preferences or "last seen" timestamps typically tolerate AP looseness. Understanding CAP is also foundational before studying how systems try to get the best of both worlds in the common case: Eventual Consistency models describe how AP systems converge after partitions heal, and Distributed Transactions and Two-Phase Commit describes a CP-flavored protocol for atomic multi-node commits that explicitly blocks (sacrifices availability) when a coordinator or participant becomes unreachable.
Ask the tutor: How would you redesign the CP bank example to minimize downtime during a partition without giving up consistency guarantees?
Does CAP mean I must permanently sacrifice either consistency or availability in my whole system?
No. CAP constrains behavior only during an active network partition, not at all times. In the common case, when the network is healthy, a well-engineered system can offer both strong consistency and high availability simultaneously — most systems spend the vast majority of their uptime in this happy path. What CAP forces you to decide in advance is what happens for the (hopefully rare, hopefully short) windows when a partition does occur: will affected nodes refuse requests to stay correct (CP), or will they keep answering and risk temporary inconsistency (AP)? Many real systems even make this choice per operation type rather than globally, treating financial balances as CP and non-critical metadata as AP within the same application.
Is CAP the same theorem as FLP impossibility?
No, though they are close relatives proved with similar adversarial techniques. FLP Impossibility Result concerns consensus: it shows no deterministic algorithm can guarantee agreement in bounded time on an asynchronous network if even one process might crash, because a correct process cannot distinguish a crashed peer from a very slow one. CAP concerns data replication: it shows no algorithm can guarantee linearizable reads/writes and total availability once a partition can isolate replicas from each other. Both rely on the same core fact — asynchronous networks make "slow" and "unreachable" indistinguishable — but FLP is about reaching agreement on a value, while CAP is about serving read/write requests against replicated state.
What does "availability" in CAP actually require, precisely?
Total availability, in the formal CAP sense, requires that every request received by a non-crashed node eventually produces a non-error response — the node is never allowed to simply say "I don't know" or block indefinitely. This is a strict definition: a system that occasionally times out or returns an explicit error during a partition is, by this definition, not fully available during that window, even if it is available 99.99% of the time overall. Real-world "availability" as measured in SLAs (e.g., "five nines") is a looser, probabilistic notion computed over time, which is why a system can be "highly available" in commercial terms while still being formally a CP system that sacrifices availability during rare partitions.
If I use a majority quorum (like Raft or Paxos), do I get both C and A?
Quorum-based systems (Raft, Paxos, and systems built on them like etcd and CockroachDB) achieve linearizable consistency and are available as long as a majority of nodes can communicate. This is a clever middle path, but it does not evade CAP: during a partition that leaves no side with a majority — for example, a network split into three roughly equal groups — no side can safely commit new writes, so the system becomes unavailable for writes on every side until a majority re-forms. Quorums narrow the conditions under which availability is sacrificed (only true minority partitions are affected) but they do not eliminate the CAP tradeoff itself.
How does PACELC extend or refine CAP?
PACELC, proposed by Daniel Abadi in 2012, observes that CAP only describes behavior during partitions and is silent about the much more common partition-free case. PACELC states: if Partitioned, a system must choose Availability or Consistency (the CAP tradeoff); Else (no partition), it must still choose between Latency and Consistency, because achieving strong consistency generally requires extra coordination round trips even when the network is perfectly healthy. This framing explains why even non-partitioned systems like Spanner or synchronously replicated PostgreSQL show higher write latency than their eventually-consistent counterparts — that cost is unrelated to partitions and is paid every single day.
Can a system be CP for some operations and AP for others?
Yes, and many production systems are designed this way deliberately. A single application can route strongly consistent operations (e.g., processing a payment, decrementing inventory) through a CP path — a quorum-backed store or a distributed transaction — while routing tolerant operations (e.g., updating a "last active" timestamp, incrementing a view counter, storing a shopping-cart item) through an AP path with eventual reconciliation. This hybrid approach is common in large e-commerce and social platforms and reflects the mature, post-2012 understanding of CAP: the tradeoff is best applied per data type or per operation, not as one irreversible, system-wide architectural decision.
Does using more replicas make the CAP tradeoff go away?
No — more replicas change the shape of the tradeoff but not its existence. With more nodes, a well-designed quorum system can tolerate the loss of some nodes without sacrificing availability, because a majority can still form even if a minority is partitioned away. But the theorem still applies to whichever side of any possible partition lacks a majority (or lacks contact with the required replicas): that side must still choose to reject requests (CP) or serve possibly-stale data (AP). Adding replicas improves fault tolerance and can reduce how often the tradeoff bites, but the underlying impossibility proved by Gilbert and Lynch holds for any number of nodes greater than one.