CAP Theorem: The Trade-off Every Distributed System Makes

Proposed by Eric Brewer in 2000, CAP theorem remains one of the most fundamental principles in distributed systems engineering. It doesn’t tell you what to build — it tells you what you’re giving up.

The Three Properties

CAP states that a distributed system can guarantee at most two of: Consistency, Availability, Partition Tolerance.

Consistency — every read returns the most recent write, or an error. All nodes see the same data at the same time.

Availability — every request gets a response. No errors, no timeouts, even if some nodes are degraded.

Partition Tolerance — the system keeps operating when network messages between nodes are dropped or delayed.

Partition Tolerance is Not Optional

Network partitions happen in any real distributed system. You cannot opt out of P. In fact, it is not feasible to forego partition tolerance in favor for a true CA application. It assumes that a network never fails. In a distributed system spanning multiple nodes — sometimes spanning multiple data centers — this assumption simply doesn’t hold. When a partition occurs and the system does not have any handling strategy, it simply goes down.

The real choice is: what do you do when a partition occurs?

CP — refuse to serve potentially stale data. Return an error until the partition heals. Consistent, not always available.
AP — keep serving from reachable nodes. Accept that different nodes may return different values until they resync. Available, not always consistent.

Consistency is not always the right answer. For many systems, serving a slightly stale response is far better than returning an error. A social feed, a product catalogue, a cache — users expect these to stay up, not to be perfectly fresh.

CP vs. AP in Practice

CP — bank transfer

Node B hasn’t received a write from Node A due to a partition. A CP system refuses to answer until it can confirm it has the latest data. You never show a stale balance that could cause an overdraft.

Common CP databases: Zookeeper, etcd (leader election, config), Google Spanner (global transactions).

AP — shopping cart / social feed

Two sessions diverge during a partition — items added in both. An AP system keeps accepting writes and reconciles later. Briefly stale or merged data is acceptable; an error is not.

Common AP databases: Cassandra (wide-column, tunable), DynamoDB (managed, serverless-friendly).

Consistency Is a Spectrum

“Consistent or not” is too crude. In practice, it’s a dial:

Level	Guarantee
Linearizability	Every read reflects the latest write. Operations appear instantaneous.
Sequential consistency	All nodes see operations in the same order, but not necessarily in real time.
Causal consistency	Causally related operations are seen in order. Unrelated writes may diverge.
Eventual consistency	All nodes converge to the same value given no new writes — eventually.

Visualization between different configurations of consistency approaches in distributed systems

Most “AP” systems in practice offer eventual consistency — they’re not chaotic, they just don’t guarantee instantaneous agreement.

PACELC: The More Complete Model

CAP only describes behaviour during a partition. PACELC extends it:

If Partition → choose Availability or Consistency.
Else (normal operation) → choose Latency or Consistency.

Even without a partition, replicating synchronously to all nodes before acknowledging is consistent but slow. Replicating asynchronously is fast but briefly inconsistent. Most real systems are making both trade-offs simultaneously, all the time.

Quorum: Voting for Consistency

A quorum is the minimum number of nodes that must agree on a read or write for it to be considered valid. It’s how distributed systems enforce consistency without requiring every node to respond.

In a cluster of N replicas, define:

W — nodes that must acknowledge a write
R — nodes that must respond to a read

If W + R > N, the read and write sets are guaranteed to overlap — at least one node in every read saw the latest write. That’s the consistency guarantee.

N=3, W=2, R=2  →  W + R = 4 > 3  ✓  (overlap guaranteed)
N=3, W=1, R=1  →  W + R = 2 < 3  ✗  (may read stale data)

With Cassandra’s default replication factor of 3:

CONSISTENCY ONE;     -- R or W = 1, fastest, weakest
CONSISTENCY QUORUM;  -- R or W = ceil(N/2) + 1 = 2, balanced
CONSISTENCY ALL;     -- R or W = 3, strongest, least available

Sloppy quorum relaxes this further. When a target node is unavailable during a partition, the write is accepted by any available node instead — preserving availability. The write is delivered to the intended node when it recovers (hinted handoff). This trades strict quorum overlap for higher availability under failure. Dynamo and Cassandra both use this approach. See Dynamo for the full mechanics.

Practical Heuristics

Use case	Lean toward
Financials, inventory, auth	CP
Feeds, caches, location, carts	AP
Both matter	Tunable consistency (Cassandra, DynamoDB)

CAP isn’t a law you obey — it’s a lens for asking: when something goes wrong, what do you want to preserve?