CAP Theorem

Also known as: Brewer's Theorem

framework · computer science · formal-scientific

Distributed system can guarantee at most two of consistency, availability, partition tolerance.

The CAP Theorem was proposed by Eric Brewer as a conjecture in his 2000 PODC keynote and proved formally by Seth Gilbert and Nancy Lynch in their 2002 paper. The theorem holds that any distributed data store can simultaneously provide at most two of three properties: Consistency (every read receives the most recent write or an error), Availability (every request receives a non-error response), and Partition tolerance (the system continues operating despite arbitrary message loss between nodes). Because real networks always partition eventually, P is typically not optional, and the practical CAP choice reduces to CP versus AP — choose consistency and refuse to serve during partitions, or choose availability and risk serving stale or divergent data. Brewer's 2012 'CAP Twelve Years Later' clarified that the binary trade-off is itself an oversimplification, with practical systems making fine-grained per-operation choices and using techniques like partition recovery to mitigate the trade-off. CAP fundamentally shaped the NoSQL movement and contemporary distributed-systems thinking.

Originators

Eric Brewer (conjecture); Seth Gilbert and Nancy Lynch (formal proof) high

Year / Decade

2000 (Brewer PODC keynote); 2002 (Gilbert & Lynch proof); 2012 (Brewer 'CAP Twelve Years Later') high

Primary sources

Brewer, E. (2000). 'Towards Robust Distributed Systems', PODC keynote, Gilbert, S. & Lynch, N. (2002). 'Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services', ACM SIGACT News, Brewer, E. (2012). 'CAP Twelve Years Later: How the "Rules" Have Changed', IEEE Computer high

Core components

Consistency (every read sees most recent write or error)
Availability (every request gets non-error response)
Partition tolerance (system continues despite network partition)
Pick at most two
Practical reduction to CP vs AP since P is not optional
Fine-grained per-operation choices in practice
Connection to ACID (CP-leaning) and BASE (AP-leaning)

Primary use case

Foundational analytical framework for distributed-system design choices; framing for NoSQL database architectural decisions; teaching tool for understanding consistency-availability trade-offs; reference in choosing between database options for specific applications.

Common criticisms

Original 2-of-3 framing is widely acknowledged as an oversimplification — Brewer's 2012 clarification noted real systems make fine-grained operation-level choices and that partition recovery enables nuanced trade-offs
'Consistency' in CAP is linearizability, a much stronger property than ACID's transactional consistency, leading to terminological confusion
PACELC (Abadi 2010) extends CAP by addressing latency-vs-consistency trade-off in the absence of partitions
CAP is sometimes invoked to dismiss as impossible solutions that are actually feasible with careful design
binary framing tends to obscure the rich design space distributed systems actually inhabit.

Lineage

Parent of: PACELC Theorem
Siblings: ACID Properties, BASE Properties, PACELC Theorem