CAP Theorem¶

A distributed data store cannot guarantee consistency and availability at once during a network partition, and since real networks always partition, the architect must choose which to sacrifice when one strikes.

Version: v3 · 2026-09-28 · History · 1 correction
Domain-specific #: 132
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Distributed Systems → Computer Science & Software Engineering

Core Idea¶

The CAP theorem (Brewer 2000; proved by Gilbert and Lynch 2002) states that a distributed data store cannot simultaneously guarantee Consistency (every read returns the latest write), Availability (every node answers in finite time), and Partition tolerance (it keeps operating when inter-node messages are lost). During a partition a store that must answer may serve stale data, while one that must stay consistent must refuse. Because real networks always partition, the choice collapses to consistency versus availability.

How would you explain it like I'm…

Answer Now or Get It Right

Two friends each keep a copy of the same notebook and pass notes to keep them matching. If the notes get stuck and someone asks one friend a question, that friend has to choose: answer right now, maybe with old information, or say 'wait, I can't answer yet' until the notes get through. While the notes are stuck, a friend can't always answer and always be up to date at the same time.

Up-to-Date or Always Answering

Big computer systems keep copies of the same data on many computers that talk to each other over a network. Sometimes the messages between those computers get lost or stuck, and the network is split into parts that cannot talk. The CAP theorem says that when that happens, the system must choose: either every computer keeps answering, even if some answers are out of date, or the system refuses some requests so that every answer is up to date. You cannot have 'always answers' and 'always up to date' at the same time while the network is split. Since networks really do break sometimes, every such system has to pick which one it gives up.

Consistency vs. Availability Under Partition

The CAP theorem is about data stored across many networked machines. It names three guarantees: Consistency (every read sees the latest successful write), Availability (every working machine answers every request), and Partition tolerance (the system keeps running even when messages between machines are lost or delayed). It proves you cannot guarantee all three at once. Because network partitions really do happen, partition tolerance is not optional, so the true choice is: during a partition, give up consistency or give up availability. 'CP' systems refuse or error out rather than give stale answers, while 'AP' systems keep answering and fix disagreements between copies later. A later refinement, PACELC, adds that even without a partition there is a trade-off between speed and consistency.

Conjectured by Brewer and proved by Gilbert and Lynch, the CAP theorem states that a distributed data store cannot simultaneously guarantee linearizable Consistency, Availability (every non-failing node returns a non-error response in finite time), and Partition tolerance (operation despite arbitrary lost or delayed messages). The proof works in the asynchronous network model, where message delays are unbounded: during a partition, a node that must answer cannot know whether it has missed a write elsewhere, so answering risks violating linearizability, and preserving linearizability requires sometimes not answering. Because partitions are an environmental fact of real networks (hardware failure, congestion, misrouting), the practical reading is not 'choose two of three' but 'during a partition, choose C or A.' CP systems such as Bigtable, Spanner, etcd, and HBase refuse or error during a partition; AP systems such as Cassandra, DynamoDB, Riak, and CouchDB keep serving and let replicas diverge, later reconciling via last-write-wins, CRDTs, or application-level merge. PACELC extends this: Else (no partition), systems trade Latency against Consistency, because synchronous replication costs round trips while asynchronous replication risks stale reads.

Scope of Application¶

Its reach is within replicated data stores — the formalism stays home — across the distributed-systems and database-engineering subfields of computer science.

NoSQL and distributed-database design — its canonical home; the CP/AP taxonomy classifies stores by partition behaviour.
Consensus protocol design — Paxos and Raft trade availability for a quorum's linearizability.
Eventual-consistency machinery — the AP branch's reconciliation toolkit (CRDTs, vector clocks, Merkle anti-entropy).
Multi-region cloud architecture — whether geo-distributed services serve stale reads or refuse during inter-region partitions.
Distributed-systems impossibility theory — CAP sits with FLP and Two-Generals as a formal impossibility bounding designs.

Clarity¶

Classifying a store as CP or AP forces the architect to make precise what marketing terms like "highly available" leave vague: what the consistency guarantee actually is, what availability means, and how partitions are handled. The operative question sharpens from "is this system reliable?" to "when the network partitions, does this store serve stale data or refuse — and is that what this workload needs?"

Manages Complexity¶

The catalogue of distributed stores is bewildering — dozens of products, each with its own replication and consistency model, marketed in incomparable adjectives. CAP collapses it to one forced binary, CP or AP, having disposed of partition tolerance as an environmental fact rather than a knob. The architect reads failure behaviour off one label instead of internals; PACELC adds a second letter for the latency-versus-consistency choice at steady state.

Abstract Reasoning¶

The theorem licenses a boundary-drawing move that treats partition tolerance as a given, making the live question consistency-versus-availability during a partition. It supports a diagnostic move that reads failure-time behaviour off the CP/AP label without re-deriving internals (and runs in reverse), and an interventionist move that matches the bit to each data class — with relaxing the consistency requirement itself a second lever that buys back availability.

Knowledge Transfer¶

Within computer science the CAP theorem transfers as mechanism, intact: from its NoSQL home it shapes consensus protocols, eventual-consistency machinery, and multi-region architecture without translation. Beyond it, CAP is the distributed-data-store instance of a broader trilemma — three desirable properties, a constraint forbidding all three, a forced choice of two — recurring as co-instances like Mundell's open-economy trilemma, and that Trilemma parent carries the cross-domain weight. The caution: the formalism making CAP a theorem (linearizability, the Gilbert-Lynch proof, PACELC) is distributed-systems-bound, so naming a non-distributed trilemma "the CAP theorem of X" smuggles in machinery the substrate cannot meet.

Relationships to Other Abstractions¶

Current abstraction CAP Theorem Domain-specific

Parents (2) — outgoing typed relations

CAP Theorem is a kind of Axiomatic Incompatibility Prime

CAP is axiomatic incompatibility specialized to consistency, availability, and partition tolerance over replicated state.
CAP Theorem is a kind of Trilemma Prime

CAP is a trilemma specialized to consistency, availability, and partition tolerance in an asynchronous replicated data store.

Children (1) — abstractions linked here by typed relations

PACELC Theorem Domain-specific includes CAP Theorem

PACELC contains the CAP partition-regime choice and adds an Else-regime latency-versus-consistency coordinate.

Hierarchy paths (2) — routes to 2 parentless roots

CAP Theorem → is a kind of Axiomatic Incompatibility

Show alternative path (1)

Neighborhood in Abstraction Space¶

CAP Theorem sits in a moderately populated region (60^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Distributed Systems Theorems & Fallacies (19 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25