Key Question

Why can’t you have all three guarantees simultaneously?

Deep Dive

The CAP theorem is provable with a simple thought experiment involving two nodes and a network partition. Let’s walk through it step by step.

Setup

Two nodes, N1 and N2, both maintain a register X (initialized to X=0). They communicate over a network. A partition occurs: all messages between N1 and N2 are dropped.

Before partition:        During partition:
┌─────┐    ┌─────┐      ┌─────┐    ┌─────┐
│ N1  │────│ N2  │      │ N1  │~~~~│ N2  │
│ X=0 │    │ X=0 │      │ X=0 │    │ X=0 │
└─────┘    └─────┘      └─────┘    └─────┘
                        Network cut — no communication

Two clients: Client A (connected to N1) and Client B (connected to N2).

Step 1: Client A writes to N1

Client A sends write X=1 to N1. N1 accepts the write and updates its local state. X is now 1 on N1.

┌─────┐    //    ┌─────┐
│ N1  │~~~~~~~~│ N2  │
│ X=1 │         │ X=0 │  ← N2 can't know about the write
└─────┘         └─────┘
   ↑
Client A: write X=1 (acknowledged)

The partition means N2 never receives the update from N1. N2’s state remains X=0.

Step 2: Client B reads from N2

Client B sends read X to N2. Now we face the dilemma.

Goal: Consistency (C) + Availability (A) + Partition Tolerance (P)

We have P (the partition exists).
Now we need C and A simultaneously.

For Availability (A): 
  N2 must respond to Client B's request (it cannot timeout or error out).

For Consistency (C): 
  N2 must return the latest value, which is X=1.

But N2 CANNOT return X=1 because it doesn't know about the write!
N2 only knows X=0.

The Two Impossible Outcomes

There is NO third option. N2 cannot return X=1 because it doesn’t have it. The partition prevents communication. Therefore, in the presence of a partition, you CANNOT simultaneously satisfy C and A.

Mathematical Summary

The CAP theorem is a proof by contradiction:

1. Assume a system that provides C, A, and P.
2. Introduce a partition (P is tolerated, so the system must continue).
3. Write happens on one side of the partition.
4. Read happens on the other side.
5. For A: the read must return a response.
6. For C: the response must be the latest write.
7. But the latest write is inaccessible across the partition.
8. Contradiction: the read cannot satisfy both C and A.

Therefore, no system can simultaneously provide C, A, and P.

Formal statement by Gilbert and Lynch (2002):

“In a distributed system, it is impossible to guarantee both consistency and availability in the presence of network partitions.”

Note: the theorem doesn’t say “you only get two.” It says “you cannot have all three.” During a partition, you give up either C or A. When there is no partition, you can have both — which is the common case.

What the Proof Does NOT Say

• It doesn’t say you can’t have both C and A MOST of the time (you can, when there’s no partition).
• It doesn’t choose for you which to sacrifice (that’s an application-level decision).
• It doesn’t say systems must choose CP or AP at all times (you can have tunable consistency, like Cassandra).
• It doesn’t apply to single-node systems (no network, no partition).

Check Your Understanding

1. Walk through the CAP proof with three nodes instead of two. Does the result change?
2. In the proof, what happens if N2 waits until the partition heals before responding? Is the system CAP-available?
3. Could N2 return X=1 if it has a cached/pre-negotiated value of X? What assumptions would this require?

The “So What?”

This proof is mathematically airtight — CAP is a theorem, not an opinion. When someone claims their system has “all three,” they’re either misunderstanding the definitions, or they’re describing a single-node system. The proof forces you to accept the fundamental trade-off: when the network fails, you must choose between serving stale data or serving no data. There’s no escape. The only way to “have both” is to design systems where partitions are so unlikely that you’re willing to risk inconsistency or unavailability when they occur.

✏️ Exercises

CAP Theorem — Exercises

Exercise 1

A traditional relational database (e.g., PostgreSQL) with a single primary and two asynchronous replicas experiences a network partition that isolates the primary from the replicas. Is this system CP or CA during the partition? Explain what happens.

Exercise 2

A system claims to provide “eventual consistency.” Can it also claim to provide CAP Consistency (linearizability)? Explain the relationship between eventual consistency and CAP’s C.

Exercise 3

During a network partition, an AP system accepts writes on both sides of the partition. When the partition heals, those writes might conflict. Describe two approaches the system can use to resolve these conflicts and converge.

Exercise 4

A single-machine database with no replication experiences a hard drive failure that prevents any reads or writes. Does CAP apply to this scenario? Why or why not? What about a single-machine database that IS replicated (e.g., a single PostgreSQL instance that streams WAL to a standby)?

Client A writes X=1 (completed)
Client B reads X (starts 1ms after A's write completed)
  - Under CAP-C: B must see X=1
  - Under EC: B might see X=0 (it will eventually converge, maybe after 100ms)

Side A: write X=1 at T=10:00:05
Side B: write X=2 at T=10:00:06

After healing: X=2 wins (T=10:00:06 > 10:00:05)

Side A: write X=1 → version ([A,1])
Side B: write X=2 → version ([B,1])

Neither dominates the other (A doesn't know about B's write, vice versa).
Resolution: both values are kept as siblings: {1, 2}

On next read, the application merges them:
- Shopping cart: union of items {milk} + {eggs} = {milk, eggs}
- Profile name: ask the user which one to keep
- Counter: sum (if appropriate) or max (if appropriate)