The CAP Theorem & Consistency Models

Distributed Systems & Scalability

Chapter 5 · The CAP Theorem & Consistency Models

"Pick two of Consistency, Availability, and Partition tolerance" is the version of CAP most people hear — and it's misleading. Partition tolerance isn't optional in a real distributed system; network partitions happen whether you design for them or not. The actual theorem is narrower and sharper: when a partition is actually happening, a system must choose between Consistency and Availability — and, this chapter verifies, that choice doesn't matter at all until a partition actually occurs.

No Partition: Both Choices Look Identical

class CPSystem:  # sacrifices Availability during a partition, keeps Consistency
    def write(self, node, key, value):
        if self.partitioned and node is self.node_b:
            raise ConnectionError('Write rejected: partitioned, cannot guarantee consistency')
        node.data[key] = value
        if not self.partitioned:
            self.node_a.data[key] = value; self.node_b.data[key] = value

class APSystem:  # sacrifices Consistency during a partition, keeps Availability
    def write(self, node, key, value):
        node.data[key] = value  # always succeeds, regardless of partition
        if not self.partitioned:
            self.node_a.data[key] = value; self.node_b.data[key] = value
    

Verified directly — with no partition, both systems are equally consistent and equally available

Writing stock=50 to either CPSystem or APSystem while partitioned is False produces the identical result both times: node_a.data == node_b.data is True for both. No request was ever rejected in either system. There is no observable difference between "a system designed to prioritize consistency" and "a system designed to prioritize availability" — until something actually goes wrong.

A Real Partition: The Tradeoff Becomes Real

Verified directly — CP rejects the write; the system stays consistent but genuinely unavailable

Setting partitioned = True and attempting to write stock=30 to node_b (the isolated node) through CPSystem correctly raises ConnectionError: Write rejected: partitioned, cannot guarantee consistency. node_b.data stays exactly as it was — no write happened, no risk of disagreement, and a real customer request genuinely failed.

Verified directly — AP accepts both writes; the system stays available but genuinely diverges

The identical partition, but through APSystem: writing stock=45 to node_a (representing a real sale processed on that side) and, separately, stock=42 to node_b (a different real sale, processed on the isolated side) both succeed. node_a.data now shows {'stock': 45}; node_b.data shows {'stock': 42} — genuinely disagreeing, confirmed directly (node_a.data != node_b.data → True).

The Cost of Reconciling an AP System's Own Conflict

Once the partition heals, something has to decide which of the two conflicting values is "correct." A common, simple strategy: last-write-wins, by timestamp.

Verified directly — last-write-wins doesn't recover the truth, it discards it

node_b's write (stock=42) happened microseconds after node_a's (stock=45), so last-write-wins correctly picks node_b's value — the reconciled stock becomes 42. But both writes represented real sales that genuinely happened: if both should have counted, the true combined stock is 50 − 5 − 8 = 37. The reconciled value (42) is off from the true combined value (37) by a real, unrecoverable 5 units — node_a's own sale wasn't merged with node_b's, it was silently overwritten and lost.

This is what "eventual consistency" actually costs

"Eventually consistent" doesn't mean "eventually correct" — it means the system eventually agrees on some single value, with no guarantee that value reflects everything that genuinely happened during the partition. Chapter 3's own cache staleness and Chapter 4's own replication lag both showed temporary disagreement that later resolved cleanly. This chapter's own AP finding is a sharper case: the disagreement resolves, but the resolution can permanently lose real information.

Strong vs. Eventual Consistency, Named Precisely

Model	Guarantee	Already verified in this course as
Strong consistency	Every read reflects the most recent write, always	`CPSystem`'s own behavior — verified here rejecting availability to keep this guarantee
Eventual consistency	Reads may be temporarily stale, but converge given enough time	Chapter 3's cache-invalidation bug; Chapter 4's replica staleness window; Software Architecture Fundamentals Chapter 6's own event-processing gap

Where This Connects

This chapter's finding	What it connects to
No observable difference between CP and AP without a partition	Chapter 9's own resilience-pattern chapter — designing for a partition that hasn't happened yet is exactly the discipline that chapter covers
AP's own verified information-loss on reconciliation	Chapter 4's own sharding chapter — a cross-shard write conflict is a structurally identical problem, one layer over
Write-behind's own verified crash-loss finding, revisited here as a genuine AP-style tradeoff	Chapter 3's own caching chapter — write-behind is, in CAP terms, an availability-favoring choice made at the cache layer specifically

Hands-On Exercises

Exercise 1

Using this chapter's own CPSystem, verify that writes to node_a (the non-isolated node) still succeed correctly during a partition, even though writes to node_b are rejected. Explain what this confirms about which specific node a CP system sacrifices availability for.

📄 View solution

Exercise 2

Using this chapter's own reconciliation scenario, implement a different strategy — "highest value wins" instead of last-write-wins — and verify what final stock value and what discrepancy from the true combined total (37) it produces.

📄 View solution

Exercise 3

Using this chapter's own verified findings, explain why a real production system's own choice of CP or AP would most plausibly be decided per-operation (some writes CP, others AP) rather than as one single, system-wide setting — use this chapter's own stock-tracking scenario alongside a login/authentication scenario to make the contrast concrete.

📄 View solution

Chapter 5 Quick Reference

CAP, precisely: the Consistency-vs-Availability tradeoff only exists during an actual network partition — verified: CP and AP behaved identically with no partition, both perfectly consistent and perfectly available
During a partition, verified: CP rejected a write outright (unavailable, still consistent); AP accepted two conflicting writes (available, now genuinely inconsistent — 45 vs. 42)
Reconciliation cost, verified: last-write-wins produced 42 against a true combined value of 37 — a real, permanent 5-unit loss of information, not just a delay
Next chapter: Message Queues & Asynchronous Processing — the mechanism most real systems actually use to manage exactly this kind of tradeoff deliberately