CAP Theorem & Consistency Models

Table of Contents#

1. Why This Is the "Hard Theory" Interview Topic
2. The Setup: Why Distributed Systems Need This At All
3. The CAP Theorem, in Plain English
4. Consistency, Availability, and Partition Tolerance — One at a Time
5. Why You Can't Actually "Choose" All Three
6. The Most Common Misunderstanding About CAP
7. CP Systems — Consistency Over Availability
8. AP Systems — Availability Over Consistency
9. Real Systems Mapped to CAP
10. PACELC — CAP's More Complete Sequel
11. Consistency Models, From Strongest to Weakest
12. Strong Consistency
13. Eventual Consistency
14. Causal Consistency
15. Read-Your-Writes and Session Consistency
16. Choosing a Consistency Model — A Practical Framework
17. Quorum-Based Systems — Tuning the Tradeoff Yourself
18. How This Connects Back to Parts 1 and 2
19. Common Mistakes
20. Worked Practice Problems
21. Summary

---

Why This Is the "Hard Theory" Interview Topic#

Everything in Parts 1 and 2 was fairly intuitive once explained — "have backups," "don't wait forever," "stop calling something that's broken." This part is different: it's the one piece of genuine theory that shows up again and again in SRE and backend interviews, and it's the one most candidates fumble, usually because they memorized a slogan ("pick two of three") without understanding why it's true.

The good news: the actual idea, once you strip away the jargon, is simple enough to explain to a friend over coffee. Let's build it up from scratch instead of just stating the rule.

---

The Setup: Why Distributed Systems Need This At All#

Imagine you have a single database on a single machine. There's no "network" between different copies of your data — there's just one copy, in one place. Simple.

Now imagine you have two copies of that database, on two different machines, in two different data centers, so that if one data center loses power, the other keeps serving traffic (this is exactly the redundancy idea from Part 1). Now there's a network connection between those two machines, keeping them in sync.

Diagram

Here's the uncomfortable question that CAP theorem is entirely about: what happens if that network link between the two data centers breaks?

Diagram

Now A and B can't talk to each other. But users are still sending requests to both of them (because from the outside, both still look like working databases). This exact situation — a network split between parts of a distributed system that are otherwise both still running — is called a network partition.

---

The CAP Theorem, in Plain English#

The CAP theorem, first stated by Eric Brewer in 2000 (and formally proven by Seth Gilbert and Nancy Lynch in 2002), says: when a network partition happens, you can only keep one of these two promises — not both:

Diagram

That's the whole theorem. Consistency, Availability, Partition tolerance — the famous claim is you can only have two of the three. But here's the nuance almost everyone glosses over, covered fully in the next section: in any real distributed system (more than one machine, connected by a network), partitions are not optional — they will eventually happen. So the real, practical choice isn't "pick 2 of 3" — it's "when a partition happens, do you favor Consistency or Availability?"

---

Consistency, Availability, and Partition Tolerance — One at a Time#

Consistency (C)#

Every read gets the most recent write, or an error — never stale or incorrect data. In plain terms: every copy of the data agrees, all the time, from the outside observer's point of view.

Diagram

Availability (A)#

Every request gets a response — not an error, not a hang — even if it can't guarantee the response is the absolute latest data.

Diagram

Partition Tolerance (P)#

The system continues to function (in some form) even when network messages between nodes are lost or delayed.

Diagram

---

Why You Can't Actually "Choose" All Three#

Here's the key insight, walked through concretely instead of just asserted.

Diagram

This is the entire theorem in one picture. During a partition, Copy B is physically unable to check with Copy A (that's what "partition" means — they can't talk). So B has exactly two choices: answer anyway (risking staleness = sacrificing Consistency) or refuse to answer (sacrificing Availability). There is no third option that gives you both, because the one thing that would let B safely do both — asking A "hey, are you sure I have the latest data?" — is precisely the thing a network partition prevents.

Why "Partition Tolerance" isn't really a choice at all: some early explanations of CAP frame it as "pick any 2 of C, A, P" — but in a real distributed system spanning more than one machine, network partitions are not optional; they will happen eventually (a cable gets cut, a router fails, a data center loses connectivity). So "not tolerating partitions" isn't a real option for any system that actually has more than one node — it would mean the system simply stops working entirely the moment a partition occurs, which is rarely acceptable. This is why, in practice, the real-world choice is always CP vs. AP, not "which 2 of 3."

---

The Most Common Misunderstanding About CAP#

This deserves its own spotlight because it's exactly what separates a candidate who memorized the slogan from one who actually understands it.

Diagram

Say this explicitly in an interview if CAP comes up: "CAP isn't a permanent tax you pay all the time — it's specifically about what happens during a network partition, which is hopefully rare. The rest of the time, a good system delivers both consistency and availability. The 'C vs A' choice is really about what your system's fallback behavior is when things go wrong, not its normal, everyday behavior."

---

CP Systems — Consistency Over Availability#

A CP system chooses to refuse requests (become unavailable) rather than ever risk giving out stale or conflicting data.

Diagram

When this makes sense: anywhere being wrong is worse than being unavailable. Classic example: a banking system checking your account balance before allowing a withdrawal — showing a stale (too-high) balance and letting you overdraw is a much worse outcome than the ATM saying "service temporarily unavailable, try again."

Real examples: traditional relational databases configured for strong consistency (a single-primary Postgres/MySQL setup, where writes go only to the primary), HBase, MongoDB (in its default configuration), ZooKeeper, etcd.

---

AP Systems — Availability Over Consistency#

An AP system chooses to keep answering requests, even if it means some answers might be slightly stale or, in rarer cases, that two copies temporarily disagree.

Diagram

When this makes sense: anywhere being unavailable is worse than being briefly stale. Classic example: a shopping cart — if the system can't immediately confirm the absolute latest state of your cart during a network hiccup, it's usually much better to show you a slightly-stale-but-probably-fine cart than to refuse to load the page at all. Another classic: a social media "like count" — nobody is harmed if it's off by a few for a moment.

Real examples: Cassandra, DynamoDB (in its default, eventually-consistent read mode), Riak, CouchDB.

---

Real Systems Mapped to CAP#

A great interview answer: naming 2-3 of these systems and correctly categorizing them (with the reasoning, not just the label) is much stronger than reciting CAP theorem's definition alone.

---

PACELC — CAP's More Complete Sequel#

A genuinely advanced point that will impress an interviewer if raised naturally: CAP theorem only describes tradeoffs during a partition. But there's a second, equally real tradeoff that exists even when there's no partition at all — and CAP theorem says nothing about it. This gap is exactly what PACELC (coined by Daniel Abadi in 2010) fills in.

Diagram

The "Else" part is the genuinely new insight: even with a perfectly healthy network and no partition at all, there's still a real tradeoff — if you want every read to reflect the absolute latest write (strong consistency), you generally have to wait for confirmation from other replicas before responding, which costs latency. If you want the fastest possible response (low latency), you accept the small risk of returning slightly stale data.

Why this matters practically: it explains something CAP alone can't — why a system like DynamoDB offers both "eventually consistent reads" (fast) and "strongly consistent reads" (slower) as an explicit choice you make on every single query, completely independent of whether a partition is currently happening. That's PACELC's Latency-vs-Consistency tradeoff in action, in normal day-to-day operation.

A strong, senior-level interview line: "CAP only tells you what happens during the rare event of a network partition. PACELC captures the more common, everyday tradeoff — even with a perfectly healthy network, you still have to choose between waiting for strong consistency and accepting the latency cost, or responding fast and accepting some staleness risk. Systems like DynamoDB expose this choice directly to the caller, on every query."

---

Consistency Models, From Strongest to Weakest#

CAP theorem treats "Consistency" as one single concept, but in real systems, consistency isn't just on-or-off — it's a spectrum, and knowing where different systems sit on that spectrum is high-value interview knowledge.

Diagram

---

Strong Consistency#

Every read reflects the absolute latest write, everywhere, immediately, with no exceptions — as if there were really only one single copy of the data, even though there are actually many.

Diagram

Cost: requires coordination (nodes talking to each other to confirm agreement) before responding, which adds latency, and — per CAP — can require refusing requests during a partition.

Use when: correctness is more important than speed or availability — bank balances, inventory counts that must never oversell, distributed locks/leader election.

---

Eventual Consistency#

If no new writes happen, all copies will eventually converge to the same value — but there's no guarantee about exactly when, and in the meantime, different reads might return different (all validly-written-at-some-point, just not yet synced) answers.

Diagram

Cost: callers must tolerate the possibility of seeing stale data for some (usually short) window of time.

Use when: speed and availability matter more than perfect real-time accuracy — social media feeds, "like" counts, product view counts, DNS records, most caching layers.

---

Causal Consistency#

A middle ground: unrelated writes can be seen in any order (loose, like eventual consistency), but writes that are causally related (one clearly happened because of, or after, another) are always seen in the correct order by everyone.

Diagram

Analogy: imagine a group chat where messages can arrive slightly out of order across different people's phones — that's fine for unrelated messages, but it would be genuinely confusing if someone saw a reply to a message before they could see the original message it was replying to. Causal consistency specifically prevents that kind of confusing "effect before cause" ordering, while still not requiring the full expense of strong consistency for everything else.

Use when: comment threads, chat applications, collaborative editing — situations where order matters for related actions, but perfect global real-time sync isn't required.

---

Read-Your-Writes and Session Consistency#

A very practical, narrower guarantee: you will always see your own writes, even if you might briefly see stale data from other users' writes.

Diagram

Why this matters practically: it's a common, pragmatic compromise — full strong consistency for everyone is expensive, but "at minimum, never show me my own stale data" is both cheap to implement (often just: route a user's reads to whichever replica handled their most recent write, or briefly to the primary) and covers the single most jarring, common complaint users have about eventually-consistent systems ("I just updated this, why does it still show the old value?!").

Session consistency is essentially "read-your-writes, scoped to one continuous user session" — a common practical target for many real-world systems (e.g., serve a user's reads from the primary/most-recent-replica for a short window right after they write something, then fall back to normal eventually-consistent reads).

---

Choosing a Consistency Model — A Practical Framework#

Diagram

Interview-ready summary: "I don't pick a consistency model in the abstract — I pick it by asking what actually breaks if a user sees stale data for a moment. A bank balance affecting a withdrawal decision needs strong consistency. A 'like' count or a product view counter can be eventually consistent with zero real harm. Most real applications end up using a mix of both, chosen per use case, not one single global choice for the entire system."

---

Quorum-Based Systems — Tuning the Tradeoff Yourself#

Some systems (Cassandra and DynamoDB are the classic examples) don't force you into one fixed point on the consistency spectrum — they let you tune it per-request, using a concept called quorum.

The idea: with N total replicas of your data, you can require that a write succeed on at least W replicas before confirming success, and require a read to check at least R replicas (returning the most recent value among them) before answering.

Diagram

The magic rule: if W + R > N, you're mathematically guaranteed that every read overlaps with the most recent write on at least one replica — giving you strong consistency, without needing all N replicas to participate in every single operation.

Diagram

Why this is a great interview topic to bring up: it shows you understand that "consistency vs. availability" isn't always a fixed, binary architectural decision baked in at design time — some real systems let you dial the tradeoff per individual operation, choosing stronger consistency for operations that need it (e.g., checking inventory before a purchase) and weaker consistency for operations that don't (e.g., logging a page view), all within the same database cluster.

---

How This Connects Back to Parts 1 and 2#

Tying the whole three-part series together:

Diagram

This is the single most valuable synthesis point you can make in an interview if these topics come up together: "Part 1's active-active pattern is exactly what creates the CAP theorem's dilemma in the first place — the moment you have multiple simultaneously-writable copies of data, you've signed up for the C-vs-A tradeoff during a partition. And Part 2's resilience patterns — falling back to cached/local data, degrading gracefully instead of hanging — are literally the implementation of choosing Availability over Consistency when a partition happens."

---

Common Mistakes#

---

Worked Practice Problems#

Problem 1: An interviewer asks: "Our checkout service uses Cassandra (an AP system). During a network partition, a customer's 'add to cart' request succeeds on one replica, but a moment later, a 'view cart' request on a different, partitioned-off replica shows the cart as empty. Is this a bug?"

Answer: Not necessarily a bug — it's the expected, documented tradeoff of choosing an AP system: during a partition, different replicas can temporarily disagree, and Cassandra chose to keep answering requests (Availability) rather than refuse them (Consistency). Whether this is acceptable depends on the use case — for a shopping cart, this is often tolerable (the discrepancy resolves once the partition heals and the copies sync back up), but if this were, say, a "confirm payment received" check, the team should reconsider using stronger consistency (higher W+R quorum, or a CP-style read) specifically for that particular operation.

Problem 2: A system has N=5 replicas. The team wants fast reads and is willing to accept slightly slower writes to guarantee strong consistency. What W and R values would you recommend, and why?

Answer: Since fast reads matter most, keep R low (e.g., R=1 — read from just one replica, fast). To still guarantee W+R > N (5), that means W must be at least 5 (W=5, R=1 → 5+1=6 > 5). This means every write must be confirmed by all 5 replicas before succeeding — slower and less available on writes (any one replica being down blocks all writes), but reads stay fast and, combined with W=5, are guaranteed to always see the latest data (since every replica has every write by the time it succeeds). This directly trades write latency/availability for read speed with guaranteed consistency — exactly matching the stated goal.

Problem 3: Explain, without using the words "Consistency" or "Availability," why a network partition forces a genuine tradeoff rather than being solvable with "just better engineering."

Answer: When two parts of a system can't send messages to each other (that's what a partition literally means), a node on one side has no way to know whether the other side has received a more recent update. It has exactly two choices: respond anyway using only the information it currently has (risking that the information is out of date), or refuse to respond until it can somehow confirm with the other side (which it fundamentally cannot do while the partition lasts). No amount of clever engineering can let a node truthfully answer "yes, this is definitely the latest data" while it's physically unable to check — the tradeoff is a logical necessity of the situation, not an engineering shortfall.

---

Summary#

• CAP theorem: during a network partition, a distributed system must choose between Consistency (refuse to answer unless certain the answer is correct) and Availability (always answer, even if the answer might be stale) — it cannot guarantee both at the same time, during the partition.
• Partition tolerance isn't really an optional choice for any real multi-node system — partitions will eventually happen, so the practical, everyday framing is "CP vs. AP," not "pick any 2 of 3."
• The tradeoff only applies during an actual partition — a well-designed system is both consistent and available the rest of the time. Don't describe CAP as a permanent, always-on tax.
• PACELC extends this: even with a perfectly healthy network (no partition), there's still a Latency vs. Consistency tradeoff in normal, everyday operation — systems like DynamoDB expose this choice explicitly, per query.
• Consistency itself is a spectrum, not a binary: strong (always latest) → causal (related events stay ordered) → read-your-writes (you always see your own changes) → eventual (converges eventually, no timing guarantee).
• Quorum-based systems (W + R > N) let you tune the consistency/availability/latency tradeoff per operation, rather than committing to one fixed choice for an entire system.
• This whole topic explains why Part 1's active-active database patterns are genuinely hard, and explains what Part 2's resilience patterns (fallbacks, graceful degradation) are actually implementing when a system chooses Availability during a partition.

This completes the Reliability & Architecture Patterns series. See questions.md in this folder for the full interview question bank covering all three parts.