CAP Theorem

CAP concerns what a distributed system can guarantee while communication is partitioned. In the theorem, consistency is a single-copy, linearizable view of operations, and availability requires every request to a non-failing node to complete under the model. These are narrower terms than “data quality” and “good uptime.” During a partition, a service cannot guarantee both for all operations.

Learning goals

Network partitions; linearizable consistency; availability in the theorem; stale reads; per-operation choices; quorum limits; recovery.

The mechanism at a glance

Figure — Buyer Alice → Replica A (reserve); Replica A → Partition (cannot reach B); Replica B → Partition (cannot reach A); Buyer Bob → Replica B (reserve); One-owner invariant → Replica A (requires authority); One-owner invariant → Replica B (requires authority)

The numbered components identify responsibilities. Follow the labeled arrows rather than treating the numbers as a global execution order. The scenario later in this lesson shows one concrete sequence.

Step-by-step reasoning

1. Construct the partition

Two replicas begin with one available seat. Their communication link breaks, but each still receives clients. A buyer asks each replica to reserve that last seat. Neither replica can learn whether the other has accepted a conflicting reservation. The missing information, not machine count, creates the problem.

2. Choose behavior per operation

To preserve the one-owner invariant, restrict successful reservations to an authoritative side or return an unavailable response when authority cannot be established. A profile read may instead return a labeled stale copy. These choices can coexist in one product. Calling an entire application “CP” or “AP” hides the operation-specific user experience.

3. Understand quorum limits

Overlapping quorums are useful building blocks, but R+W>N is not a complete proof of linearizability for an arbitrary implementation. Version ordering, leader behavior, concurrent writes, failure detection, and the read protocol matter. A majority-based protocol may keep a majority side operating while a minority refuses operations that require consensus.

4. Plan recovery and explain latency

When the link returns, reconcile divergent state according to the semantics you promised. A last-write-wins rule may be acceptable for a cosmetic preference but can lose a purchase or double-spend a scarce resource. Even without a partition, geographic coordination has latency costs; CAP does not say a healthy network makes all trade-offs disappear.

Contracts and state

The following sketch makes the decision boundary concrete. Field names and capacity assumptions are illustrative; adapt them to the stated product contract.

Invariant: confirmed_owner(seat) has at most one value
Replica A: buyer Alice requests seat 7
Replica B: buyer Bob requests seat 7
A <network partition> B
Both local success responses would violate the invariant.

Worked example

A travel app can show cached hotel descriptions during a regional outage while refusing to confirm the last room when the booking authority is unreachable. This is a deliberate degradation policy. The interface should distinguish stale browsing from confirmed booking. Returning a successful-looking booking and hoping to cancel one later changes the contract; it does not preserve the original invariant.

Failure walkthrough

A timeout cannot reliably distinguish a crashed server from a slow or isolated one. Automatically electing independent writers on both sides can cause split brain. Use an authority protocol with clearly defined quorums, terms, and fencing, or explicitly accept conflict resolution. Test clients pinned to the minority side and explain whether they are redirected, rejected, or allowed stale reads.

Figure — Both replicas show one seat → Network divides replicas → Alice and Bob request it → Only authority may confirm → Other side rejects or waits

Decisions and trade-offs

Check your understanding

Can both isolated replicas confirm the final seat and still guarantee that only one buyer owns it?

Transfer to a new scenario

Compare reading an old profile with authorizing a scarce seat during a partition.

Can two isolated replicas both confirm the final seat while preserving the single-owner invariant?

Continue the connection

Study Dealing with Contention and explain which guarantee from this lesson carries into that topic.

Make a decision during a partition

Imagine two regions cannot communicate. A seat is available in both replicas before the partition. If both regions accept a conflicting reservation and promise success, they cannot preserve one linearizable seat history. If only the designated authority accepts writes, some requests on the isolated side must fail or wait. That is the relevant partition-time choice.

CAP consistency means a single-copy, real-time ordering guarantee, not “all validation rules” or the C in ACID. Availability means a successful response for every request to a non-failing node in the theorem’s model, not a monthly uptime percentage. A service can make different choices for different operations: cached descriptions may remain available while seat ownership requires coordination.

Outside a partition there are still latency and consistency tradeoffs. A read replica may lag under normal operation, so saying “we chose CP” does not explain read-your-writes or failover durability. Name the read and write protocol, the required acknowledgements and the permitted stale results.

Figure — A decision worksheet for CAP Theorem: read the mechanism and its guarantee together.

Operational sketch

Partition: region A cannot contact region B
Reserve seat S at A; reserve S at B
Option 1: one authority -> other side rejects/waits
Option 2: both accept -> conflict requiring reconciliation

A tempting mistake

“Pick any two of three” hides the fact that the difficult choice arises when a partition occurs. Quorum overlap alone also does not prove full linearizability without the rest of the protocol.

Transfer exercise

Can a service stay useful during a partition without accepting conflicting purchases?