CAP Theorem: The Fundamental Trade-off

📘 Chapter 9: Consistency & Distributed Consensus ⏱️ 8 min read 🏗️ Lesson 035

Every distributed system faces a fundamental constraint. In 2000, Eric Brewer proposed what became known as the CAP theorem: a distributed data store can only guarantee two of three properties — Consistency, Availability, and Partition Tolerance. But the real insight is subtler than "pick 2 of 3."

The Three Properties

C — Consistency

Every read receives the most recent write or an error. All nodes see the same data at the same time. It's as if there's only one copy of the data.

A — Availability

Every request receives a non-error response — without guarantee that it contains the most recent write. The system always responds, even if the data might be stale.

P — Partition Tolerance

The system continues to operate despite network failures between nodes. Messages between nodes can be dropped, delayed, or reordered.

The Venn Diagram (and Where Real Systems Land)

CAP Theorem — Real Systems Placement C Consistency A Availability P Partition Tolerance CA Single-node RDBMS PostgreSQL (single) CP HBase MongoDB ZooKeeper etcd AP Cassandra DynamoDB CouchDB Riak ⚠️ CA is theoretical in distributed systems — partitions WILL happen in any network
Figure 1: The CAP Venn diagram. In practice, distributed systems must tolerate partitions (P), so the real choice is between CP and AP.

The Real Choice: C vs A During a Partition

Here's the key insight most people miss: network partitions will happen. Cables get cut, switches fail, cloud regions lose connectivity. Since P is non-negotiable in any distributed system, the actual decision is:

  • Choose C (reject requests): When a partition occurs, the system refuses to respond rather than risk returning stale data. Users get errors, but data stays consistent.
  • Choose A (serve stale data): When a partition occurs, the system continues responding with whatever data it has — potentially outdated. Users get responses, but might see inconsistent data.
What Happens During a Network Partition? ⚡ NETWORK PARTITION ⚡ Node A Has: balance = $100 Node B Has: balance = $100 ✏️ Write: balance = $80 (Client withdrew $20) ✗ Can't replicate Choose Consistency (CP) Node B: "Read balance?" → ERROR: Service unavailable Refuses to serve stale $100 value Choose Availability (AP) Node B: "Read balance?" → Response: balance = $100 Serves stale data (real value is $80)
Figure 2: During a partition, you must choose: refuse requests (consistency) or serve potentially stale data (availability).

Brewer's Clarification

In 2012, Eric Brewer published a clarification: CAP is about the system's behavior during a partition, not in normal operation. When the network is healthy, you can have both consistency and availability. The theorem only forces a choice when things go wrong.

Most systems aren't purely CP or AP — they make different trade-offs for different operations. DynamoDB is "AP by default" but offers optional strongly consistent reads.

PACELC: The Extended Model

If Partition → A or C; Else → Latency or Consistency

PACELC extends CAP to address what happens during normal operation:

  • PA/EL: During partition choose Availability; Else choose Low Latency → DynamoDB, Cassandra
  • PC/EC: During partition choose Consistency; Else choose Consistency → ZooKeeper, HBase
  • PA/EC: During partition choose Availability; Else choose Consistency → MongoDB (default)
  • PC/EL: During partition choose Consistency; Else choose Low Latency → (rare combination)

This model captures the reality that even without partitions, there's a trade-off between latency and consistency due to replication delays.

Real-World Examples

🏢 DynamoDB: Choosing AP (with Optional Strong Consistency)

DynamoDB prioritizes availability — writes always succeed and are propagated asynchronously to replicas. This means:

  • Default: Eventually consistent reads — you might read slightly stale data (usually consistent within milliseconds)
  • Optional: Strongly consistent reads — DynamoDB reads from the leader replica, guaranteeing the latest data, but at higher latency and cost (2x the read capacity units)
  • During a partition: The system remains available. Writes succeed to reachable nodes and sync later

This is perfect for shopping carts, session stores, and user preferences where a brief stale read is acceptable.

🏢 ZooKeeper: Choosing CP

ZooKeeper is used for coordination tasks (leader election, distributed locks, configuration). It prioritizes consistency:

  • Writes require a quorum (majority of nodes must acknowledge)
  • If the leader can't reach a quorum → rejects all writes
  • Reads are served from the leader (or any node in relaxed mode), guaranteeing clients see a consistent view
  • During a partition: minority-side nodes become unavailable — they refuse requests

This is essential for coordination — you can't have two services both thinking they're the leader.

Interactive: Simulate a Network Partition

Choose your system's behavior during a partition:

Node A (Leader)
balance = $100
🟢 Connected
Node B (Replica)
balance = $100