CAP Theorem & PACELC

🔴 P0 — the foundational impossibility result and its more nuanced successor

CAP Theorem #

In a distributed system experiencing a network partition (P), you must choose between:

• Consistency (C): Every read receives the most recent write
• Availability (A): Every request receives a response (not an error)

You cannot have both during a partition. This is a proven impossibility result (Brewer’s conjecture, proved by Gilbert & Lynch, 2002).

Limitations of CAP #

• CAP only applies during partitions. In normal operation, you can have both C and A.
• CAP says nothing about latency — a “consistent” system that takes 30 seconds to respond is technically CAP-consistent but practically useless.
• Real systems don’t choose “CP or AP” globally — they choose per-operation or per-data-type.

PACELC: The Better Framing #

If there's a Partition (P):
  Choose between Availability (A) and Consistency (C)
Else (E), in normal operation:
  Choose between Latency (L) and Consistency (C)

Instinct #

PACELC is the mature framing for interviews. Saying “we’ll use a CP system” is junior-level. Saying “during partitions we sacrifice availability for consistency on the payment path, but in normal operation we accept higher latency for strong consistency — that’s a PC/EC choice” shows sophistication.

• INSIGHT: Different components of the same system can (and should) use different consistency models. The payment ledger needs strong consistency; the activity feed tolerates eventual consistency; the product catalog can be stale for seconds. Stating this explicitly in an interview is a seniority signal.
• RULE OF THUMB: When in doubt, choose availability with eventual consistency. Slightly stale data is tolerable for most use-cases. Only reach for strong consistency when correctness is a business requirement (money, inventory, bookings).

References #

• CAP Twelve Years Later — Eric Brewer’s retrospective
• Please Stop Calling Databases CP or AP — Martin Kleppmann
• Consistency Tradeoffs in Modern Distributed Database System Design — Abadi; the PACELC paper

DDIA 2e Reference #

• Chapter 9: Linearizability, CAP, and the relationship between consistency and consensus
• Chapter 5: Trade-offs in replication