Distributedcap theoremconsistencyavailabilitypartition toleranceeventual consistency

Distributed Consistency: CAP, Quorums, Consensus

CAP is not "pick two" — it is a choice you make only during a network partition, between refusing writes to stay consistent and accepting them to stay available; the rest of the time you are trading latency for consistency.

▶ Interactive Interview question See how this works internally →

Progress

CAP, stated correctly

A distributed system can be Consistent (every read sees the latest write), Available (every request gets a non-error response), and it must tolerate Partitions (the network between nodes can fail), because networks do fail. The theorem says: when a partition happens, you must choose C or A. You cannot have both while nodes cannot talk to each other. When there is no partition — almost always — you have both, and CAP says nothing.

So the "pick two" slogan is misleading. P is not optional; you do not get to choose it away. The real choice is C-versus-A *during a partition*, and the honest name for the everyday trade is PACELC: during a Partition choose A or C, Else (normal operation) choose Latency or Consistency. Synchronous replication chooses consistency and pays latency; asynchronous chooses latency and is eventually consistent.

What each choice looks like

A CP system (a single-primary SQL database, etcd, ZooKeeper, HBase) during a partition refuses writes on the side that cannot reach a majority. Clients there get errors; nobody ever reads a value that will later be rolled back. Correct, partially unavailable. An AP system (Dynamo-style stores, Cassandra with low quorums) keeps accepting writes on both sides of the partition. Everyone stays up; the two sides now disagree, and when the partition heals something must merge them — last-writer-wins (lossy), CRDTs (mergeable by construction), or application logic. Available, temporarily inconsistent.

Neither is better. A bank ledger wants CP: refuse the write rather than double-spend. A shopping cart wants AP: never block the user, reconcile two versions of the cart later. The system’s job determines the choice.

Quorums

Replicated stores tune consistency with three numbers: N replicas, W must acknowledge a write, R must be read. When W + R > N, any read set and any write set overlap on at least one node, so a read always sees the latest write — strong consistency. N=3, W=2, R=2 is the common majority-both-ways setting. W=1, R=1 is fast and eventually consistent. W=N gives no write availability if any node is down. The knobs let one system be CP or AP per operation.

Consensus

The CP side needs the nodes to agree on one leader and one order of writes, even as nodes fail. Raft and Paxos do this: a leader is elected by majority vote with a term number; a write is committed once a majority has it in its log; a partitioned minority can never gather a majority, so it can never elect a leader or commit a write — which is exactly what prevents two leaders and split-brain. Every strongly-consistent distributed database — CockroachDB, Spanner, etcd, YugabyteDB — is a consensus log with a database on top. Understanding that one sentence demystifies the whole category.

Majority wins, minority waits

UserLLMAgentToolDataDecisionHumanGuardrail

Key points

Partition tolerance is mandatory; CAP is a C-vs-A choice made only during a partition.
PACELC names the everyday trade: else, latency vs consistency.
CP refuses writes in the minority; AP accepts everywhere and reconciles later. The workload decides.
Quorums (W + R > N) tune consistency per operation; consensus (Raft/Paxos) is how CP systems keep one leader and one log.

CAP under a real partition

CAP is about what you do during a partition

Three nodes, one network. Cut the network and decide: refuse writes until it heals (consistent), or accept them on both sides (available). There is no third option while the partition lasts — and no choice at all while it does not.

No partition. The system is both consistent and available — CAP imposes nothing until the network fails. Day to day, the trade you are actually making is latency vs consistency: synchronous replication costs a round trip per write; asynchronous is fast and lags.

Quorums: N replicas, W to write, R to read

N3W2R2

W + R > N ?

4 > 3 — read sees latest write

With W + R > N, any read set overlaps any write set on at least one node, so at least one replica in the read has the newest value. W = R = 1 is fast and eventually consistent; W = N gives no availability if any node is down. Most systems run N=3, W=2, R=2 — a majority both ways.

-- Postgres synchronous_commit / synchronous_standby_names
-- is the same idea with W: how many replicas must confirm
synchronous_standby_names = 'ANY 1 (replica_a, replica_b)'

Consensus, briefly: the CP side needs the majority to agree on a single leader and a single log order — that is what Raft and Paxos do. A leader is elected by majority vote with a term number; writes are committed once a majority has them in its log; a partitioned minority can never elect a leader, which is exactly what keeps two leaders from existing. Every "strongly consistent distributed database" is a consensus log with a database on top.

When to use — and when not

Use it when

Any multi-node datastore decision; understanding what a managed distributed database is really promising.

Avoid it when

Reaching for a distributed database when one primary with replicas would serve the actual load — the consistency tax is real.

Failure modes

Assuming "highly available" means "consistent".
Choosing an AP store for money.
Last-writer-wins silently dropping concurrent writes.
Running consensus across regions and paying cross-region latency on every write.