The CAP theorem,
and the spectrum of consistency.

A distributed system tries to offer three things. Consistency — every read returns the most recent write (or an error). Availability — every request receives a non-error response, even if it isn't the latest. Partition tolerance — the system keeps working when the network drops or delays messages between nodes.

The theorem (Brewer's conjecture, proved by Gilbert & Lynch) says you can't have all three at the same time. But the framing "pick two of three" is misleading. In any real network, partitions will happen — cables fail, switches reboot, packets vanish. So partition tolerance isn't something you choose; it's something reality imposes. The actual decision is what to do during a partition: stay consistent, or stay available.

People often label a single-node SQL database as "CA". That's only true because a single node can't be partitioned from itself. The moment you replicate that database across two machines to survive failure, you've entered the distributed world, and a partition between them forces the same CP-or-AP choice.

So the honest reading of CAP is: P is mandatory, and you trade C against A only when P strikes. When the network is healthy, a well-built system can deliver both strong consistency and high availability — CAP says nothing about the happy path. Which is exactly the gap PACELC fills.

Gilbert and Lynch proved the theorem for exact definitions. Consistency means linearizability: the system behaves as if there were one copy of the data, and every read returns the most recent completed write. Availability means every request received by a node that hasn't crashed eventually gets a non-error response. Not most requests, and not only requests on the majority side: every live node, on both sides of the split. Partition tolerance means the network may lose any number of messages between nodes. The theorem then says one precise thing: while the network is split, no system can be linearizable and also answer on every live node.

Real systems rarely fit either label under those definitions:

So use CAP for the one thing it proves, and describe a real system by what it actually guarantees: which consistency model, for which operations, and what a client sees when its node is cut off. CAP is also silent on most of what you design around day to day: latency, crashed nodes, and every consistency model weaker than linearizability. Brewer made the same point in his 2012 retrospective, "CAP Twelve Years Later", and Martin Kleppmann's essay "Please stop calling databases CP or AP" argues it straight from the definitions.

PACELC completes the picture: if there is a Partition, trade Availability vs Consistency; Else (normal operation), trade Latency vs Consistency. The insight is that consistency has a cost even with no failures: to guarantee a read sees the latest write, replicas must coordinate, and coordination takes round-trips. Lower latency means accepting weaker guarantees.

These labels describe default configurations, and defaults move. MongoDB 5.0 made majority write concern the default, which changes what a primary cut off from its majority can acknowledge. Treat a PACELC label as a question to ask of a configuration, not a property of a product.

Some stores let you slide the trade-off per request: Cassandra through its consistency level (how many replicas must answer), DynamoDB by choosing an eventually consistent or a strongly consistent read. For leaderless stores that knob is the quorum, worked through below; the replication mechanics behind it are in partitioning and replication.

Pick the weakest model that still keeps your product correct. A bank balance needs linearizability. A "likes" counter is fine with eventual consistency. A chat app usually wants causal, so a reply never appears before the message it answers.

Linearizability is a recency guarantee for single operations on one object, such as a key or a register. Once a write completes, every read that starts afterwards returns that value or a newer one, and once any read has returned the new value, no later read may return the old one. It says nothing about grouping operations together. Serializability is an isolation guarantee for transactions that touch many objects: the outcome equals running the transactions one at a time in some order. That order need not match real time, so a serializable database may legally answer a read-only transaction from a slightly old snapshot.

Get both and you have strict serializability: transactions appear to run one at a time, in an order consistent with real time. Google's Spanner provides it under the name external consistency, using its TrueTime clock bounds to order commits. Two-phase locking and actual serial execution are typically strictly serializable too. Serializable snapshot isolation (PostgreSQL's SERIALIZABLE level) is not, by design: every read in a transaction comes from the snapshot taken at its first statement, so a write that commits while the transaction runs stays invisible to it. Isolation levels and their anomalies are covered in concurrency and locking.

Leaderless stores let you dial consistency at query time. With N replicas, a write waits for W acknowledgements and a read queries R replicas. If W + R > N, every read set overlaps every write set, so each read reaches at least one replica holding the latest acknowledged write. That overlap is what people usually mean by "strong consistency" here, but it is a weaker promise than linearizability, and section 09 lists where it breaks. Lower the numbers and you trade that freshness for latency and availability.

This is the bridge between CAP and the physical mechanics of replication — and when you need a single agreed value rather than a tunable one, you've crossed into consensus.

Run the failure case by hand. Three replicas hold x = 1. A client writes x = 2 with W = 1: node A acknowledges, the write returns "success," and A now disagrees with B and C. A read with R = 1 lands on node C — it returns x = 1. Stale, and the client has no way to know.

Now the same write with W = 2 (A and B ack) and a read with R = 2 (hits B and C). The read set must include B — a node with the new value — because two sets of size 2 drawn from 3 nodes cannot avoid each other. The read compares versions and returns 2. That's the entire theorem behind tunable consistency:

Every configuration for N = 3, worked out (this table is exhaustively checkable — the runnable proof is below):

Note the trap in row two: W = 2, R = 1 "feels" safe — a majority acked the write! — but 2 + 1 = 3 is not greater than 3, and the single-node read can land on the one replica that missed the write. This is exactly how Cassandra's QUORUM write + ONE read surprises people in production. And the "yes" rows promise overlap, not linearizability; the next section shows what still goes wrong.

The brute-force proof assumes every write lands on W of the key's own N replicas, writes never race, and a write either reaches W replicas or none. Production breaks all three assumptions:

The fourth row is why quorums aren't linearizable even when nothing fails. With N = 3, a writer sends x = 2 with W = 3, and the write reaches replica C first:

t1  C has x=2; A and B still have x=1       (write in flight)
t2  reader 1: R=2, asks B and C  -> 1, 2    -> returns 2
t3  reader 2 starts after reader 1 returned
    R=2, asks A and B            -> 1, 1    -> returns 1

Reader 2 started after reader 1 had seen the new value, and still got the old one. Every quorum rule held, and linearizability forbids exactly this.

Read repair is the partial fix: when a read sees replicas disagree, the coordinator writes the newest version back to the stale ones, and a background anti-entropy process (Dynamo and Cassandra compare Merkle trees) catches the keys nobody reads. If the reader finishes that repair before returning, and every writer first reads the latest version from a quorum, plain reads and writes on one key become linearizable, at a cost in latency. Riak skips the synchronous repair for performance. Cassandra does wait for repair on quorum reads, but still loses linearizability under concurrent writes because it resolves them by last-write-wins. And a linearizable compare-and-set ("create this username only if it's free") can't be built this way at all: it needs consensus. Try the failure cases in the quorum simulator, or size N, W and R in the quorum explorer.