CAP Precisely: Network Partitions Force a Consistency-or-Availability Choice for Conflicting Operations

Learning outcomes

AtlasMart has one physical unit of a limited-edition product left. The inventory record is replicated between two sites so shoppers can continue ordering during failures. A link failure now isolates the sites. If both sides keep accepting reservations, the store may sell the same final unit twice; if one side refuses, some customers receive an error even though a local replica is running. This is the narrow but important shape of the CAP problem.

1. State the CAP model before using the acronym

The theorem formalized by Seth Gilbert and Nancy Lynch studies a replicated service in an asynchronous network. In the simplified register view used here, consistency means behavior compatible with one up-to-date copy—commonly explained using linearizability. Linearizability requires each completed operation to appear to take effect at one instant between invocation and response while respecting real-time order. Availability means every request received by a non-failing node eventually receives a response. A network partition means messages between some groups of nodes can be lost indefinitely.

Those definitions are intentionally stronger and narrower than everyday uses of the words. “Available” here is not your monthly uptime percentage. “Consistency” here is not the C in ACID and is not simply “replicas converge eventually.” The theorem says that while a partition prevents the replicas from exchanging the information needed to establish a single current value, you cannot promise both linearizable behavior and a successful response for every request.

2. The two-replica timeline: why the choice appears

Start with replicas East and West both storing stock = 1. A network partition isolates them. Shopper A reaches East and Shopper B reaches West. Neither side can learn what the other is doing before it must decide whether to answer.

The point is not that every available system must literally oversell inventory. The point is that if both sides must remain able to accept arbitrary conflicting updates without communication, the service cannot simultaneously promise a single real-time order for those updates. A design can change the operation, partition the invariant, pre-allocate rights, or compensate later—but those are changes to the problem, not counterexamples to the theorem.

3. Availability-first: a successful ACK can still encode a conflict

Suppose AtlasMart prioritizes write availability and permits both replicas to accept the reservation. Each local state transition is internally sensible: 1 → 0. The failure appears in the history: two independent clients were told they reserved the only item. Reconciliation later cannot make both promises true without an explicit conflict rule or business compensation.

partition starts
A -> East: reserve sku-42
East -> A: 200 OK, reservation=R-A
B -> West: reserve sku-42
West -> B: 200 OK, reservation=R-B
partition heals
reconciliation: physical stock was 1, acknowledged reservations are 2

Notice the evidence that matters: the two acknowledgements and the physical invariant. Merely showing that replicas eventually converge to the same integer does not prove that the business history was correct.

4. Consistency-first: refusing work can be the correct result

A linearizability-first design must avoid letting both isolated sides behave as authoritative writers for the same register. Real systems may use a leader elected by consensus, a majority quorum, a lease with fencing, or another ownership mechanism. During a partition, the side that cannot establish authority must reject, wait, or otherwise fail the operation. That loss of availability is not a bug if the invariant demands a single accepted ordering.

5. Controlled failure: the “active-active last item” mistake

A common production mistake is to replicate a record to two writable regions, configure routing so both regions continue serving during isolation, and then assume “replication” itself prevents oversell. Replication transports state; it does not invent a conflict-free meaning for two concurrent decrements. Last-write-wins can make the replicas converge while silently discarding one write, which is still wrong if both customers received durable success.

The repair starts with the invariant. For a scarce counter you can choose a single owner, a linearizable conditional mutation, or an escrow-style design that pre-allocates independent reservation rights to regions. If the business allows back-ordering or compensation, an availability-first design can be valid—but that changed tolerance must be explicit.

6. AtlasMart lab — simulate both sides of the tradeoff

The lab is deterministic Python using only the standard library. It does not create sockets, modify your firewall, or pretend to be a consensus implementation. Its purpose is to make the client-visible history and per-replica state mechanically repeatable.

from dataclasses import dataclass

@dataclass
class Replica:
    name: str
    stock: int = 1
    version: int = 0


def ap_reserve(replica, order_id):
    # Availability-first during a partition: each side answers locally.
    if replica.stock <= 0:
        return f"{replica.name}: REJECT {order_id} (sold out)"
    replica.stock -= 1
    replica.version += 1
    return f"{replica.name}: ACK {order_id} -> stock={replica.stock}, v={replica.version}"


def cp_reserve(replica, order_id, has_authority):
    # Linearizable register-style policy: the side without authority must refuse.
    if not has_authority:
        return f"{replica.name}: UNAVAILABLE {order_id} (cannot prove single-writer authority)"
    if replica.stock <= 0:
        return f"{replica.name}: REJECT {order_id} (sold out)"
    replica.stock -= 1
    replica.version += 1
    return f"{replica.name}: ACK {order_id} -> stock={replica.stock}, v={replica.version}"

print("=== availability-first under partition ===")
east, west = Replica("east"), Replica("west")
print(ap_reserve(east, "order-A"))
print(ap_reserve(west, "order-B"))
print("partitioned states:", east, west)
print("merge fact: two reservations were acknowledged from one physical item")

print("\n=== linearizability-first under partition ===")
east, west = Replica("east"), Replica("west")
print(cp_reserve(east, "order-A", has_authority=True))
print(cp_reserve(west, "order-B", has_authority=False))
print("partitioned states:", east, west)

Expected output

=== availability-first under partition ===
east: ACK order-A -> stock=0, v=1
west: ACK order-B -> stock=0, v=1
partitioned states: Replica(name='east', stock=0, version=1) Replica(name='west', stock=0, version=1)
merge fact: two reservations were acknowledged from one physical item

=== linearizability-first under partition ===
east: ACK order-A -> stock=0, v=1
west: UNAVAILABLE order-B (cannot prove single-writer authority)
partitioned states: Replica(name='east', stock=0, version=1) Replica(name='west', stock=1, version=0)

Verification checklist

• The availability-first branch returns two acknowledgements from one initial unit.
• The linearizability-first branch returns one acknowledgement and one explicit unavailable result.
• No conclusion depends on wall-clock timing, threads, real packets, or probabilistic scheduling.
• You can identify which property is sacrificed in each branch and which business invariant motivates the decision.

7. Production judgment

Apply CAP at the granularity of a concrete operation and invariant. Ask which nodes must communicate, which histories are acceptable, and what clients are promised when that communication fails. Do not stamp an entire technology “CP” or “AP” and stop reasoning. Monitor rejected operations, authority/term changes, replication lag, conflict counts, and client retries; test real partition and asymmetric-reachability scenarios in an isolated environment before relying on failover behavior.

This chapter uses no database product, cloud service, or proprietary feature. The lab was executed with Python 3.13.5 on Linux and uses only standard-library constructs. The next lesson explains why the same system can provide both consistency and availability in healthy operation and why “pick two” is therefore a misleading everyday summary.

Authoritative references

• Gilbert & Lynch — Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services — formal CAP framing and proof in the asynchronous network model
• Herlihy & Wing — Linearizability: A Correctness Condition for Concurrent Objects — foundational definition of linearizability and real-time operation ordering
• Amazon Dynamo paper — a concrete availability-oriented design with versioning and conflict resolution under failures