CAP and PACELC, stated precisely

What does CAP really say and not say, and why does the 'else' branch of PACELC carry most of the cost?

CaseConstructed case · Anika at Pebble

1,140 bonuses from a promotion of 1,000

Pebble runs a promotion: "the first 1,000 sign-ups get a 5 euro bonus." The promotion table promo(code, remaining) is replicated in Frankfurt and Singapore, and both regions accept sign-ups. During a 40-minute network partition between the regions (each region keeps working but cannot talk to the other), both regions keep handing out bonuses. At the end, 1,140 bonuses have been given. Each region's local check, "remaining > 0", was true every time.

A second request arrives: usernames must be unique across both regions. And the CTO, reading a blog post, asks in the all-hands: "Are we CP or AP?"

Anika has no good answer to the third question yet. She realizes the first two are about her rules (the invariants), and no database setting can know them. This is what she learns.

How it ends →

A question about the application

Transactional isolation, Distributed consistency and Sessions, convergence and quorums asked questions about systems. This article asks a question about an application: given this invariant, is coordination required? That is categorically different, because for the first time the answer depends on something no database can see: the semantics of what you are trying to keep true.

The surprise is that the question is not a matter of judgment. It is decidable from your schema and your transaction set, before you choose a database. The two theorems that decide it (invariant confluence, CALM) are less famous than the one that cannot (CAP).

CAP, stated precisely so it can be set aside

The CAP theorem (Gilbert and Lynch's formalization) is narrow in every term.

C is linearizability: one-copy atomic register semantics. It is not "consistency" in any general sense. It is emphatically not the C in ACID. The C in ACID means application-defined invariant preservation, and shares nothing with CAP's C except the letter.
A is total availability: every request to every non-failing node terminates with a non-error response. Not 99.99%. Not "the system is up".
P is a network that may drop or delay arbitrarily many messages.

The proof takes three sentences. Partition node A from node B. A client writes to A, which must respond without hearing from B. A client then reads from B, which must respond without hearing from A, and therefore returns the old value. No linearizable history contains both responses.

That a theorem this small carried a decade of architecture arguments is the interesting fact about it. What it does not say:

It is not "pick two of three." Partitions are a property of the world, not a design option. The theorem is a conditional: during a partition, choose. A system described as "CA" is a system that has not thought about partitions.
Its A is far stronger than operational availability. A so-called CP system is unavailable only to the minority side, and only while partitioned. Many AP systems have worse measured availability than CP ones, because partitions are not what takes systems down.
It says nothing about latency, which is what you pay during the 99.99% of the time when the network is fine.
It is about one register. It does not directly address transactions, which the next results cover.
The choice is per operation, not per system, as tunable consistency (Sessions, convergence and quorums) already showed.

CAP's durable contribution is naming the partition-time decision. Its practical contribution has been largely negative.

PACELC: the branch that actually runs

Abadi's extension: if there is a Partition, choose A or C; Else (no partition), choose Latency or Consistency.

The "else" branch runs all the time, and it is where r + w ≥ d lives.

Spanner is PC/EC. It pays the E-branch bill visibly, as commit wait.
Dynamo-style stores are PA/EL. They pay it as staleness.

The classification matters less than the reframe: most systems' entire consistency cost is paid in the E branch, and CAP pointed everyone at the branch that almost never executes. To know what a consistency choice costs you, look at your p99 latency on a normal Tuesday, not at your partition runbook.