Eric Brewer — The CAP Theorem

<!-- hierarchy:nav -->

Path: OIP › Thinker Reference › Thinkers › Eric Brewer — The CAP Theorem

Shelf: Thinkers · Traversal: self-explaining · hierarchical · voxel-ready
Machine root: OIP tree · Registry

Eric Brewer — The CAP Theorem

§SELF — thinker-eric-brewer

What this page is: An explanation of a theorem that governs all distributed computer systems. What it explains: The CAP theorem and why distributed systems must choose between consistency and availability. Why read it: To understand why no distributed database can be fully consistent and fully available at the same time.

What the CAP Theorem Is

The CAP theorem was proposed by Eric Brewer (born 1965), a computer scientist at UC Berkeley and Google, in a keynote address in 2000. It was formally proved in 2002 by Seth Gilbert and Nancy Lynch of MIT.

CAP names three properties of a distributed data store (a system where data is stored across multiple connected computers):

• Consistency (C): Every read receives the most recent write. All nodes (individual computers in the system) see the same data at the same time.
• Availability (A): Every request receives a non-error response. The system responds to every query, even if the data is not the most recent.
• Partition tolerance (P): The system continues to operate despite network partitions — situations where messages between nodes are lost or delayed.

The theorem states: in a distributed data store, you can guarantee at most two of the three properties.

Why It Matters

The theorem matters because network partitions (P) are inevitable in real systems. Cables fail. Routers reboot. Data centers lose connectivity. If a partition occurs, the system must choose: either preserve consistency (C) by refusing some requests, or preserve availability (A) by serving possibly stale data.

This is not a technological limitation that better engineering will solve. It is a logical limit proved by the Gilbert-Lynch proof.

The Key Idea: The Trade-off

If the network partitions (P), you must choose between consistency (C) and availability (A). You cannot have both.

• Choose CP: The system blocks writes until consistency is restored. Some requests fail. The system is consistent but not fully available.
• Choose AP: The system accepts all writes and serves all reads. Some responses contain stale data. The system is available but not fully consistent.

Most real-world distributed systems choose AP and handle consistency asynchronously (in the background). They accept that different nodes may see different data for a short period, and they resolve differences later.

What Brewer Got Right

• Identified the three properties that matter in distributed systems design.
• Showed that the choice between them is a logical necessity, not an engineering failure.
• Forced system designers to be explicit about which properties they prioritize.

What Brewer Got Wrong or Left Unfinished

• The theorem is often stated as "pick two of three," which implies you could build a system that is CA (consistent and available) but not partition-tolerant. In practice, network partitions are unavoidable, so every real system must tolerate partitions. The actual choice is between CP and AP, not among all three pairs.
• The theorem does not quantify the trade-off. It does not say how much consistency you lose for a given gain in availability.
• Brewer later noted that the theorem describes a binary at partition time, but real systems operate on a spectrum between strong consistency and eventual consistency.

How It Connects to Other Ideas

• ACID vs. BASE: ACID (Atomicity, Consistency, Isolation, Durability) describes the properties of traditional relational databases, which prioritize consistency. BASE (Basically Available, Soft state, Eventual consistency) describes the properties of many distributed databases, which prioritize availability. CAP explains why BASE exists.
• Consensus protocols (Paxos, Raft): These algorithms achieve strong consistency in distributed systems by requiring a majority of nodes to agree before committing a write. They implement the CP choice. CAP explains why these protocols are necessary and why they add latency.

Sources

• Brewer, Eric. "Towards Robust Distributed Systems" (keynote, PODC 2000).
• Gilbert, Seth, and Nancy Lynch. "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services." ACM SIGACT News 33, no. 2 (2002): 51–59.

---

Up the tree

• OIP root — protocol root, zero-context entry
• Thinker Reference hub — full hierarchy map
• Thinkers shelf — siblings on this shelf
• Voxel graph article — how pages link as voxels
• Self-describing protocol

Related on this shelf

• Alan Kay — The Big Idea Is Messaging
• Alfred North Whitehead — Process and Reality
• J.L. Austin and John Searle — Speech Acts
• Barbara Liskov — Abstract Data Types and Distributed Consensus
• Bram Cohen — BitTorrent and Content-Addressed Protocol Design
• Butler Lampson — Protection and Access Control
• Carl Hewitt — The Actor Model
• Charles Sanders Peirce — Signs, Abduction, and Pragmatism

Machine surfaces

• Public page: https://miscsubjects.com/a/thinker-eric-brewer
• JSON article: https://miscsubjects.com/api/articles/thinker-eric-brewer
• OIP ask: https://miscsubjects.com/api/dispatch?ask=Eric%20Brewer%20%E2%80%94%20The%20CAP%20Theorem