CAP theorem without the slogan

CAP is an impossibility result for a replicated read/write object. In the asynchronous model, while messages between partitions may be lost, no algorithm can guarantee both:

• atomic (linearizable) consistency for every completed operation;
• availability in the paper's sense: every request received by a non-failing node eventually returns a response.

Partition tolerance is the failure condition being considered, not a product feature that can simply be exchanged for the other two. The choice becomes unavoidable during an execution in which the components cannot communicate.

Precise meanings

Atomic or linearizable consistency means operations can be placed in a single order that respects real time. If a write completes before a read begins, that read cannot return an older value.

CAP availability is stronger than a typical monthly uptime SLO and weaker about latency: it requires termination but gives no finite response-time bound. A timeout or deliberate rejection therefore gives up this formal availability property even though it may be the correct product behavior.

The theorem does not say that every database is permanently “CP” or “AP”, nor that all consistency models form one switch. A system may make different decisions by operation, key, failure mode, or policy.

During a partition

A consistency-preserving protocol may wait, reject, or route only to a component that can still prove a safe order. This preserves safety but some reachable clients do not receive successful results.

An availability-preserving protocol can accept independent operations on both sides. Because neither side can know the other side's concurrent history, it cannot promise one real-time atomic register. When communication returns, the application needs an explicit reconciliation rule: a commutative data type, domain merge, deterministic winner, or surfaced conflict. “Last timestamp wins” is not automatically safe when clocks and causality matter.

Quorums are a protocol, not arithmetic alone

Conditions such as W + R > N describe overlap of selected read and write sets, but overlap by itself does not prove linearizability. A complete protocol must define leaders or version ordering, membership changes, failure detection, read repair, concurrent writers, and which acknowledgement makes an operation complete. Sloppy quorums and hinted replicas can intentionally choose nodes outside the original replica set.

Scenarios

▶Walkthrough: normal-linearizable (not found)

A completed replicated write is ordered before a later read.

▶Walkthrough: partition-cp (not found)

The write is not acknowledged because the protocol cannot prove a safe order across the cut.

▶Walkthrough: partition-ap (not found)

Both components answer independently and later reconcile by a declared domain policy.

▶Walkthrough: scope (not found)

The animation separates the formal theorem from broader latency, durability and cost trade-offs.

Design checklist

• State the object and operation whose consistency is required.
• Define exactly when an operation is committed and what clients may retry.
• Treat timeout outcomes as unknown until an idempotency key or status read resolves them.
• Specify conflict representation and reconciliation before enabling writes on both sides.
• Test membership changes, partitions, clock anomalies and recovery, not only replica crashes.
• Use an SLO/SLI for production availability; do not substitute the CAP definition.

Primary sources

• Gilbert and Lynch, Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services: https://www.cs.princeton.edu/courses/archive/spring21/cos418/papers/cap.pdf
• Herlihy and Wing, Linearizability: A Correctness Condition for Concurrent Objects: https://www.cs.cmu.edu/~wing/publications/HerlihyWing90.pdf