The CAP Theorem

Why this matters

Sooner or later you'll read an outage postmortem or a database marketing page that says something like "we chose availability over consistency during the incident." The CAP theorem is what gives that sentence meaning. It's the single most quoted idea in distributed systems — you'll hear it in interviews, design reviews, and conference talks. Half the people who mention it get it slightly wrong. (Not you. Not after this lesson.)

Video: My thoughts on the CAP theorem — Hussein Nasser
Hussein Nasser uses a master-and-replicas story to show how CAP trade-offs shape real architecture decisions.

Picture a restaurant chain

This lesson's running analogy: you run a tiny restaurant chain with two diners across town, sharing one menu. Let's define the CAP properties in diner terms:

• Consistency (C) — Both diners' menu boards always show the same specials. If the lunch special changes, every customer at every diner sees the update at the same time. Nobody orders a dish that was cancelled ten minutes ago.
• Availability (A) — Every diner always seats every customer and takes every order, no exceptions. Nobody is turned away or told to "come back later."
• Partition tolerance (P) — The system keeps working even if the phone line between the two diners is cut and they can't talk to each other.

And here's the thing about that phone line: it will get cut. Cables get chewed, switches die, packets vanish into the void. In the world of networks, the gremlins always strike eventually — usually at 2 a.m., usually right before your launch. A partition is simply two servers that are both alive, both serving customers, but unable to reach each other:

flowchart LR
    C[Client] --> R1[Replica 1]
    C --> R2[Replica 2]
    R1 -. "partition: the phone line is down" .-> R2

Video: CAP Theorem Simplified — ByteByteGo
Gaurav Sen explains each guarantee with simple visuals so the three CAP promises are easy to picture and compare.

The theorem, precisely

In the presence of a network partition, a distributed system must choose between consistency and availability. It cannot provide both.

Why? Go back to the diners. The phone line is cut. A customer at Diner 1 orders the new lunch special. Diner 2 has no idea the special changed — its menu board is stale. Now a customer at Diner 2 asks "what's the special?"

You have exactly two options, and they are both a little awkward:

1. Diner 2 answers with the old special (stale data) — that's availability: everyone gets served, but not everyone gets the truth.
2. Diner 2 refuses to answer until it can confirm the menu — that's consistency: no one gets a wrong answer, but someone gets no answer at all.

There is no third option where the diner serves the correct special without talking to Diner 1. That's the whole theorem. It's less a deep mathematical mystery and more a very obvious dilemma — dressed up in academic clothes.

flowchart TD
    P{Phone line cut?} -->|No| CA[Consistent AND available]
    P -->|Yes| CH{What's the priority?}
    CH -->|The truth matters most| CP[CP: refuse unsafe requests]
    CH -->|Serving customers matters most| AP[AP: keep serving, maybe stale]

Because partitions are inevitable, the "P" in CAP is really non-negotiable for a distributed system — so the practical question is: during a partition, are you CP or AP?

A CP system would rather close the kitchen than serve the wrong special:

sequenceDiagram
    participant Client
    participant NodeA as Reachable Node
    participant NodeB as Unreachable Node

    Client->>NodeA: Write request
    NodeA--xNodeB: Replicate write
    Note over NodeA,NodeB: Partition — the other node can't be reached
    NodeA-->>Client: Reject write (better no answer than a wrong one)

Video: CAP Theorem Explained in 6 Minutes | System Design Interview #11 — Learn with Manoj
Defines consistency, availability, and partition tolerance exactly, then states the real tradeoff clearly.

The thing everyone gets wrong

Here is the misconception to watch for at parties: CAP does not say a system must permanently pick only two of three, like some kind of loyalty program. When the phone line is working — which is most of the time — a system can be both consistent and available. The trade-off only bites during a partition. It's a fire-escape plan, not a personality type.

This is also why later models like PACELC extended CAP: they ask "and even when there's no partition, are you trading consistency for latency?" Because the gremlins are always in the details.

Video: Why Are Distributed Systems so Hard? • Denise Yu • GOTO 2020 — GOTO Conferences
Conference talk clearing up CAP myths, like why partition tolerance is never optional.

Takeaways

1. Partitions are a fact of life, not an edge case — the gremlins always strike eventually, so design for them explicitly.
2. During a partition you must choose: serve everyone with possibly stale data (AP), or serve only what you can guarantee is correct (CP).
3. CAP's C means linearizability — every read sees the latest completed write, as if there were only one copy — which is a different idea from ACID's C (transactions preserve your data's rules). Same word, different meaning entirely.
4. Most real systems are tunable (e.g., Cassandra's quorum reads/writes) rather than strictly CP or AP — CAP is a lens for reasoning, not a rigid checklist.

Go deeper

Want to keep pulling this thread? These talks and tutorials go further than we did here:

• Are you Using CAP Theorem Wrong? — LearnThatStack, YouTube tutorial (~18 min). Why "pick two" is a myth, plus PACELC and CRDTs.
• System design from First Principle[8/15]: CAP Theorem & PACELC — YouTube series. Why partition tolerance isn't a choice; LWW versus vector clocks.
• System Design Basics #15 — The CAP Theorem: Consistency vs. Availability, Honestly — YouTube series (~10 min). A network partition walked through CP versus AP, with PACELC.
• Transactions: myths, surprises and opportunities — Martin Kleppmann, Strange Loop 2015 (~41 min). The closest thing to a definitive CAP treatment — the Designing Data-Intensive Applications author tackles the "much-misunderstood CAP theorem" head on; the CAP discussion sits in the second half, after ACID and weak-isolation race conditions.

Sources & further reading

• Eric A. Brewer, "Towards Robust Distributed Systems" (PODC 2000 keynote) — the original CAP conjecture.
• Seth Gilbert & Nancy Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services," ACM SIGACT News 33(2), 2002 — the formal proof.
• Daniel J. Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design," IEEE Computer 45(2), 2012 — introduces the PACELC extension.
• Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), Ch. 9 — linearizability and consistency in practice.