CAP Theorem

1The Three Properties, Defined Precisely

CAP theorem states that a distributed data system can provide at most two of the following three guarantees at the same time, during a network partition:

• Consistency (C) — every read receives the most recent write, or an error. Every node that responds to a request agrees on the current value; there is no such thing as one node returning old data while another returns new data.
• Availability (A) — every request to a non-failing node receives a response (not an error, not a timeout) — though not necessarily the most recent write.
• Partition tolerance (P) — the system continues to operate despite an arbitrary number of messages being dropped or delayed between nodes (a network partition: some nodes can't talk to some other nodes for a while).

The precise, easy-to-misstate claim: you cannot have all three simultaneously once a partition actually occurs. Outside of a partition (the normal, healthy case), a well-built system can absolutely offer both consistency and availability — CAP is specifically a statement about what has to give during a partition, not a permanent, constant tradeoff.

2Why Partition Tolerance Isn't Really an Optional Choice

CAP is often (mis)taught as "pick any 2 of C, A, P" — as if P were a design choice on equal footing with C and A. In a real distributed system, spanning more than one machine, over a real network, partitions will happen — a switch fails, a cable gets cut, a datacenter loses connectivity, a process pauses long enough for peers to consider it unreachable. A system that "chooses" not to tolerate partitions isn't choosing CA over CP/AP — it's simply going to fail completely (become fully unavailable, everywhere) the moment a partition occurs, because it has no defined behavior for that case at all.

This reframes the real question CAP forces onto every distributed system's design: given that a partition WILL eventually happen, when it does, do you sacrifice Consistency or Availability? That's a genuine design choice — CP or AP — made concretely, node by node, for the duration of the partition.

3CP: Choosing Consistency, Sacrificing Availability During a Partition

A CP system, when partitioned, refuses to serve requests it can't guarantee are consistent — some nodes go unavailable (return errors/timeouts) rather than risk serving stale or conflicting data:

Cluster of 3 nodes, partitioned into [Node A] | [Node B, Node C]

A CP system:
  - Node A, isolated and unable to confirm it has the latest write, REFUSES
    reads/writes rather than risk serving stale data -> Node A is UNAVAILABLE
  - Nodes B and C, still able to talk to each other, may continue serving
    (if they still have a majority -- see quorum-based systems)

Concrete examples: a strongly-consistent configuration store like etcd or ZooKeeper (used specifically because callers need a guaranteed-current value, e.g. for leader election — serving a stale "who is the leader" answer to two different callers would be actively dangerous) is built CP. A traditional single-primary relational database, when its primary is unreachable, typically refuses writes rather than let a secondary accept writes it can't guarantee are consistent with the primary.

4AP: Choosing Availability, Sacrificing (Strict) Consistency During a Partition

An AP system keeps serving requests on both sides of a partition, accepting that the two sides may temporarily disagree:

Same partition: [Node A] | [Node B, Node C]

An AP system:
  - Node A keeps serving reads AND writes using whatever data it has locally
  - Nodes B/C also keep serving reads and writes
  - If a client wrote to Node A during the partition, and another client
    reads from Node B, it may get a DIFFERENT (older, or conflicting) value
  - Once the partition heals, the system must RECONCILE the divergent
    writes (last-write-wins, vector clocks, application-level merge logic,
    etc. -- how reconciliation works is implementation-specific)

Concrete examples: Cassandra and DynamoDB are classically AP-oriented (configurable, but designed to keep serving during a partition, favoring uptime), because for their common use cases (a shopping cart, a metrics store, a social feed) briefly serving slightly-stale data to keep the system responsive is a better tradeoff than an outage. A CDN cache is AP by nature — an edge node cut off from origin keeps serving its (possibly stale) cached content rather than erroring.

5This Is a Per-System (Often Per-Operation) Choice, Not a Universal Ranking

Neither CP nor AP is "more correct" in the abstract — the right choice depends entirely on what an inconsistent-but-available response would cost versus what an unavailable response would cost, for that specific piece of data:

Many real systems aren't purely one or the other everywhere — they make this choice per operation or per data type, using a strongly-consistent store for account balances and an eventually-consistent one for view counters, even within the same product.

6PACELC: A Refinement Worth Knowing

CAP technically only describes behavior during a partition — it says nothing about the consistency/latency tradeoff a system makes when there is no partition, which is the vast majority of the time. PACELC extends the idea: if Partitioned, choose Availability or Consistency; Else (normal operation), choose Latency or Consistency. Even with no partition at all, a strongly consistent system typically pays a latency cost (coordinating with other replicas before acknowledging a write) that an eventually-consistent system avoids — so the C-vs-something tradeoff doesn't fully disappear even in the healthy case, it just becomes a latency tradeoff instead of an availability one.

⚠️ Common Pitfalls

1. Treating "pick 2 of 3" as a literal, always-available menu — partition tolerance isn't optional in a real networked system; the real, constant choice is CP vs AP for what happens when (not if) a partition occurs.
2. Assuming a system is CP or AP everywhere, uniformly — many real systems make the choice per data type or per operation (strongly-consistent account balances, eventually-consistent view counters, in the same product).
3. Forgetting CAP only describes partition behavior — during normal, healthy operation, a well-built system can offer both consistency and availability; conflating "CP system" with "always slow or unavailable" misreads the theorem.
4. Ignoring the reconciliation problem in an AP design — choosing availability during a partition defers, but doesn't eliminate, the need to actually reconcile divergent writes once the partition heals; a design that hand-waves this isn't actually finished.
5. Not considering PACELC's latency dimension — evaluating a database purely on its partition-time CAP category while ignoring its normal-operation consistency/latency tradeoff misses a large part of the real-world cost difference between systems.

📋 Quick Reference

C = Consistency: every read sees the latest write (or an error) -- all nodes agree
A = Availability: every request to a healthy node gets a non-error response
P = Partition tolerance: system keeps functioning despite dropped/delayed messages

P is NOT optional in a real network -- partitions WILL happen
Real choice: when partitioned, sacrifice C (go CP) or sacrifice A (go AP)?

CP examples: etcd, ZooKeeper, traditional single-primary RDBMS (refuses writes when isolated)
AP examples: Cassandra, DynamoDB (configurable), CDN edge caches (serve stale rather than error)

PACELC: if Partitioned -> Availability or Consistency; Else -> Latency or Consistency
        (the C-vs-something tradeoff exists even with NO partition, as a latency cost)

🎤 Interview Q&A

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

✅ Check yourself

Source: dist_cap_theorem_theory.md · generated by tools/build_lessons.py