CAP & PACELC

The CAP theorem is the most-cited and most-misquoted result in distributed systems. The version repeated at conferences — "pick two of three" — is misleading in nearly every operational sense. The real statement is narrower, weaker, and more useful.

This page covers the theorem as a theoretical tool: what it formally claims, why the proof works, the common misreadings, and where PACELC sharpens it. For the storage-system flavor — databases that pick CP vs AP, configuration tips — see database/advanced/cap-theorem.

What CAP Actually Says

Brewer's 2000 conjecture, formalized by Gilbert and Lynch in 2002, talks about three properties of a distributed data store:

• Consistency (C) — every read returns the value of the most recent write, or an error. This is linearizability (see Consistency Models), not the looser "C" from ACID.
• Availability (A) — every request to a non-failing node receives a non-error response, eventually.
• Partition tolerance (P) — the system continues to operate despite arbitrary message loss between nodes.

The formal claim is:

In an asynchronous network with partitions, no protocol can guarantee both C and A for all clients.

That is the whole theorem. Notice what it does not say:

• It does not say a system can be "CA". In any real network, partitions happen — they are a property of the medium, not a design choice. "CA" is not a meaningful operating point; it is the absence of distribution.
• It does not say you must permanently sacrifice C or A. The choice is per-request, during a partition. The rest of the time both can hold.
• It does not say anything about latency, throughput, or any other property people lump in with "consistency."

Proof Intuition

The argument is short enough to carry in your head.

   Client 1                          Client 2
     │                                  │
     │ write x=1                read x  │
     ▼                                  ▼
  ┌───────┐         ╳╳╳╳╳         ┌───────┐
  │ Node A│◀────network split────▶│ Node B│
  │ x=1   │                        │ x=0   │
  └───────┘                        └───────┘

Suppose nodes A and B are partitioned. Client 1 writes x=1 to A. Client 2 reads x from B.

• If B returns 0, the read is not linearizable — a later read returned an earlier value. Consistency is violated.
• If B refuses to respond (waits for A or errors), availability is violated.
• If B could synchronize with A first, there would be no partition; we assumed there is one.

There is no third option. The system must give up one of C or A for this request. That is all the theorem proves.

Common Misreadings

"You can have any 2 of CAP."

Strictly false in the practical sense: you cannot avoid P. The honest framing is: during a partition, choose between C and A. Outside of partitions, both can hold.

"NoSQL chose A; SQL chose C."

Both database families contain CP and AP systems. Postgres with synchronous replication is CP. MongoDB with majority writes is CP. Cassandra with LOCAL_QUORUM reads/writes is tunable (see Quorum Systems). The label belongs on the configuration, not the brand.

"CAP is about consistency in general."

It is specifically about linearizability of single-object reads/writes. Multi-object transactions, causal consistency, snapshot isolation — these have their own results (often more permissive). A system that violates CAP-style C can still offer strong-enough guarantees for many real applications. See Consistency Models.

"Eventual consistency is the same as AP."

Eventual consistency is a liveness property of AP systems: if writes stop, replicas converge. AP is the partition-time choice; eventual consistency is what the system does afterward. They are related, not identical.

PACELC: The More Honest Extension

Daniel Abadi's 2010 PACELC formulation fixes CAP's biggest blind spot: the theorem only describes behavior during a partition, but most systems are not partitioned most of the time. What governs their behavior then?

If there is a Partition, choose between Availability and Consistency. Else (normal operation), choose between Latency and Consistency.

Every distributed store has a PA/EL, PA/EC, PC/EL, or PC/EC profile. The interesting tradeoffs in production are almost always on the EL/EC side:

PACELC's contribution is not "another acronym." It is the recognition that the latency-vs-consistency trade is the more important one in day-to-day operation, and CAP alone hides it.

Practical Takeaways

1. Stop calling systems "CA". Either they tolerate partitions (CP / AP) or they are single-node.
2. Decide per-operation, not per-system. Many real designs use linearizable writes for some keys and AP reads for others.
3. PACELC is the better mental model. The interesting question is rarely "what happens during a partition?" but "what latency are we willing to pay to be correct?"
4. Linearizability is one consistency model. CAP is silent about the others, and those others are often what you actually need. Read Consistency Models before deciding you need "CP."
5. Partitions are rarer than they look but longer than you think. When they do happen — cloud-provider network event, AZ isolation, misconfigured switch — they last minutes to hours, not seconds. Design for that timescale, not the rare-event one.

Further Reading

• Brewer, Towards Robust Distributed Systems (PODC 2000) — the original keynote.
• Gilbert & Lynch, Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services (2002) — the proof.
• Abadi, Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story (2012) — PACELC.
• Brewer, CAP Twelve Years Later: How the "Rules" Have Changed (2012) — Brewer's own clarification.
• Kleppmann, A Critique of the CAP Theorem (2015) — argues CAP is too informal to be useful and suggests alternatives.

Pre-commit Checklist

• Am I claiming "CA" anywhere? Replace with single-node or "low-partition-frequency CP".
• For each multi-node read/write, did I name which side of PACELC it sits on?
• For "strong consistency" claims, did I mean linearizability, sequential, snapshot isolation, or something else? Be specific.
• Have I designed for partition durations of minutes, not milliseconds?