CAP: You Can’t Have All Three

The CAP theorem (Brewer, proved by Gilbert & Lynch) says that during a network partition, a distributed system must choose between:

• Consistency (C) — every read returns the most recent write; all nodes agree.
• Availability (A) — every request gets a non-error response, even if it may be stale.

Partition tolerance (P) isn’t really a third option — it’s a fact: the network will partition. So the real choice is CP (when partitioned, refuse to serve contradictory data) or AP (when partitioned, keep serving, accepting that two sides may briefly disagree).

The crucial clarifications that kill most misuse of CAP:

1. CAP is about the partitioned state — when the network is healthy you can have both C and A.
2. CAP is about one operation on one datum, not the whole system. You can be CP for account balances and AP for the news feed, simultaneously.
3. “Eventual consistency” and “strong consistency” are models for how the system behaves; CAP describes the boundary of what’s possible during a partition.

CP vs AP in Practice

Choosing CP says: a wrong answer is worse than no answer (bank ledger, locks, leader election). Choosing AP says: an answer now is worth a possibly-stale answer (catalog, feed, sensor data). Most real systems are a blend.

Consistency Models: What “Consistent” Actually Means

The word “consistency” covers a spectrum. From strongest to weakest:

• Linearizability (strongest) — the system behaves as if a single, atomic copy existed: once a write is acknowledged, every subsequent read (from any node) sees it, and operations appear in a real-time order. This is what a single machine’s memory gives you, and what distributed systems usually can’t give you cheaply.
• Sequential consistency — operations appear in some order consistent with each node’s program order (weaker than linearizability; no real-time constraint).
• Causal consistency — causally related operations are seen in order; concurrent ones can be seen in any order.
• Read-your-writes / monotonic reads — pragmatic guarantees: your own writes are visible to you; your reads don’t go backward. These are the guarantees products actually ship with.
• Eventual consistency — if writes stop, all replicas converge to the same value. Eventually — the model says nothing about when, which is why it needs convergence machinery (versioning, conflict resolution, anti-entropy).

Convergence: How Eventual Systems Agree

Eventually-consistent systems must reconcile divergent replicas. Standard tools:

• Last-write-wins (LWW) — highest timestamp wins. Simple, silently loses writes.
• CRDTs (conflict-free replicated data types) — merges are designed to converge: counters (increment-only register merging), registers, sets with add/remove rules. The merge function is a lattice join, so any order of applying ops converges.
• Version vectors — track per-node versions to detect and hand conflicts to the application.

The Dynamo paper (the DNA of Cassandra/DynamoDB) added the famous tunable consistency: reads and writes specify a quorum (N replicas, R reads, W writes). With W + R > N, a read that waits for R nodes is guaranteed to see the newest acknowledged write — strong at your chosen cost; relax the quorum and you accept more staleness for less latency.

The Real-Time Trade

Even with a perfect model, distributed reads cost latency: strong consistency means waiting for the slowest quorum member (or the leader, cross-region). The universal engineering move is to make the trade explicit and per-request: strong consistency for writes that must be instantly visible (account creation, password change), eventual/stale reads for everything else, and caches with TTLs that bound staleness.

Practice Trajectory

1. Classify a bank transfer as CP and a global news feed as AP; write one sentence justifying each.
2. Given N=3, W=2, R=2, prove a read sees the newest write; then show what W=1, R=1 risks.
3. Name three product features that need linearizability and three that tolerate eventual consistency.
4. Describe how a CRDT counter converges where LWW would lose a decrement.
5. Design the consistency policy for a distributed shopping cart: what must be linearizable, what can lag.

When It’s the Right Tool