CAP Theorem, PACELC, and Distributed System Tradeoffs

A field guide to the tradeoffs every distributed system makes — during a network partition, and even when nothing is broken. What you give up, when, and why the "right" answer depends entirely on what a stale read actually costs you.

1. CAP Theorem

Every distributed system can guarantee at most 2 of 3 properties:

Why P is non-negotiable: Networks fail. Any distributed system deployed across nodes will experience partitions. You cannot sacrifice P — you can only choose between C and A when a partition occurs.

So the real tradeoff is:

• CP: When partitioned, reject requests to guarantee consistency (return error or block)
• AP: When partitioned, serve potentially stale data to guarantee availability

2. Network Partition: CP vs AP Behavior

graph TD
    classDef primary fill:#2980b9,stroke:#1f618d,color:#fff
    classDef replica fill:#7f8c8d,stroke:#616a6b,color:#fff
    classDef cut fill:#e74c3c,stroke:#c0392b,color:#fff
    classDef cpResult fill:#c0392b,stroke:#922b21,color:#fff
    classDef apResult fill:#e67e22,stroke:#ba6018,color:#fff

    CLIENT["Client"] -->|"write x=5"| N1["Node 1 — Primary<br/>holds x=5"]:::primary
    N1 -->|"replicate x=5"| N2["Node 2 — Replica<br/>in sync, holds x=5"]:::replica
    N1 -.->|"NETWORK PARTITION<br/>replication link down"| N3["Node 3 — Replica<br/>cut off, still holds x=0"]:::cut

    subgraph CP["CP system — during the partition"]
        N3 -->|"read request"| CPR["Refuses to answer<br/>returns ERROR — can't guarantee freshness"]:::cpResult
    end

    subgraph AP["AP system — during the partition"]
        N3 -->|"read request"| APR["Answers anyway<br/>returns x=0, stale but available"]:::apResult
    end

CP (ZooKeeper, etcd): Node 3 refuses to serve reads — it may be out of sync. Client gets an error.

AP (Cassandra, DynamoDB): Node 3 serves stale data. Client gets a response, possibly wrong.

3. Real System Classifications

Why Consensus Gives You CP

The table above lists etcd's consistency as "Linearizable (Raft)" — but why does a Raft- or Paxos-based consensus protocol earn you the C in CP, rather than just happening to be strong most of the time? The mechanism is quorum writes. Every write has to be replicated to and acknowledged by a majority of nodes before the leader commits it and answers the client — that's exactly the same W+R>N overlap guarantee from the quorum math in Section 8, with W set to a majority and every read served by (or forwarded to) the current leader.

That single rule is what produces both halves of CP simultaneously. Consistency falls out because any future leader must also win a majority vote, and a majority-vote quorum always overlaps with any majority-write quorum in at least one node — so a new leader can never be elected without seeing every previously committed write. Availability loss on a minority partition isn't a bug or a side effect — it's the same rule enforced from the other direction: a minority of nodes can never assemble a quorum for a write or an election, so it cannot make progress, full stop, not "make progress slowly." That inability to progress is the unavailability CAP describes.

The actual leader-election state machine, term numbers, and log-replication protocol that implement this — plus a live, interactive Raft election simulator you can click through node failures on — live in databases/replication.md § 9, Consensus Algorithms. This section only covers the CAP-level "why"; that one covers the "how."

4. Consistency Models Spectrum

From strongest to weakest:

graph LR
    classDef strong fill:#c0392b,stroke:#922b21,color:#fff
    classDef high fill:#e67e22,stroke:#ba6018,color:#fff
    classDef medium fill:#f1c40f,stroke:#b7950b,color:#000
    classDef weak fill:#27ae60,stroke:#1e8449,color:#fff

    LIN["Linearizable<br/>strongest — real-time global order"]:::strong --> SEQ["Sequential<br/>one shared order, no wall-clock guarantee"]:::high --> CAU["Causal<br/>only causally-related ops ordered"]:::medium --> EVT["Eventual<br/>weakest — converges given enough time"]:::weak

5. PACELC

CAP only covers behavior during partitions. PACELC extends it:

If Partition → choose A or C Else (normal operation) → choose Latency or Consistency

Even without failures, replicating synchronously costs latency.

graph TD
    classDef question fill:#34495e,stroke:#212f3c,color:#fff
    classDef cpath fill:#c0392b,stroke:#922b21,color:#fff
    classDef apath fill:#e67e22,stroke:#ba6018,color:#fff

    START{"Is the system<br/>currently partitioned?"}:::question
    START -->|"Yes"| PICKAC{"Pick: Availability<br/>or Consistency?"}:::question
    START -->|"No — normal operation"| PICKLC{"Pick: Latency<br/>or Consistency?"}:::question
    PICKAC -->|"Choose A"| PA["PA — serve stale data,<br/>stay available (Cassandra, DynamoDB)"]:::apath
    PICKAC -->|"Choose C"| PC["PC — refuse requests,<br/>stay correct (ZooKeeper, etcd)"]:::cpath
    PICKLC -->|"Choose L"| EL["EL — respond fast,<br/>replicate asynchronously (Cassandra, DynamoDB)"]:::apath
    PICKLC -->|"Choose C"| EC["EC — wait for sync replication,<br/>pay the latency (ZooKeeper, etcd, Spanner)"]:::cpath

6. Consistency vs Availability Tradeoffs in Practice

DynamoDB: AP saves latency

Eventually consistent read:  ~1ms  — reads from any replica
Strongly consistent read:    ~2ms  — reads only from leader

At 100k req/s: eventually consistent = 2x throughput capacity

DynamoDB's default eventual consistency means your shopping cart may show a stale item count — acceptable. A banking balance cannot use this.

ZooKeeper: CP costs availability

graph TD
    classDef healthy fill:#27ae60,stroke:#1e8449,color:#fff
    classDef degraded fill:#f39c12,stroke:#ba6018,color:#fff
    classDef down fill:#e74c3c,stroke:#c0392b,color:#fff

    A["All 3 nodes healthy<br/>quorum = 3/3<br/>leader serves reads + writes ✓"]:::healthy -->|"1 node fails"| B["1 node down<br/>quorum intact = 2/3<br/>still fully operational ✓"]:::degraded
    B -->|"2nd node fails"| C["2 nodes down<br/>quorum lost = 1/3<br/>ALL reads + writes REFUSED ✗"]:::down
    B -->|"failed node recovers"| A
    C -->|"a node recovers"| B

ZooKeeper refuses to serve rather than risk inconsistency. This is correct for distributed locking and leader election — a stale lock is worse than no lock.

7. Tunable Consistency

DynamoDB

# Eventual consistent read (default, faster)
table.get_item(Key={"id": "123"})

# Strongly consistent read (latest data, higher latency)
table.get_item(Key={"id": "123"}, ConsistentRead=True)

Cassandra Quorum

-- Strong consistency (W+R > N)
INSERT INTO orders ... USING CONSISTENCY QUORUM;   -- W=2 of 3
SELECT * FROM orders WHERE ... CONSISTENCY QUORUM; -- R=2 of 3

-- High availability, eventual
INSERT INTO orders ... USING CONSISTENCY ONE;      -- W=1 of 3
SELECT * FROM orders WHERE ... CONSISTENCY ONE;    -- R=1 of 3

MongoDB Read/Write Concern

// Strong: wait for majority replica acknowledgment
db.collection.insertOne(doc, { writeConcern: { w: "majority" } })

// Read from primary only (latest)
db.collection.find({}).readPreference("primary")

// Read from secondary (may be stale, lower latency)
db.collection.find({}).readPreference("secondaryPreferred")

8. Quorum Math

For a cluster of N nodes with W write acknowledgments and R read replicas consulted:

Strong consistency requires: W + R > N

This guarantees at least one node in the read set saw the latest write.

graph TD
    classDef write fill:#e67e22,stroke:#ba6018,color:#fff
    classDef read fill:#3498db,stroke:#2471a3,color:#fff
    classDef overlap fill:#27ae60,stroke:#1e8449,color:#fff
    classDef idle fill:#7f8c8d,stroke:#616a6b,color:#fff

    subgraph CLUSTER["3-node cluster — W=2 write acks, R=2 read replicas (W+R=4, N=3: overlap guaranteed)"]
        N1["Node 1<br/>acked the write, has latest value"]:::overlap
        N2["Node 2<br/>acked the write, has latest value"]:::write
        N3["Node 3<br/>never received the write, stale"]:::idle
    end

    WSET["Write set (W=2)<br/>Node 1 + Node 2"]:::write
    RSET["Read set (R=2)<br/>Node 1 + Node 3"]:::read

    N1 --> WSET
    N2 --> WSET
    N1 --> RSET
    N3 --> RSET
    WSET -.->|"shared member: Node 1 —<br/>the read set always includes<br/>at least one node from the write set"| RSET

Availability tradeoff: Higher W = slower writes (more nodes must respond). Higher R = slower reads. Tune based on whether reads or writes are on the hot path.

Fault tolerance: With W+R>N and N=3, W=2, R=2 → you can lose 1 node and still have quorum. With N=5, W=3, R=3 → tolerate 2 node failures.

Try It Yourself: Live Quorum Overlap

The table above states W+R>N as a static arithmetic rule. But the guarantee it describes is really about specific nodes, not just counts — a write quorum and a read quorum only actually overlap if the particular nodes chosen for each happen to share a member. Toggle real nodes into a write set and a read set below and see whether they actually intersect, for sizes both above and at-or-below the W+R>N threshold.

Try this: set N=5. Pick W = {0, 1} and R = {2, 3} — sizes 2 and 2, W+R=4, which is not greater than N=5, and these two picks share no node: no overlap. Now, keeping the same sizes, try W = {0, 1} and R = {0, 2} instead — still W+R=4 ≤ N=5, but this particular pair does share node 0. That's the point: below the W+R>N threshold, overlap is possible but not guaranteed — whether any given pair overlaps depends entirely on which specific nodes got picked, which is luck unless a protocol enforces it. Now expand the read set to {2, 3, 4} (R=3) — still W+R=5, not greater than N=5, and you can still find non-overlapping picks. Finally grow the read set to 4 nodes (W+R=6 > N=5) and try several completely different node choices for both sets: every single one overlaps, no matter which specific nodes you pick — with only 5 nodes total, 2 write nodes and 4 read nodes can't help but share one. That's pigeonhole, not luck, and it's exactly the guarantee a real quorum protocol enforces on every request by construction (see "Why Consensus Gives You CP" above), rather than leaving it to chance the way this toy does.

9. Vector Clocks and Version Vectors

Distributed systems need to detect concurrent writes — changes made on different nodes with no causal ordering.

Vector Clock

Each node maintains a counter per node. On every event:

• Increment own counter
• Merge (take max) on receive

C cannot determine which write happened first → conflict detected. System must reconcile (last-write-wins, merge, or surface to application).

Try It: Live Vector Clocks

The stepper above walks through one scripted sequence. Below, drive three real vector clocks yourself — write on any node, replicate in either direction between any pair, and watch the status line classify the two clocks it just compared as concurrent or causally ordered. Reproduce the stepper's exact scenario (Write @ A, Write @ B, Replicate A→C, Replicate B→C — watch the last step report "concurrent"), then try other orderings: what happens if you replicate A→C before B ever writes?

Conflict Resolution Strategies

Version Vectors vs Vector Clocks

• Vector clocks: track causality per event
• Version vectors: track causality per replica/object (more common in databases)

DynamoDB uses version vectors internally. Cassandra uses timestamps (LWW), not vector clocks — simpler but can lose data on concurrent writes.

10. Practical Guidance: CP vs AP by Use Case

Decision Framework

graph TD
    classDef question fill:#34495e,stroke:#212f3c,color:#fff
    classDef cp fill:#c0392b,stroke:#922b21,color:#fff
    classDef ap fill:#e67e22,stroke:#ba6018,color:#fff

    subgraph H1["Heuristic 1 — blast radius of a stale read"]
        Q1{"Is stale data dangerous?<br/>security, money, inventory"}:::question
        Q1 -->|"Yes"| CP1["CP — accept availability<br/>degradation on partition"]:::cp
        Q1 -->|"No"| AP1["AP — accept stale reads<br/>for higher availability"]:::ap
    end

    subgraph H2["Heuristic 2 — can the caller just retry?"]
        Q2{"Is the operation idempotent<br/>and safely retryable?"}:::question
        Q2 -->|"Yes"| AP2["AP is safer —<br/>client retries on a stale read"]:::ap
        Q2 -->|"No"| CP2["CP required —<br/>a retry could double-charge/deduct"]:::cp
    end

    subgraph H3["Heuristic 3 — latency vs. accuracy"]
        Q3{"Is low latency more important<br/>than perfect accuracy?"}:::question
        Q3 -->|"Yes"| AP3["AP + eventual consistency —<br/>feeds, analytics, caches"]:::ap
        Q3 -->|"No"| CP3["CP —<br/>financial records, auth tokens, locks"]:::cp
    end

Summary

CAP:    Network partition is inevitable → choose CP or AP
PACELC: Even without partition → Latency (AP) vs Consistency (CP)

CP systems:  ZooKeeper, etcd, PostgreSQL (sync), Kafka (ISR)
AP systems:  Cassandra, DynamoDB (default), Riak, Couchbase

Quorum:     W + R > N → strong consistency
Vector clocks: detect concurrent writes, enable conflict resolution

Rule of thumb:
  Money / Auth / Locks → CP
  Feeds / Carts / Caches → AP