CAP Theorem

Details
Full Name

CAP Theorem (Consistency, Availability, Partition tolerance)

Also known as

Brewer’s Theorem

Core Concepts:

The three properties

Consistency (every read sees the most recent write), Availability (every request gets a non-error response), Partition tolerance (the system keeps working despite dropped/delayed messages between nodes)

The trade-off

When a network partition occurs, a distributed system must choose between consistency and availability — it cannot have both during the partition

Partitions are not optional

Real networks partition, so P is a given; the genuine design choice is CP vs AP behaviour while partitioned

Common misreading

"Pick 2 of 3" is a simplification; outside a partition a system can be both consistent and available

PACELC extension

Else (no partition), trade Latency against Consistency — captures the everyday tuning that CAP alone omits (Abadi, 2012)

Key Proponents

Eric Brewer (2000 conjecture, PODC keynote); formally proved by Seth Gilbert & Nancy Lynch (2002); PACELC by Daniel Abadi (2012)

When to Use:

  • Choosing or evaluating a distributed datastore (CP vs AP behaviour)

  • Framing a concrete consistency/availability trade-off for a feature

  • Reasoning about behaviour during network partitions and failover

  • Explaining why strong consistency costs availability or latency

When NOT to Use:

  • For single-node systems with no replication (no partitions to tolerate)

  • As a crude "2 of 3" slogan — prefer the partition-time framing or PACELC

Criticism:

  • Eric Brewer himself, "CAP Twelve Years Later: How the 'Rules' Have Changed" (IEEE Computer, 2012) — the "2 of 3" formulation is misleading; the trade-off is narrower and more nuanced than the slogan suggests

  • Martin Kleppmann, "Please stop calling databases CP or AP" (2015) — CAP’s formal definitions are too narrow to classify real systems; many databases are neither CP nor AP under the theorem’s own terms

  • Alternative named in the discourse: reason with precise consistency models (linearizability, causal consistency, etc.) and the PACELC framing instead of the CP/AP dichotomy