Distributed systems impossibility result
CAP Theorem
During a network partition, a replicated system cannot guarantee both linearizable consistency and a successful response from every non-failing node.
Partition present -> choose C or A
In the formal asynchronous model, consistency means atomic or linearizable reads and writes; availability means every request to a non-failing node eventually receives a response. Partition tolerance is the failure being considered, not a free third feature.
Switch between a healthy network, a consistency-preserving partition response, and an availability-preserving response. Request counts are operational illustrations; the theorem itself is an impossibility result, not a throughput formula.
(requests)
The partition is the vertical cut. Under CP, unsafe requests stop at the cut; under AP, both sides answer and the copies can diverge until reconciliation.
- CHANGE
- Requests arriving during a partition
- WATCH
- C / A policy
- MEANING
- Switch between a healthy network, a consistency-preserving partition response, and an availability-preserving response. Request counts are operational illustrations; the theorem itself is an impossibility result, not a throughput formula.
The trade-off appears only across the cut.
Two replica groups lose contact. A consistent design blocks or rejects unsafe operations; an available design continues locally and accepts reconciliation work later.
What it actually says
CAP is not a product taxonomy and not a permanent instruction to pick two letters. It is an impossibility result about executions in which messages between parts of a distributed system are lost indefinitely: no algorithm can guarantee both atomic consistency and total availability in that execution.
The practical decision is granular. Systems can choose differently by operation, data item, user, region, partition duration, or confidence level. They can also weaken consistency, bound staleness, use leases, reject writes, serve cached reads, or degrade selected features.
"A useful law compresses a pattern. It does not erase the conditions that make the pattern true."
How the idea developed
The modern form emerged through observation, argument, and later refinement. The timeline separates the first insight from the version now used in textbooks and practice.[1]
Eric Brewer presents the consistency, availability, and partition trade-off.
Seth Gilbert and Nancy Lynch formalize and prove the asynchronous impossibility result.
Gilbert and Lynch revisit practical interpretations and the broader safety-liveness context.
Distributed databases expose tunable consistency, quorum, conflict, and failure policies rather than one global CAP label.
How the pattern works
The relation becomes useful only when its mechanism, measurement process, and operating range are visible.
A node cannot tell whether a remote replica is delayed, disconnected, or failed when no message arrives.
A response must reflect a single legal order of operations, so uncertain concurrent state may make answering unsafe.
Every request to a non-failing node must terminate, so waiting indefinitely for the other side is forbidden.
With communication severed, an algorithm cannot obtain both the missing information and the required timely response.
In the formal asynchronous model, consistency means atomic or linearizable reads and writes; availability means every request to a non-failing node eventually receives a response. Partition tolerance is the failure being considered, not a free third feature.
Where it earns its keep
Applications are strongest when the law changes a decision, measurement, model, or experiment rather than merely providing an analogy.
Define behavior by operation
ApplicationA payment write may reject on uncertainty while a product catalog read serves bounded-stale data.
Document guarantees per operation and failure mode, not per database logo.
Plan partition response
ApplicationTeams decide which regions accept writes, how leaders fail over, and how conflicts are detected.
Test long partitions and asymmetric reachability, not only clean outages.
Design honest degradation
ApplicationFeatures can switch to read-only, queue intents, or narrow their scope during communication loss.
Users need visible state when an accepted action is provisional.
Where it stops working
The theorem uses precise definitions. "Consistency" is linearizability in the classic proof, not every form of database consistency; "availability" requires a response from every non-failing node, not a high monthly uptime percentage.
CAP does not describe the normal no-partition trade-offs among latency, consistency, durability, throughput, cost, and freshness. PACELC and other frameworks address some choices that remain when the network is healthy.
"CAP means choose any two forever"
Better: When a partition occurs, the theorem forces a C/A trade-off for affected operations."Partition tolerance can be omitted"
Better: A distributed system cannot prevent network partitions; it can only choose behavior under them."Eventual consistency guarantees availability"
Better: A design can sacrifice both or fail for unrelated reasons."Consistency means ACID"
Better: The CAP proof concerns atomic or linearizable object behavior, not the whole ACID acronym.Sources and further reading
Original publications and serious secondary scholarship are prioritized over summaries.
- Gilbert and Lynch - Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web ServicesThe 2002 formal statement and proof of the CAP impossibility result.https://doi.org/10.1145/564585.564601
- Gilbert and Lynch - Perspectives on the CAP TheoremAuthors revisit definitions, practical implications, and safety versus liveness.https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf
- MIT CSAIL - Distributed Database Systems, CAP lectureUniversity course treatment of the theorem and its operating assumptions.https://dsg.csail.mit.edu/6.5830/lectures/lec18.pdf
- Nancy Lynch - Theory of Distributed Systems publication listAuthor-maintained publication record for the original paper and related work.https://groups.csail.mit.edu/tds/lynch-pubs.html