CAP and Distributed Systems

The CAP theorem is usually presented as a menu — consistency, availability, partition tolerance, "pick two" — and the menu is misleading, because partition tolerance is not on offer. A partition is any situation in which two nodes that should communicate cannot, for long enough to matter. Cables get cut, but far more often a switch drops packets for 8 seconds, a garbage collection pause stops a node for 20 seconds, a kernel is starved of CPU, or a link is simply slow enough that every request times out. A timeout is a partition: from the caller’s point of view there is no difference between "the network is down" and "the node is too slow to answer within my deadline", and the caller has to decide what to do without knowing which it is. If your system runs on more than one machine, partitions will happen; the only decision available is what the system does *during* one.

The precise statement is this: during a partition, a system with replicated data must either refuse some operations (typically writes, and sometimes reads, on the side that cannot reach a majority) to keep a single, consistent history — or accept operations on both sides and therefore allow the sides to diverge, to be reconciled afterwards. The first is what CAP calls consistent (CP), the second available (AP). Both are legitimate; neither is free; and the choice can be made per operation, not just per system.

The "C" in CAP is linearizability: every operation appears to take effect atomically at some instant between its start and its end, so that once any client has seen a write, every later read anywhere sees it or something newer — the system behaves as if there were one copy. That is a much stronger property than the "C" in ACID, and it is expensive because it requires the replicas to agree before answering. Eventual consistency is the weak end: replicas may return different values for a while, and are guaranteed only to converge once writes stop and communication resumes. Between them sit useful intermediate guarantees — read-your-own-writes, monotonic reads, causal consistency — which Distributed Consistency: CAP, Quorums, Consensus covers in detail; in practice the most common architectures offer linearizability for a few operations (a unique-username check, a balance debit, a leader election) and eventual consistency for the rest.

Choosing availability during a partition is not "free availability". The system that accepts balance = 80 in Europe and balance = 50 in the US must later decide which is right, and there is no general answer: last-writer-wins silently discards one of them, version vectors detect the conflict and hand it to the application, and CRDTs restrict the data types to ones that merge automatically (counters, sets, registers with defined merge rules). Shopping carts merge well — a union of items is acceptable. Bank balances do not, which is why a bank refuses the write instead. The choice is dictated by whether a conflict can be resolved meaningfully after the fact.

Quorum systems turn the choice into arithmetic. With N replicas, a write is acknowledged after W replicas have it, and a read consults R replicas and takes the newest. If W + R > N, every read set overlaps every write set in at least one replica, so a read is guaranteed to see the latest acknowledged write. With N = 3, W = 2, R = 2, the system tolerates one replica being unreachable for both reads and writes; a side of a partition holding only one replica can serve neither, which is the consistent choice. Set W = 1, R = 1 and both sides keep serving — the available choice — at the cost of stale reads and divergent writes. Sloppy quorums and hinted handoff (Dynamo, Cassandra) let writes land on any W reachable nodes, not the designated ones, and forward them later; this keeps writes available through a partition and weakens the overlap guarantee, so the numbers stop meaning what they appear to mean.

Consensus protocols — Raft in etcd, Consul and CockroachDB, ZAB in ZooKeeper, Paxos in Spanner — are the strict form: a majority must agree on every write in order, and the minority side of a partition cannot make progress at all. That is exactly the property a lock service or a leader election needs: two leaders is worse than no leader.

CAP describes the partition, which is rare. PACELC adds the everyday case: if there is a Partition, trade Availability against Consistency; Else, trade Latency against Consistency. A system that stays linearizable in normal operation pays a round trip to a quorum on every write, and often on every read; one that answers from the nearest replica is faster and can be stale. Cross-region synchronous replication is the sharpest example — 80 ms per commit between Frankfurt and Virginia, for every write, forever, in exchange for never losing an acknowledged write in a regional failure. That latency is the price of consistency when *nothing is wrong*, and it is paid far more often than the partition-time price.

What a system actually does during a partition is a matter of its configuration, not its marketing, and most systems can be tuned to either side.

Because partitions include timeouts, every system that makes a remote call has already made a CAP decision, usually by accident. A payment service that times out on the database and returns an error chose consistency. One that times out and returns "probably succeeded" chose availability and must now reconcile — which is where the idempotency key from the async module and the compensation in Saga Pattern come from; Distributed Transactions is the same problem stated for multi-step writes. Make the decision explicit, per operation: the operations that cannot tolerate divergence (debits, unique names, leader election, inventory reservation) go through a quorum or a single leader and are unavailable on the minority side; everything else (view counts, presence, carts, feeds) accepts writes anywhere and merges.

Then rehearse it. Inject latency and drop links between availability zones in staging and watch what each store does; the failure that surprises you in production is the one you assumed was a theory. Leases should have expiry so a partitioned leader stops leading before a new one is elected (fencing tokens make the old leader’s late writes rejectable). And the minority side should *know* it is the minority: a node that cannot reach a majority should say so, not guess.