Course contentsShow
← System Design
Lesson 491 of 1,91914. CAP TheoremFree lesson

CAP Theorem's Original Paper

Eric Brewer's conjecture from 2000, later formally proven by Gilbert and Lynch in 2002 for atomic read/write operations.

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.