CAP is the most quoted and most misunderstood result in distributed systems. This page states it precisely, shows why a partition forces a choice, extends it with PACELC, and maps real databases onto both.
The CAP theorem, conjectured by Eric Brewer in 2000 and proved by Gilbert and Lynch in 2002, concerns a data store replicated across machines. It names three properties:
The theorem states that when a network partition happens, a system cannot be both consistent and available. Because partitions do happen in real networks, the practical reading is: during a partition, choose C or A.
CAP explains why distributed databases behave differently under failure and forces designers to state which guarantee they give up. But it is frequently misquoted. "Pick two of three" suggests you could pick CA and forgo partition tolerance; in a distributed system you cannot opt out of partitions, only decide how to behave during one. CAP also says nothing about the system when the network is healthy, nothing about latency, and uses very strict definitions: a system that is not linearizable may still offer useful weaker guarantees such as read-your-writes or causal consistency, and a "CP" system is fully available most of the time. Brewer's own 2012 retrospective, CAP Twelve Years Later, makes these points.
Two replicas hold x. A client writes x = 2 to replica A just as the link between A and B fails. Another client now reads x from B. B has exactly two options. It can answer with the value it has, 1: the system stays available but the read is stale, breaking linearizability (an AP choice). Or it can refuse, or block until it hears from A: the system stays consistent but that request is unavailable (a CP choice). No algorithm escapes this, because B cannot learn about a write it never received.
Daniel Abadi's PACELC (2010, published 2012) extends CAP: if there is a Partition, trade Availability against Consistency; Else, trade Latency against Consistency. The else-branch exists because keeping replicas consistent requires coordination — waiting for other nodes, often in other data centres — on every write or read. Giving that up lowers latency. Since partitions are rare, the else-branch often matters more for user experience and cost.
Dynamo-style stores replicate each key to N nodes and let clients choose how many must acknowledge a write (W) and answer a read (R). If R + W > N, every read quorum overlaps the latest write quorum, so reads usually see the latest value (strict linearizability still needs extra mechanisms such as read repair and careful conflict handling). Lowering R or W reduces latency and increases availability at the cost of possible staleness: the PACELC trade-off made into a per-query setting.
This toy simulation models three replicas and a partition, and shows how quorum settings change behaviour.
import random
class Cluster:
def __init__(self, n=3):
self.data = [{"x": (0, 1)} for _ in range(n)] # key -> (version, value)
self.reachable = set(range(n))
def write(self, value, W):
up = list(self.reachable)
if len(up) < W:
return "ERROR: not enough replicas (stay consistent, lose availability)"
version = max(d["x"][0] for d in self.data) + 1
for i in up: # write to every reachable replica
self.data[i]["x"] = (version, value)
return f"ok v{version} on {sorted(up)}"
def read(self, R):
up = list(self.reachable)
if len(up) < R:
return "ERROR: not enough replicas"
replies = [self.data[i]["x"] for i in random.sample(up, R)]
return max(replies)[1] # newest version wins
c = Cluster()
c.reachable = {0, 1} # node 2 is cut off
print(c.write(2, W=2), "| quorum read:", c.read(R=2)) # 2
c.reachable = {2} # now this client can only reach node 2
print("CP-style write W=2:", c.write(3, W=2)) # ERROR
print("AP-style read R=1:", c.read(R=1)) # 1 (stale)With the partition, a strict quorum write fails (consistency kept, availability lost) while a single-replica read succeeds but may return old data. In Cassandra the same choice is the per-statement consistency level, for example CONSISTENCY QUORUM versus CONSISTENCY ONE in cqlsh.
When designing a system, CAP and PACELC turn into concrete questions for each kind of data. What should happen to a request that cannot reach a majority of replicas: fail fast, wait, or serve possibly stale data? How stale is acceptable, measured in seconds or versions? Is it acceptable for two users to make conflicting updates that are merged later, and if so, what is the merge rule — last writer wins, a counter that adds, a set that unions (the idea behind CRDTs)?
A shopping-cart example shows how answers differ within one product. Adding items to a cart can be AP: accept the write locally and merge carts later, which is the design the Dynamo paper describes. Charging the card and decrementing stock should be CP: better to show an error than to sell an item twice. Product reviews and recommendation lists can be EL, served from nearby replicas with a few seconds of lag. Writing these choices down per entity makes trade-offs explicit and reviewable.
| System | During partition (PAC) | Normal operation (ELC) | Notes |
|---|---|---|---|
| Cassandra, Riak (default settings) | PA | EL | Tunable per query; QUORUM moves toward C |
| Amazon DynamoDB | PA | EL by default | Strongly consistent reads optional, at higher cost |
| Google Spanner | PC | EC | TrueTime and Paxos; high availability in practice from Google's network |
| CockroachDB, YugabyteDB | PC | EC | Raft per range; minority side becomes unavailable |
| etcd, ZooKeeper | PC | EC | Coordination services; need a majority |
| MongoDB (majority read/write concern) | PC | EC | Weaker concerns trade toward latency |
| PostgreSQL with async replicas | PC on primary | EL for replica reads | Replica reads can be stale |
These labels describe default or typical configurations; most systems let you move along the spectrum.