CAP Theorem's Original Paper
You'll learn about the historical origins of the CAP Theorem and how it evolved from conjecture to proven theory.
Eric Brewer's Conjecture (2000)
In 2000, computer scientist Eric Brewer presented a conjecture at the PODC (Principles of Distributed Computing) symposium. He proposed that distributed systems fundamentally cannot simultaneously guarantee all three of:
- Consistency (C)
- Availability (A)
- Partition tolerance (P)
This was initially an observation based on real-world distributed systems experience at Inktomi (a search engine company), not a mathematical proof. Brewer noticed patterns in how systems behaved under network failures and framed this as a design principle.
The Formal Proof (2002)
Two years later, MIT researchers Seth Gilbert and Nancy Lynch published a formal proof of Brewer's conjecture in their paper "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services."
Key limitations of the proof:
- Applied specifically to atomic read/write operations (single-object consistency)
- Focused on asynchronous networks with potential message loss
- Did not cover complex transactions, eventual consistency, or real-time guarantees
This proof transformed CAP from an intuitive guideline into a mathematically rigorous theorem, cementing its place in distributed systems theory.
Why This Matters
Understanding CAP's origins helps you recognize its scope and limitations. The theorem applies to a specific model of distributed computation, not every possible scenario. Many modern interpretations extend beyond what Gilbert and Lynch proved.
Key Takeaway: CAP Theorem began as Eric Brewer's 2000 conjecture based on practical experience and was formally proven in 2002 by Gilbert and Lynch for atomic read/write operations, establishing the mathematical foundation for understanding distributed system tradeoffs.