The CAP Theorem and PACELC

Symptom

Someone in a design review says “we’re AP, not CP,” and the room nods.

Nobody asks which consistency, which availability, or what happens when there is no partition, which is 99.9% of the time. The phrase has done the work of a decision without containing one.

Meanwhile the actual system: reads sometimes return values from thirty seconds ago, and nobody can say whether that is expected. It is not a partition; the network is fine. It is an asynchronous replica that was chosen for latency, and that choice was never in the CAP framing at all. The theorem everybody quoted is silent about the situation the system spends its entire life in.

The other symptom is the opposite error. A team refuses to use a replicated database because “CAP says you can’t have consistency and availability,” and builds on a single node instead, which has neither.

Statement

Brewer’s conjecture, proved by Gilbert and Lynch:

A distributed data store cannot simultaneously provide linearizable consistency, total availability, and tolerance of network partitions. When a partition occurs, a system must choose between consistency and availability.

The precision matters more here than anywhere else in this series, because almost every popular restatement is wrong in a way that changes the engineering.

“Pick two” is the wrong reading. Partitions are not a design choice. They are a property of networks, and networks partition: cables get cut, switches misconfigure, a datacenter link saturates. You do not get to choose P. The theorem is therefore a conditional, and Brewer himself said so in 2012: if a partition happens, then you choose C or A.

“C” is not the C in ACID. CAP’s C is linearizability, a single-object recency guarantee. ACID’s C is a schema-and-invariant guarantee that a transaction preserves. They are unrelated, and the collision of the letter is responsible for an enormous amount of confused writing.

“A” is not uptime. CAP availability means every request to every non-failing node returns successfully. A system that is up 99.999% of the time is not CAP-available if a single node ever returns an error during a partition. No production system is CAP-available in this sense, and the metric that operations teams call availability is a different quantity entirely.

Argument

The proof is two lines and looks like FLP’s. Take two nodes $A$ and $B$ holding a replicated value $v_0$. Partition them so no messages pass.

A client writes $v_1$ to $A$. If the system is available, $A$ must acknowledge without hearing from $B$. Another client reads from $B$. If the system is available, $B$ must answer without hearing from $A$, so it answers $v_0$.

But a linearizable history requires the read, which happens after the completed write in real time, to return $v_1$. It returned $v_0$. So the system is not linearizable. The only alternative was for $A$ or $B$ to refuse to answer, which forfeits availability. $\blacksquare$

It is once again an indistinguishability argument. $B$ cannot tell “no write happened” from “a write happened and I cannot hear about it,” so whatever it does must be wrong in one of the two worlds.

PACELC is the statement that is actually useful. Abadi’s observation is that CAP describes a rare event and says nothing about the common one:

Partition: Availability or Consistency? Else: Latency or Consistency?

The else-branch is where systems live. With no partition at all, a replicated write can be acknowledged immediately (low latency, weak consistency) or after replicas confirm (higher latency, strong consistency), and that choice is made on every single write, forever, whereas the partition choice is made a few times a year.

The classification is concrete:

PNUTS is the interesting row, because it is the combination CAP cannot express and it was a deliberate choice by Yahoo: give up consistency for latency in normal operation, then become strict when the network breaks. Any framework that cannot describe that design is not a design tool.

Why the latency branch is not optional. A cross-continental round trip is roughly 150 ms, fixed by the speed of light in fiber, and that is the floor for synchronous replication between London and Sydney. No engineering removes it. So a globally replicated system choosing EC is choosing to add that to every write, and choosing EL is choosing to serve some stale reads. That decision has vastly more effect on your product than what happens during the two hours a year when a link is down.

Brewer’s own retraction is worth reading as a design method. His 2012 essay “CAP Twelve Years Later” argues the useful framing is not to choose a letter but to plan the partition: detect it, enter an explicitly degraded mode, record what was done during it, and reconcile afterward. Under that framing the question stops being “are we CP or AP” and becomes “what operations do we allow while split, and how do we merge.” An ATM that dispenses up to a limit while offline and reconciles later is applying exactly this, and so is a shopping cart that accepts additions during a partition and resolves duplicates on heal.

Forbids

A globally distributed, linearizable, always-available store. Every vendor claim of all three at once is either redefining a term or is a claim about the non-partitioned case.

“Eventually consistent” as a description of behaviour under partition. It tells you the system converges eventually, which is compatible with any amount of divergence for any length of time. It is a liveness property with no bound, and using it as a reassurance is a category error.

Free strong consistency across regions. The latency is a physical constant, and any system offering cross-region linearizable writes at single-region latency has moved the cost somewhere you have not looked yet, usually to a lease or a clock assumption.

Escaping the choice by adding replicas. More replicas make partitions more likely, not less, since there are more links to break.

Does not forbid

It does not forbid strongly consistent distributed databases. This is the most expensive misreading, because it steers teams away from tools that would have solved their problem. Spanner, CockroachDB, FoundationDB, and etcd are all linearizable and all run in production at scale. They are CP: during a partition, the minority side stops serving. That is a perfectly good behaviour for most business data, and “stops serving” here means a small subset of requests for a few seconds during a rare event.

It does not mean NoSQL means eventual consistency. MongoDB defaults to strong consistency for reads from the primary, HBase is strongly consistent, and DynamoDB offers strongly consistent reads as a per-request option. The 2010-era equation of NoSQL with AP was a snapshot of one design generation, not a theorem.

It does not forbid per-operation choices. The same system can be CP for payments and AP for view counters. Cassandra’s consistency levels and DynamoDB’s consistent-read flag are exactly this, and treating CAP as a whole-system property gives up a knob that exists at the request level.

It does not apply to a single node. A non-distributed database has no partitions and no tradeoff. It also has no fault tolerance, which is the trade you actually made.

It does not say partition-tolerant systems must be unavailable during partitions for all operations. A CP system typically keeps serving on the majority side. Availability is lost for the minority, which may be a small fraction of clients, and describing that as “the system is down” overstates it considerably.

Boundary

CAP assumes the asynchronous model with no clocks, and linearizability as the consistency target. Both are where the escapes live.

• Weaken consistency and the impossibility dissolves. Causal consistency (T059) is the strongest model achievable with total availability under partition, which is a sharp result rather than a hedge: you can have all the ordering that causality implies, and no more, at zero coordination cost.
• Add clocks. Spanner’s TrueTime uses GPS and atomic clocks to bound clock skew, converting an asynchronous system into a nearly synchronous one and buying external consistency at the cost of waiting out the uncertainty interval, typically a few milliseconds, on commit.
• Restrict the operations. CALM (T067) says monotone programs need no coordination at all, so for that class of computation the tradeoff never arises.
• Bound the partition. Systems with a designated primary region can allow writes only there, making partitions an availability question for one side and a non-event for the other.

The framing worth keeping: CAP is a proof that one specific combination is impossible, PACELC is a design vocabulary, and Brewer’s partition-planning is the actual method. If a discussion is using CAP to choose a database, it is using the wrong one of the three.

Read next