The CAP Theorem

Imagine a globally replicated banking database. Copies of your account balance sit in New York and Singapore. A backhoe severs the transatlantic cable connecting them mid-transaction. Should the New York replica keep answering withdrawal requests? Or should it refuse them until it confirms with Singapore that no double-spend is happening? This single question — what to do when the network breaks — is the entire subject of the CAP theorem. Every distributed database on the market has picked an answer. CAP formalizes an intuition that distributed systems engineers had reached painfully. They learned it through outages, long before it was written down. You cannot simultaneously guarantee that every read sees the latest write, that every request gets a response, and that the system tolerates network partitions. Real systems must partition-tolerate (networks fail — this is not optional). So the theorem reduces in practice to a choice between consistency and availability during a partition. That choice shapes the design of every large-scale storage system. Amazon's Dynamo chose availability. Google's Spanner leans toward consistency. Most NoSQL systems expose the tradeoff as a knob. The theorem's power is not in a clever proof — the proof is short. Its power lies in the discipline it imposes on system design. Before CAP was articulated, vendors could claim their system was simultaneously strongly consistent, always available, and partition-tolerant. It was hard to argue otherwise without a crisp counterexample. After CAP, such claims could be checked against a rigorous impossibility result. This works the way perpetual-motion claims are checked against thermodynamics. This article states CAP precisely, and proves it with a minimal counterexample. It then extends CAP with the more operationally useful PACELC framework. PACELC addresses the latency-consistency tradeoff that persists even when there is no partition at all. Together these ideas set up Eventual Consistency and Consistency Models and the design space surveyed in NoSQL Data Models Overview.

Key takeaways

CAP: a distributed data store cannot simultaneously guarantee Consistency, Availability, and Partition tolerance.
Because networks will partition, the real choice is C vs. A during a partition — not whether P is desired.
The proof is a two-node, two-client counterexample: any protocol either blocks (loses A) or answers stale data (loses C).
PACELC generalizes CAP: even with no partition, systems trade latency (L) against consistency (C).
"Consistency" in CAP means linearizability, a strong per-object guarantee — not the C in ACID.
Systems like DynamoDB, Cassandra, and Cosmos DB let you tune the tradeoff per-operation rather than pick one globally.

The core insight

When the network partitions, a distributed system must choose between returning a possibly stale answer or returning no answer at all — it cannot always do both.

The idea

The CAP theorem, formalized by Eric Brewer in a 2000 keynote and proven by Seth Gilbert and Nancy Lynch in 2002, concerns three properties of a distributed data store that replicates data across multiple network-connected nodes.

Consistency (C), in the CAP sense, means linearizability: every read returns the value of the most recent completed write, as if all operations executed atomically on a single copy of the data, in some order consistent with real time. This is a strong guarantee — stronger than the "C" in ACID (which refers to constraint preservation), and it should not be confused with eventual consistency, which explicitly permits reads of stale data.

Availability (A) means every request received by a non-failing node must eventually generate a response — the system cannot simply refuse to answer. Formally, availability requires that every request terminates, and it terminates with a meaningful (non-error) result.

Partition tolerance (P) means the system continues to operate despite an arbitrary number of messages being dropped or delayed between nodes by the network. A partition splits the nodes into groups that cannot communicate with each other, even though each individual node is alive and functioning correctly. The theorem states: no distributed algorithm can guarantee C, A, and P simultaneously; at most two of the three can be achieved at once. Since network partitions are a physical reality — cables get cut, switches fail, packets get dropped by congestion — a system deployed across more than one node must be prepared for P to occur. This means the real design decision is not "which two of three do I want," but "when a partition happens, do I sacrifice C or A?" Systems that keep answering with possibly-stale data during a partition are called AP systems; systems that refuse to answer (or block) rather than risk inconsistency are called CP systems. A theoretical "CA" system — consistent and available, but not partition tolerant — only makes sense as a single-node system, or as a description of behavior during the (hopefully long) periods when no partition is occurring.

How it works

The impossibility argument

The cleanest way to understand why CAP holds is to walk through Gilbert and Lynch's minimal counterexample, which uses just two nodes. Consider two nodes, $N_1$ and $N_2$ , each storing a replica of a single data object with initial value $v_0$ . They are connected by a network link. Two clients, $C_1$ and $C_2$ , can each talk only to one node: $C_1$ talks to $N_1$ , $C_2$ talks to $N_2$ . ``` setup: N1, N2 hold replicated copies of object X, value = v0 network link between N1 and N2 may be cut ("partitioned") scenario: 1. Partition the network: cut the link between N1 and N2. 2. C1 sends write(X = v1) to N1. N1 must respond (Availability requires this). N1 cannot forward the write to N2 (link is cut). 3. C2 sends read(X) to N2. N2 must respond (Availability requires this). N2 has not received the update from N1 (link is cut). claim: N2 must return either v0 (stale) or block forever.

if N2 returns v0 -> violates Consistency (C1's write was not seen)
if N2 blocks/refuses -> violates Availability

therefore: C and A cannot both hold while the partition persists. ``` The argument generalizes beyond this toy case: as long as the partition prevents any communication between the sets of nodes serving $C_1$ and $C_2$ , no algorithm can let $N_2$ learn about $C_1$ 's write without violating either A (by not responding) or C (by responding with stale data). This is not a limitation of a particular protocol — quorum systems, consensus protocols, vector clocks, all face the identical wall, because the constraint is about information flow across a severed link, not about implementation cleverness.

The design space this creates

Once a partition is detected, a system administrator (or, more precisely, the system's designers, ahead of time) must choose a policy: ``` on detecting a partition (this node cannot reach a quorum / its peers): policy CP ("consistency first"): reject writes (and often reads) that cannot be certified against the rest of the replica set -> some client requests receive an error or timeout -> data never diverges policy AP ("availability first"): accept the read or write locally regardless of partition state -> every request gets an answer -> replicas may diverge; reconciliation (e.g. via vector clocks, CRDTs, or last-writer-wins) happens once the partition heals ``` Real systems often apply this choice per operation or per key rather than system-wide: Amazon DynamoDB and Cassandra default to tunable, per-request consistency levels (`ONE`, `QUORUM`, `ALL`), letting an application choose AP-like or CP-like behavior for each call. Systems built on Paxos or Raft consensus — Google Spanner, ZooKeeper, etcd — are structured as CP by default: a partitioned minority cannot commit writes because it cannot reach a majority quorum.

PACELC: the tradeoff that survives even without a partition

CAP only describes behavior during a partition, which is (ideally) rare. Daniel Abadi observed in 2010 that a second, more persistent tradeoff exists even when the network is perfectly healthy: the tradeoff between latency and consistency. He proposed PACELC to unify both: > If Partitioned, choose between Availability and Consistency; > Else (normal operation), choose between Latency and Consistency. The "Else" branch matters because achieving strong consistency during normal operation is not free — it requires coordination (e.g., synchronous replication to a quorum, or a round of consensus) before a write or read can be acknowledged, and coordination costs latency. A system can:

be PC/EC: consistent during a partition (at the cost of availability) and consistent during normal operation (at the cost of latency) — e.g., Spanner, VoltDB.
be PA/EL: available during a partition and low-latency during normal operation, sacrificing consistency in both cases — e.g., Cassandra and DynamoDB in their default configurations.
mix regimes, such as PA/EC: available under partition, but consistent (higher latency) when healthy.

PACELC is strictly more informative than CAP for comparing real systems, because most production incidents are not about total network partitions — they are about the everyday latency cost of keeping replicas synchronized.

Figure

The CAP triangle and the PACELC extension

Complexity & correctness

CAP is not an algorithm with a running-time complexity in the usual sense — it is an impossibility theorem, so its "correctness" claim is a proof that no algorithm, of any complexity, can achieve all three properties under partition. It is worth being precise about what is and is not proven.

Formal statement. Gilbert and Lynch model the system as an asynchronous network: nodes communicate only by sending messages, and a partition is modeled as an adversary that can drop or arbitrarily delay any message between two subsets of nodes, for an unbounded amount of time. Under this model: > No algorithm can guarantee both linearizable consistency and total availability in the presence of network partitions, if the network can be partitioned for an unbounded duration.

Proof sketch (the two-node argument above, generalized). Suppose, for contradiction, an algorithm $\mathcal{A}$ achieves C, A, and P. Partition the network into two nonempty groups $G_1, G_2$ with no communication possible between them for time $T$ . Let a client issue write $w$ (X = v1) to a node in $G_1$ at time $t_0$ ; by availability, this node must respond, so it must complete the write locally without waiting on $G_2$ (since it cannot reach $G_2$ during the partition). At time $t_0 + T$ (still during the partition), a client issues read(X) to a node in $G_2$ . By availability, this node must respond — it cannot block waiting for the partition to heal. But it has received no message from $G_1$ , so it has no way to know that $v_1$ was written; whatever it answers is either $v_0$ (stale — violating linearizability, since a linearizable read must reflect the completed write $w$ ) or some other guess (equally unjustified). Either way, C is violated. Since $T$ was arbitrary (the network can be partitioned as long as needed, by assumption of P), this holds regardless of timeout strategy, retry count, or protocol design. $\blacksquare$ The key move in the proof is the unbounded duration of the partition combined with the hard requirement that availability means every request eventually terminates with an answer. This is why the common escape hatch — "just wait until the partition heals, then answer" — is disallowed: waiting an unbounded time is indistinguishable from not being available.

What CAP does not say.

It does not say you must sacrifice C or A all the time — only during an actual partition. Systems can be fully C and A during normal (non-partitioned) operation; PACELC is the framework for reasoning about that regime.
It does not forbid partial availability (e.g., serving reads but rejecting writes) or tunable consistency (e.g., "consistent enough" quorum reads) — these are refinements within the CP/AP space, not counterexamples to the theorem.
It says nothing about single-node systems, where there is no network to partition, hence "CA" is a degenerate, not a competitive, category.
It is a worst-case, adversarial-network result. In practice partitions are rare and often brief, so many systems optimize for the common case (fully available and consistent) and pay the CAP cost only during rare partition windows — but they must still have a defined behavior for that window, or they are simply unspecified (and typically unsafe) under partition.

Honest tradeoffs. Choosing CP means your system has planned unavailability windows that are a feature, not a bug — correctness over uptime. Choosing AP means your application layer must handle conflict resolution (via Replication Strategies such as vector clocks, CRDTs, or last-write-wins), which pushes complexity from the storage layer to the application layer. Neither choice is "better" in the abstract; the right choice depends on whether stale reads or rejected requests are more costly for the specific workload — a fraud-detection ledger tolerates downtime far better than it tolerates double-spending, while a "likes" counter on a social post tolerates staleness far better than downtime.

Worked example

Trace a concrete scenario: a 3-node key-value cluster storing `account:42 = $100`, replicated with nodes$ N_1, N_2, N_3 $, using majority quorum ($ W $= writes needing 2 acks,$ R $= reads needing 2 acks) as a baseline, then compare CP and AP behavior when a partition isolates$ N_3 $from$ \{N_1, N_2\}$.

Step	Event	CP system (e.g., quorum/Raft-style)	AP system (e.g., Dynamo-style, sloppy quorum)
0	All nodes healthy, balance = $100 everywhere	—	—
1	Network partitions: $N_3$ isolated from $N_1, N_2$	Partition detected via failed heartbeats	Same detection, different response
2	Client A writes `withdraw $30` to$ N_1$ (majority side)	$N_1, N_2$ form a quorum (2 of 3) → write commits, balance = $70 on$ N_1, N_2$	Same: write succeeds on $N_1, N_2$ ; balance = $70 there
3	Client B reads balance from $N_3$ (minority side)	$N_3$ cannot reach a quorum → request rejected / times out. Client B gets an explicit error, retries later.	$N_3$ answers locally with its last known value: $100 (stale). Client B proceeds believing balance is$ 100.
4	Client B, believing balance = $100, attempts `withdraw$ 90` on $N_3$	Rejected outright (no quorum) — impossible to even attempt locally	$N_3$ accepts the write locally: balance = $10 on$ N_3's replica, conflicting with $70 on the majority side
5	Partition heals	$N_3$ syncs from the quorum's committed log; balance = $70 everywhere. No conflict ever existed.	Conflict detected: $N_3$ has $10, majority has$ 70. Reconciliation needed — e.g., vector-clock comparison, application-level rule ("orders can't go negative"), or manual review.
6	End state	Correct balance everywhere, but Client B experienced an outage during step 3–4	No outage anywhere, but a real overdraft may have occurred and must be resolved after the fact

This trace shows precisely what the theorem predicts: the CP system is safe (balances never diverge) but unavailable during the partition for the minority side; the AP system is always responsive but permits a real anomaly (spending $90 the account did not have) that must be caught and fixed later, typically by application logic layered on top of the [[Data Partitioning and Sharding]] scheme that placed the replicas. Neither system is "wrong" — they encode different answers to "what should happen when$ N_3$ can't reach the others," and the right answer depends on whether an overdraft or a temporary outage is the worse outcome for this particular application.

Common pitfalls & traps

Pitfall	Why it happens	Fix / correct framing
Claiming a system is "CA"	Marketing conflates "consistent and available most of the time" with the CAP guarantee	CA is only meaningful for single-node systems; any multi-node system must specify CP or AP behavior under partition
Confusing CAP's "C" with ACID's "C"	Both use the letter "Consistency"	CAP's C = linearizability (a real-time recency guarantee); ACID's C = constraints/invariants are preserved by transactions — unrelated concepts
Treating CAP as "pick any 2 of 3, always"	The triangle diagram is visually symmetric, suggesting free choice	P is not optional in a real network; the actual choice is C vs. A, only exercised during a partition
Ignoring PACELC / assuming no tradeoff exists absent a partition	CAP is silent about the non-partitioned case	Even with a healthy network, strong consistency requires coordination, which costs latency (the "ELC" branch)
Assuming "eventual consistency" means "no consistency"	The name sounds vague	Eventual consistency is a precise model — see Eventual Consistency and Consistency Models — with convergence guarantees, just not real-time recency
Designing a global CP/AP policy instead of per-operation	Simpler to reason about	Modern systems tune consistency per request (e.g., quorum reads for money, eventual reads for view counts) for better cost/availability balance

Pioneers & history

Origins · 1 minEric A. Brewer and how this was discovered

Eric A. Brewer

born 1959 · distinguished engineer at Google, professor at UC Berkeley

Brewer co-founded Inktomi, one of the earliest large-scale internet search infrastructure companies, where he confronted the practical reality that strongly consistent, always-available, partition-tolerant distributed storage was unattainable at web scale. He articulated the CAP conjecture in a keynote address at the 2000 ACM Symposium on Principles of Distributed Computing (PODC), framing it as a guiding principle for engineers building large replicated systems rather than as a formal theorem at first.

History

2000

— Eric Brewer states the CAP conjecture in a PODC keynote address.

2002

— Seth Gilbert and Nancy Lynch publish a formal proof of the CAP theorem in ACM SIGACT News.

2007

— Amazon publishes the Dynamo paper, popularizing the AP design point for large-scale key-value stores.

2010

— Daniel Abadi proposes PACELC, extending CAP to cover the latency-consistency tradeoff absent a partition.

2012

— Brewer revisits CAP in a retrospective ("CAP Twelve Years Later"), clarifying common misreadings of the theorem.

Where this matters

CAP and PACELC are not academic curiosities; they are load-bearing design decisions embedded in the architecture of nearly every large distributed data system in production.

Amazon DynamoDB and Riak trace their lineage directly to the 2007 Dynamo paper's AP design: tunable per-request consistency (`eventual` vs. `strong`), sloppy quorums, and hinted handoff for reconciling writes accepted during a partition.
Apache Cassandra exposes consistency levels (`ONE`, `QUORUM`, `ALL`, `LOCAL_QUORUM`) per query, letting an application pick a point on the CP–AP spectrum for each read or write, a direct operationalization of the CAP tradeoff.
Google Spanner targets the CP corner, using TrueTime (synchronized atomic clocks) and Paxos-based replication to offer externally consistent transactions globally, explicitly accepting reduced availability during network or clock anomalies as the price of strong consistency.
etcd and ZooKeeper, built on Raft and Zab consensus respectively, are CP by design: a partitioned minority of nodes cannot serve writes (and often not reads) because it cannot form a quorum — this is intentional, since these systems back configuration and leader-election data where staleness is dangerous.
MongoDB lets operators choose write concern (`w: majority` for CP-like durability) and read concern, again making the CAP tradeoff a configuration parameter rather than a fixed architectural commitment.
CDNs and DNS are classic AP systems at planetary scale: they always answer, but different regions may briefly see different (stale) data after an update — an acceptable tradeoff because staleness of a webpage is far cheaper than a global outage.

Understanding CAP is a prerequisite for reasoning about Replication Strategies (how many copies, and how they stay in sync), Data Partitioning and Sharding (how data is split so that partitions of the network don't have to mean partitions of the dataset in confusing ways), and the richer consistency vocabulary developed in Eventual Consistency and Consistency Models and the practical system survey in NoSQL Data Models Overview.

Ask the tutor: How would you redesign the two-node write/read scenario if the system used synchronous chain replication instead of a simple two-node quorum — would the CAP tradeoff disappear or just move?

Does CAP mean I must sacrifice consistency or availability all the time?

No. CAP constrains behavior specifically during a network partition. When the network is healthy, a well-designed system can offer both strong consistency and high availability simultaneously — this is the common case for most deployments, since partitions, while inevitable eventually, are typically rare and short. What CAP demands is that the system have a defined, deliberate policy for the partition case: either reject some requests (CP) or risk serving stale data (AP). Systems that have no defined behavior for partitions are not exempt from the theorem — they are simply unspecified, which in practice usually means unsafe, since undefined behavior under partition tends to silently produce data corruption rather than a clean tradeoff.

Is "CA" ever a legitimate category for real systems?

Only degenerately, for single-node systems where there is no network link to partition — for instance, a standalone PostgreSQL instance with no replication. Once you introduce a second node with a synchronous replication link and no fallback plan for that link failing, you have implicitly chosen either CP (block if the link fails) or AP (proceed anyway), whether or not the label is applied consciously. Some vendor materials describe multi-node systems as "CA" as a shorthand for "consistent and available under normal, unpartitioned operation," but this is an informal use of the term, not the CAP theorem's actual CA category.

How is CAP's Consistency different from the eventual consistency I hear about in NoSQL systems?

CAP's Consistency (linearizability) requires that a read always reflect the most recently completed write, with no staleness window whatsoever — effectively as if there were only one copy of the data. Eventual consistency, the model used by many AP NoSQL systems, explicitly permits reads to return stale values for some bounded or unbounded window after a write, with the only guarantee being that replicas will converge once writes stop arriving. These are different points on a spectrum of consistency models, explored in depth in Eventual Consistency and Consistency Models; eventual consistency is a deliberate, much weaker relaxation chosen specifically to preserve availability under partition.

What is PACELC and why do practitioners prefer it to plain CAP?

PACELC, proposed by Daniel Abadi, states: if a Partition occurs, choose between Availability and Consistency (CAP's tradeoff); Else (normal operation), choose between Latency and Consistency. Practitioners prefer it because network partitions are relatively rare events, while the latency cost of maintaining strong consistency is a constant, everyday tax paid on every request that needs cross-node coordination. PACELC lets engineers classify and compare systems (e.g., Cassandra as PA/EL, Spanner as PC/EC) using a framework that captures the tradeoff that actually dominates day-to-day operational experience, not just the rare partition scenario.

Can a system be AP for writes but CP for reads, or vary by operation?

Yes, and many production systems do exactly this. Consistency and availability policies can be applied per-operation-type, per-key, or even per-request, rather than as a single global system property. For example, Cassandra lets each query specify a consistency level (`ONE` for low-latency/AP-leaning, `QUORUM` or `ALL` for stronger/CP-leaning behavior), and a single application might use eventual reads for a "recently viewed" feature while requiring quorum reads for balance queries. This flexibility does not violate CAP — the theorem still holds for each individual operation's guarantee — but it lets system designers apply the tradeoff surgically rather than uniformly.

Does CAP apply to a single-datacenter cluster with fast, reliable networking?

Yes, in principle, though the probability of a partition is much lower than in a wide-area deployment. Partitions can still occur within a single datacenter due to switch failures, misconfigured VLANs, garbage-collection pauses that make a node unreachable, or network card failures — anything that prevents two live nodes from exchanging messages counts as a partition in the CAP model. Systems deployed within one datacenter often optimize for the common case of a healthy network (low-latency strong consistency) while still needing a defined, tested policy for the rare partition event, since "it probably won't happen" is not a substitute for a correctness argument.

How does CAP relate to the choice of replication and sharding strategy?

CAP describes the consistency/availability tradeoff for replicated copies of the same data; Replication Strategies determine how many copies exist and how writes propagate among them (synchronous quorum, asynchronous log shipping, leaderless gossip, etc.), which directly determines whether the system leans CP or AP. Data Partitioning and Sharding is largely an orthogonal concern — it determines which node owns which subset of data — but a partition-tolerant design typically combines both: data is sharded for scale, and each shard's replicas independently face the CAP tradeoff if a network partition isolates some of them from the others.