CAP & Consistency Models

## What the theorem states CAP theorem, first stated by Eric Brewer in 2000 and formally proven by Seth Gilbert and Nancy Lynch in 2002, describes a hard constraint on any system that stores data on more than one machine and talks to those machines over a network. The three properties are: - **Consistency** — every read returns the value of the most recent acknowledged write, as if there were only one copy of the data. - **Availability** — every request that reaches a non-failed node receives a response, not an error or timeout. - **Partition tolerance** — the system continues operating even when messages between nodes are dropped or delayed. The theorem's claim is narrow but important: when a partition actually happens — some nodes can't exchange messages with others — a system can guarantee at most one of Consistency and Availability for the affected data, not both. ## The mechanism The mechanism is concrete. Imagine two replicas, `A` and `B`, holding a copy of the same value, and a network fault severs the link between them. A client on A's side writes a new value. `B` never sees that write because the link is down. Now a second client asks `B` to read the value. `B` has two options: 1. It can answer immediately with the value it has locally — this satisfies **Availability**, but the answer is stale, so Consistency is broken. 2. Or `B` can refuse to answer until it can confirm with `A` that it has the latest data — this preserves **Consistency**, but the request effectively failed, so Availability is broken. There is no third option that lets `B` both answer immediately and guarantee correctness, because correctness requires information `B` does not have and cannot get while the partition persists. ## Why the constraint exists CAP exists because early distributed-systems designers wanted the same guarantees a single-machine database gives — always-consistent reads — while also wanting the scalability and fault tolerance that come from spreading data across many machines and, often, many data centers. Those two goals collide the moment the network misbehaves, and networks always eventually misbehave: - switches fail; - links get saturated; - cross-region links go down for maintenance; - or a node is simply too slow to be distinguished from an unreachable one. Brewer's contribution was naming the trade-off explicitly so architects stop assuming they can dodge it. ## The cost on each side The trade-off has a cost on each side. | The choice during a partition | What it costs and what it buys | |---|---| | **Systems that pick Consistency over Availability** — commonly called CP systems, such as a strongly consistent configuration store or a relational database configured for synchronous replication | They will reject writes, and sometimes reads, on the side of the partition that cannot confirm a quorum. Users on that side see errors or timeouts until the network heals. The benefit is that no client is ever shown incorrect data. | | **Systems that pick Availability** — AP systems, such as many wide-column or key-value stores in their default configuration | They keep serving reads and writes locally on both sides of the partition. The benefit is uptime: no user-facing errors caused by the network fault. The cost is that the two sides can now diverge, and the system needs a reconciliation strategy once the partition heals. | ## Failure modes 1. **Split-brain** is the failure mode most often traced back to CAP in production: both halves of a partitioned cluster believe they are the sole authority and keep accepting writes, so each half's data silently drifts from the other's. This is especially dangerous for systems doing leader election or distributed locking, where two 'leaders' active at once can corrupt shared state. 2. A second common failure mode is a **false partition**: a node isn't actually cut off from the network, but it is so slow — say, during a long garbage-collection pause — that the rest of the cluster times out and treats it as partitioned, triggering an unnecessary failover or a burst of stale reads. 3. A third is teams believing they've built a system with no cost, when in reality they've never tested what happens when the network actually splits, and the day it does, one guarantee quietly breaks. ## Where the choice shows up A concrete illustration: a multi-region deployment of a distributed configuration service like ZooKeeper is deliberately CP. If the network between two data centers is severed, the minority side of the ZooKeeper ensemble stops serving writes and stale reads entirely rather than risk two nodes disagreeing about, say, which service instance currently holds a distributed lock — an incorrect answer there could mean two processes both believe they own an exclusive resource. The minority side becomes unavailable until it can rejoin a quorum, which is the deliberate, accepted cost of guaranteeing correctness for that kind of coordination data.