Phase 3 · Chapter 1

CAP Theorem & Consistency Models

Not the definition — the physical reason why you can't have everything

What this chapter does to you: CAP theorem is the most cited and most misunderstood theorem in distributed systems. Engineers quote it to justify design decisions they don't actually understand. After this chapter, you will understand what CAP means at the physical level — why network partitions are inevitable, what you actually give up during one, and why the real tradeoff is not CAP but PACELC. You will also understand the full consistency spectrum — from strict serializability to eventual consistency — and know exactly which model each system you'll design in Phase 5 uses.

Part 1: The Physical Setup — Why This Problem Exists

In Phase 1, you learned that a network request takes ~150ms from India to Germany. In Phase 2, you learned that Postgres uses WAL for crash recovery. In Phase 2, you also added replicas and shards — and saw that copies of data can disagree. From here on, every system has multiple servers, Redis clusters, and DB replicas.

Every time you have more than one machine, you have a distributed system. And every distributed system faces one unavoidable physical reality:

Networks fail.

Not occasionally. Constantly, at scale.

• A network cable is damaged in a data centre
• A router drops packets under high load
• A cloud provider's availability zone goes down
• A BGP routing misconfiguration splits the internet for minutes

When a network failure splits your cluster of machines into two groups that cannot communicate with each other — that is called a network partition.

The question is: what does your system do during a partition? This is what CAP theorem answers.

Part 2: CAP — The Three Properties

C — Consistency (in CAP's definition): Every read receives the most recent write or an error. If you write x = 5 and then immediately read x, you get 5. Always.

⚠️ Important: CAP's "consistency" is not the C in ACID. ACID consistency = constraints are never violated (foreign keys, NOT NULL). CAP consistency = every node returns the same, most-recent value. These are different concepts with the same word. This confusion has misled thousands of engineers.

A — Availability: Every request receives a response — not an error, not a timeout. The system always responds, even if some nodes are down.

P — Partition Tolerance: The system continues operating even when network messages between nodes are lost or delayed.

The Theorem

You cannot have all three simultaneously in a distributed system.

During a network partition, you must choose between C and A. You cannot have both. This is mathematically proven.

But here's the thing most people miss:

P is not optional. Networks partition. You cannot build a system that simply never experiences network partitions. So the real choice is:

When a partition happens — do you sacrifice C or A?

• CP system: During partition, stop serving requests rather than serve stale data. Consistent but unavailable during the partition.
• AP system: During partition, keep serving requests even if data might be stale. Available but possibly inconsistent during the partition.

Try it before reading the argument. Each tab asks you to predict first — CP, AP with last-write-wins, and tuning R and W.

Part 3: The Physical Argument — Why You Can't Have Both

Let's make this concrete. Two database nodes: Node A and Node B. They replicate data between each other.

Node A ────────────── Node B
       replication

A client writes x = 5 to Node A. Node A sends this update to Node B via the network.

Normal operation:

Now another client reads from Node B. Should it return 5? Yes — replication already happened. Consistent. ✓

During a partition:

The network link breaks. Node A and Node B cannot communicate.

Another client reads from Node B. Node B hasn't received the update. x is still whatever it was before.

Now what do you do?

Option 1: Return stale x (prioritise A over C) Node B serves the old value. Client gets wrong data. Inconsistent. But: the system responded. Available.

Option 2: Return an error (prioritise C over A) Node B knows it can't guarantee freshness (it can't reach Node A to verify). It refuses to respond until the partition heals. But: the system didn't respond. Unavailable.

There is no third option. Physics does not allow it. This is not a software limitation. It is a consequence of the speed of light and the unreliability of networks.

Part 4: Real Systems — What They Actually Choose

Postgres (CP — with caveats)

In a primary-replica setup:

• All writes go to primary
• Replicas serve reads
• During a partition: if primary goes down and you promote a replica, any writes that hadn't replicated yet are lost
• If you use synchronous replication: writes block until replica confirms. During partition: writes block indefinitely. CP.
• If you use asynchronous replication (default): writes acknowledged before replica confirms. During partition: replica serves stale data. More AP.

Postgres gives you a knob (synchronous_commit) to choose your tradeoff.

Redis Cluster (AP)

Redis Cluster uses async replication between primary and replicas. During a partition: the side with the primary keeps accepting writes. The side with only replicas may elect a new primary (split brain). When partition heals: one side's writes are lost (the side that diverged).

Redis chooses availability. It keeps working. It may lose some writes. This is why you don't store financial data in Redis without careful design.

Zookeeper / etcd (CP)

Used for leader election, configuration, and coordination. Both run a majority-based consensus protocol: etcd uses Raft (Chapter 3 of this phase); ZooKeeper uses ZAB (ZooKeeper Atomic Broadcast), a different protocol with the same majority-quorum idea. During a partition: the minority side stops accepting writes until it can communicate with the majority. Unavailable during partition, but consistent when available.

Cassandra (AP with tunable consistency)

Cassandra lets you choose per-query:

• CONSISTENCY ONE: return data from any single replica. Always available, may be stale.
• CONSISTENCY QUORUM: wait for a majority of replicas. Slower, more consistent.
• CONSISTENCY ALL: wait for every replica. Consistent, least available.

This is the "tunable consistency" model — you pick your tradeoff per operation.

The rule that makes it work: R + W > N. With N replicas, if a write waits for W of them and a read asks R of them, and R + W > N, the read set and write set must overlap in at least one replica — so the read sees the latest write. With N = 3: QUORUM writes (W = 2) + QUORUM reads (R = 2) → 4 > 3, overlap guaranteed. QUORUM writes + ONE reads → 3, not > 3, stale reads possible.

A read of a product page? ONE. A user's profile they just edited? QUORUM writes + QUORUM reads.

What quorums do NOT give you: transactions. A bank transfer is "debit A and credit B, atomically, without overdrawing" — that needs multi-row atomicity and isolation. Quorum consistency only makes a single read see a single latest write; concurrent writes to the same cell are still resolved by last-write-wins timestamps. Cassandra's lightweight transactions (IF ..., Paxos-based) give compare-and-set on one partition only. Money belongs in an ACID database (Postgres, Spanner, CockroachDB); saying "Cassandra with QUORUM" for a transfer will draw immediate pushback in an interview.

Part 5: PACELC — The More Useful Framework

CAP only talks about what happens during a partition. But partitions are rare. Most of the time, your network is fine. What happens then?

PACELC extends CAP:

If Partition: choose between A (availability) and C (consistency)
Else (normal operation): choose between L (latency) and C (consistency)

During normal operation, the tradeoff is:

• Want low latency? Return data from the nearest replica immediately (may be slightly stale).
• Want consistency? Read from all replicas, confirm they agree (higher latency).

PACELC characterisations of real systems:

System      PA/EL  → Available on partition, low latency normally
  Cassandra (default), DynamoDB, CouchDB

System      PA/EC  → Available on partition, consistent normally
  (rare — most AP systems trade latency too)

System      PC/EL  → Consistent on partition, low latency normally
  (impossible — consistency requires coordination = latency)

System      PC/EC  → Consistent on partition, consistent normally
  Zookeeper, etcd, Postgres (sync replication)

Most real systems sit somewhere on the PA/EL ↔ PC/EC spectrum. You tune where you sit based on your requirements.

Part 6: Consistency Models — The Full Spectrum

CAP has two consistency positions: consistent and not consistent. Reality has many levels in between. Know the full spectrum.

Strict Serializability (Linearizability)

The strongest guarantee. Every operation appears to take effect at a single point in time between its start and completion.

Reads always return the most recent write. Writes are globally ordered. From any client, anywhere, at any time — everyone sees the same history.

Physical cost: Requires global coordination on every operation. Every write must be confirmed by all nodes before returning. Latency = slowest node. Speed of light across continents = hundreds of ms.

Used by: Spanner (Google's global SQL DB), etcd, Zookeeper. For: financial transactions, leader election, anything where wrong = catastrophic.

Sequential Consistency

Operations execute in some global sequential order, and every client sees that same order. Each process's operations appear in the order that process issued them. What it drops compared to linearizability is real-time: the agreed order does not have to match wall-clock time (a write that finished before your read started may still appear after it).

Slightly weaker than linearizability but still very strong. Rarely used directly — mostly a theoretical model.

Causal Consistency

Causally related operations appear in the same order to all nodes. Unrelated operations may appear in different orders.

A writes x=1
A tells B "I wrote x=1"
B reads x → must see x=1 (causally related)

C reads x without knowing about A's write → may see old value (not causally related)

Used by: MongoDB sessions (causal consistency mode), some versions of Dynamo. For: social feeds, collaborative tools where causality matters but global order doesn't.

Eventual Consistency

If no new updates are made to an object, all reads will eventually return the last updated value. "Eventually" has no time bound.

In practice: replicas sync within milliseconds to seconds. In theory: "eventually" could be hours.

Used by: DynamoDB (default), Cassandra (CONSISTENCY ONE), DNS. For: anything where staleness is tolerable — social likes, view counts, DNS records.

Read-Your-Writes Consistency

A client always sees the effects of its own writes. Other clients may see stale data.

You post a tweet → you immediately see it in your feed ✓
Your friend may take a second to see it (that's fine)

Used by: Most social applications. Sticky sessions (same user always routed to same replica). Token-based sessions where your write goes to the same DB your reads come from.

Monotonic Read Consistency

If you've read a value, you'll never read an older value. You might not see the latest, but you won't go backwards.

You read x=5 → next read returns x=5 or later (x=6, x=7...)
You will never read x=3 after having read x=5

Prevents confusing "time travel" where the same client sees values jumping backwards. Common in read-replica setups.

Part 7: What the Phase 5 Systems Actually Use

Now apply this to the systems you'll design in Phase 5 (a preview — reread this part after them). This is not abstract.

URL Shortener:

• Short URL → long URL mapping: eventual consistency acceptable. A newly created URL might take 1-2 seconds to appear on all replicas. 99.99% of reads are for existing URLs — fully cached.
• Cache invalidation: read-your-writes for the creator. They should see their link work immediately.

Twitter Feed:

• Tweet delivery: eventual consistency. Seeing a tweet 1-2 seconds after posting is fine. The system explicitly states "eventual consistency acceptable" in requirements.
• Like counts: eventual consistency. The write-behind counter in Redis is approximate by design.

WhatsApp Messages:

• Message delivery: causal consistency minimum. "A tells B something" → B's response must come after A's message. Ordering within a conversation is causally required.
• Message storage: durability (WAL in Postgres) — after single tick, message exists. Not a consistency model — a durability model.

Uber Driver Location:

• Location data: eventual consistency (and who cares — data is 4 seconds old anyway).
• Driver reservation (SET NX): linearizable — exactly one rider gets a driver. Redis single-threaded command = linearizable within one Redis instance.

Part 8: The Split Brain Problem

The most dangerous failure mode in distributed systems.

During a network partition, two nodes each think the other is dead. Each promotes itself to primary. Now you have two primaries accepting writes.

Node A ─── [PARTITION] ─── Node B
  ↑                           ↑
primary                     primary
(elected by left side)      (elected by right side)

Writes to Node A diverge from writes to Node B. When the partition heals, both sides have different data. Resolving this is called conflict resolution — and there is no automatically correct answer.

Resolution strategies:

Last-Write-Wins (LWW): Whichever write has a later timestamp wins. Problem: clocks on distributed machines are never perfectly synchronised. "Later" is ambiguous. Used by Cassandra and DynamoDB anyway, with the understanding that rare conflicts are acceptable.

Vector Clocks: Each update carries a version vector — a record of which updates it's aware of. Conflicts are detected precisely. Used by DynamoDB (original), Riak. Problem: conflict resolution must be done by the application, not the DB.

CRDT (Conflict-free Replicated Data Types): Data structures designed so that concurrent updates can always be merged without conflict. A counter that only increments: merge = take the max of each node's count. Used by Redis, collaborative editors (Google Docs).

Quorum writes: Only accept a write if a majority of nodes confirm it. No split brain — a minority partition cannot accept writes. Used by etcd, Zookeeper, Raft-based systems.

Part 9: The Vocabulary Map

Part 10: Practice Problems

Problem 1 (Physical Reasoning): You are designing the payment service for AttemptIQ (premium subscriptions). A user pays. Your primary DB accepts the write. Before the replica acknowledges, the primary crashes. A new primary is elected from the replica.

Under async replication: what happened to the payment record? Under sync replication: what happened to the payment record? Which do you use for payments and why? What does this tell you about the difference between "durability" and "consistency"?

Problem 2 (CAP Classification): Classify each of these systems. For each: CP, AP, or "it depends." Explain your classification using the physical partition scenario.

a) Your Redis session store (async replication, no quorum writes) b) etcd (Raft consensus, quorum required for writes) c) Postgres with synchronous_commit = on and one synchronous replica d) Your BullMQ job queue stored in Redis e) DNS (records propagate globally with TTL-based caching)

Problem 3 (Consistency Model Choice): AttemptIQ has a "streak" feature: answer 7 days in a row to earn a badge. The streak is stored as a counter in Postgres with daily updates.

A student answers a question at 11:59pm. Your primary updates the streak. The replica (used for reads) hasn't synced yet. Student refreshes the page at 12:00:01am. Read goes to replica. The streak shows 6 days, not 7. Badge not shown. Student is angry.

Which consistency model would prevent this? What is the performance cost of implementing it? Is there a cheaper solution that achieves the same user experience without changing consistency levels?

Problem 4 (Split Brain): You run Postgres with one primary and one replica. A network partition splits them. Both sides have clients connected. The replica promotes itself to primary (automatic failover).

Now you have two primaries. Writes flow to both.

When the partition heals:

• How do you detect that a split brain occurred?
• Which side's writes do you keep?
• What happens to the writes you discard?
• How do you prevent this in the first place?

Problem 5 (PACELC — Connect to Phase 5): Come back to this one after the Phase 5 case studies. For each Phase 5 system you designed, identify:

• The PACELC classification (PA/EL, PC/EC, etc.)
• The specific tradeoff that classification enables
• One scenario where the "wrong" classification would have caused a production incident

URL Shortener / Twitter / YouTube / WhatsApp / Uber Five systems. Five answers. This is your synthesis of Phase 5 through the lens of Phase 3.

End of Phase 3, Chapter 1. Estimated reading time: 60-75 minutes. Practice problems: 45-60 minutes. Do not proceed to Chapter 2 until you can explain split brain in one clear paragraph — what it is, how it happens, and three ways to prevent it. Split brain is the distributed systems interview question that separates engineers who understand theory from ones who've built real distributed systems.