Revisiting the CAP Theorem: Misconceptions, Practical Trade‑offs, and Managing Partitions

Why the “two‑of‑three” Formula Is Misleading

The simplest way to understand CAP is to imagine two nodes on opposite sides of a network partition; allowing at least one node to accept writes breaks consistency (C), while making one side unavailable breaks availability (A). Only if both sides can communicate can both C and A be satisfied, which then sacrifices partition tolerance (P). In practice, designers of cross‑region systems cannot discard P, so they must choose between C and A, a choice often oversimplified by the "two‑of‑three" slogan.

CAP was introduced in the late 1990s and quickly became the theoretical basis for many novel distributed systems and the NoSQL movement, which used it to argue against traditional relational databases.

ACID, BASE, CAP

ACID (Atomicity, Consistency, Isolation, Durability) represents the classic relational database philosophy focused on strong consistency, whereas BASE (Basically Available, Soft state, Eventually consistent) was coined to describe designs that prioritize availability and tolerate temporary inconsistency. CAP’s C is a stricter subset of ACID’s consistency, applying only to a single replica.

The four ACID properties are explained: Atomicity ensures indivisible operations; Consistency enforces database rules (a stricter guarantee than CAP’s C); Isolation requires global communication for serializability, which is impossible during a partition; Durability is usually retained, though some BASE designs relax it for performance.

CAP and Latency

Although the classic CAP statement ignores latency, in reality latency and partition are tightly coupled. When a request cannot be completed within a timeout, the system must decide whether to abort (reducing availability) or proceed (risking inconsistency). Algorithms such as Paxos or two‑phase commit merely postpone the decision.

Designers can set explicit timeouts to trigger a "partition mode"; shorter timeouts cause more frequent entry into this mode, even when the network is merely slow rather than truly partitioned.

CAP Confusion

Many misunderstand the scope of consistency and availability, especially when users cannot reach the service at all. Offline modes, now common with HTML5 storage, often force a choice favoring availability and require later reconciliation.

Real‑world systems such as Yahoo’s PNUTS, Facebook’s replica strategy, and Google’s use of Paxos illustrate different ways to balance C, A, and P, often by limiting operations during partitions or by accepting eventual consistency.

Managing Partitions

Effective partition management involves three explicit steps: detecting the start of a partition, entering a clearly defined partition mode that restricts certain operations, and launching a recovery process once communication is restored.

During partition mode, a system can either limit operations (reducing availability) or record extra information to aid later recovery, while continuously probing to detect when the partition ends.

Which Operations Can Be Executed?

Deciding which operations to allow depends on the invariants the system must preserve. For example, uniqueness constraints on primary keys are often relaxed during a partition, with duplicate keys detected and merged during recovery.

Operations that could violate critical invariants (e.g., external financial transactions) are typically logged and deferred until after the partition, sacrificing immediate availability but preserving correctness.

Partition Recovery

When communication resumes, the system must (1) make the two sides’ states identical and (2) compensate for errors that occurred during the partition. A common approach is to roll back to the state at the beginning of the partition and replay logged operations in a deterministic order, as done by systems like Bayou.

When automatic merging is impossible, manual conflict resolution may be required, similar to version‑control merges.

Compensating Errors

Beyond state reconciliation, systems must also compensate for external effects caused by erroneous operations during a partition. Strategies range from "last‑writer‑wins" to more sophisticated compensation transactions that reverse or mitigate the impact (e.g., refunding a duplicate charge).

Compensating transactions are especially important for long‑lived operations where holding locks for consistency would hurt availability.

Compensation Problem in ATMs

ATM design illustrates the trade‑off: strong consistency would prevent overdrafts but would also reduce availability and revenue. Modern ATMs limit net withdrawals during a partition (e.g., a $200 cap) to balance risk and availability.

After the partition, the bank reconciles any negative balances, often by charging overdraft fees or by accepting the loss if the customer has already deposited funds.

Acknowledgements

The authors thank Mike Dahlin, Hank Korth, Marc Shapiro, Justin Sheehy, Amin Vahdat, Ben Zhao, and volunteers from the IEEE Computer Society for their valuable feedback.

Author Biography

Eric Brewer is a Professor of Computer Science at the University of California, Berkeley and VP of Infrastructure at Google. His research interests include cloud computing, scalable servers, sensor networks, and technologies for developing regions. He earned his Ph.D. in EECS from MIT, is a member of the National Academy of Engineering, and can be contacted at [email protected].