CAP Theorem Explained: CP vs AP When the Network Splits

The CAP theorem is usually quoted as "consistency, availability, partition tolerance: pick two". That slogan is the source of most wrong interview answers about it. You do not get to pick two out of three, because a network partition is not something you choose. The real statement is narrower and more useful: when the network splits, each node must either refuse to answer or risk answering wrongly.

The problem it solves

Any system that keeps copies of data on several machines must decide what happens when they cannot talk to each other. Links fail and switches reboot, yet clients can still reach some node and ask it to read or write.

CAP, conjectured by Eric Brewer and proved in 2002 by Seth Gilbert and Nancy Lynch, pins down the three properties in play:

• Consistency: every read sees the most recent write, as if there were a single copy. This is linearizability, a much stronger meaning than the "C" in ACID.
• Availability: every request that reaches a working node gets a non-error answer.
• Partition tolerance: the system keeps operating while messages between nodes are lost.

During a partition you cannot have the first two at once. A node cut off from its peers cannot know whether they accepted a newer write: if it answers, it may be wrong; if it must be right, it cannot answer.

The intuition

Split the choice into two situations.

No partition. Every node reaches every other one, writes are agreed and replicated, and CAP forces nothing. You still pay latency, because agreeing takes round trips. That second trade-off is what the PACELC formulation adds: if partitioned, availability or consistency; else, latency or consistency.

A partition. Now each node on the smaller side has to decide:

• CP, consistent under partition: refuse. The minority side stops accepting writes, and strictly also reads, until it can reach a majority again. Users routed there see errors, but no one ever sees two different truths.
• AP, available under partition: answer from what you know. Both sides keep accepting writes. Everyone gets a response, and the two sides drift apart. When the link heals, the system has to reconcile the conflicting histories, by last-writer-wins, by merging, or by handing both versions to the application.

The usual tool on the CP side is a quorum. With N replicas, a write needs W acknowledgements and a read consults R replicas. If R + W > N, every read set overlaps every write set, so a read always touches at least one copy with the latest write. A side of the partition that holds a strict majority can keep going; the other side cannot, and that is exactly the refusal CP describes.

The right choice depends on the data. For a like count, a brief disagreement costs nothing. For a bank balance, two sides approving the same money is a loss, not a rounding error.

Watch it run

The animation starts with four nodes and one shared catalogue: every node reachable, every copy agreeing on v7. A write arrives, is agreed, and reaches all four, so the cluster is consistent and available; with no partition you get both, and CAP forces nothing yet. Then the link drops, and the cluster is two groups that cannot reach each other: A, B and C, and D alone. A, B and C still hold a quorum, so that side can keep accepting writes safely. In the CP version, node D is in the minority, so it refuses the write rather than diverge: correct, and unavailable, since those users are down until the link returns. In the AP version, the same partition gets the other answer, and D accepts the write from what it knows. The cluster is available and now divergent, with two sides believing different things. The last copy was promised twice, which is fine for a like count and a loss for a balance. When the partition heals and the two sides talk again, CP catches the minority up, while AP hands your application the conflict to resolve. You chose which, in advance.

The code

A toy model, not a real database: one replicated value, a partition into groups, and the two policies. Each node keeps the list of writes it accepted; healing either catches everyone up to a single history or reports a conflict:

class ToyCluster:
    """Toy model of one replicated value during a partition, not a real database."""
    def __init__(self, nodes, mode):
        self.mode = mode                                   # "CP" or "AP"
        self.log = {n: ["v8"] for n in nodes}              # accepted writes, per node
        self.groups = [set(nodes)]                         # who can reach whom

    def split(self, *groups):
        self.groups = [set(g) for g in groups]

    def _side(self, node):
        side = next(g for g in self.groups if node in g)
        return side, 2 * len(side) > len(self.log)         # (reachable nodes, has quorum?)

    def write(self, node, value):
        side, quorum = self._side(node)
        if self.mode == "CP" and not quorum:
            return "refused"                               # refuse rather than diverge
        for n in side:
            self.log[n] = self.log[n] + [value]
        return "ok"

    def read(self, node):
        side, quorum = self._side(node)
        if self.mode == "CP" and not quorum:
            return "refused"                               # it might be stale
        return self.log[node][-1]

    def heal(self):
        self.groups = [set(self.log)]
        logs = list(self.log.values())
        longest = max(logs, key=len)
        if all(longest[:len(l)] == l for l in logs):       # one history: just catch up
            for n in self.log:
                self.log[n] = list(longest)
            return "caught up", longest[-1]
        return "conflict", sorted({l[-1] for l in logs})   # two histories: yours to resolve

The animation's partition, played under both policies:

cp = ToyCluster("ABCD", "CP")
cp.split("ABC", "D")
print(cp.write("A", "v9"), cp.write("D", "v9b"))   # ok refused
print(cp.read("B"), cp.read("D"))                  # v9 refused
print(cp.heal(), cp.read("D"))                     # ('caught up', 'v9') v9

ap = ToyCluster("ABCD", "AP")
ap.split("ABC", "D")
print(ap.write("A", "v9"), ap.write("D", "v9b"))   # ok ok
print(ap.read("B"), ap.read("D"))                  # v9 v9b
print(ap.heal())                                   # ('conflict', ['v9', 'v9b'])

The quorum rule, checked by brute force over every pair of read and write sets, and the model over 3,000 random partitions and write patterns: CP never ends in a conflict and accepts exactly the writes from a majority side, while AP accepts everything and conflicts exactly when both sides wrote:

from itertools import combinations

def always_overlap(n, w, r):
    return all(set(a) & set(b)
               for a in combinations(range(n), w)
               for b in combinations(range(n), r))

print(always_overlap(3, 2, 2), always_overlap(4, 2, 2))   # True False

import random

random.seed(19)
ok = True
for n in range(1, 7):                              # quorum rule by brute force
    for w in range(1, n + 1):
        for r in range(1, n + 1):
            ok &= always_overlap(n, w, r) == (r + w > n)
for _ in range(3000):                              # random partitions and writes
    nodes = "ABCDEF"[:random.randint(2, 6)]
    cut = random.randint(1, len(nodes) - 1)
    shuffled = random.sample(nodes, len(nodes))
    left, right = shuffled[:cut], shuffled[cut:]
    writers = [random.choice(nodes) for _ in range(random.randint(1, 6))]
    for mode in ("CP", "AP"):
        c = ToyCluster(nodes, mode)
        c.split(left, right)
        results = [c.write(w, f"w{k}") for k, w in enumerate(writers)]
        sides_written = {w in left for w, res in zip(writers, results) if res == "ok"}
        status, _ = c.heal()
        if mode == "CP":
            ok &= len(sides_written) <= 1 and status == "caught up"
            ok &= all((res == "ok") == (2 * len(left if w in left else right) > len(nodes))
                      for w, res in zip(writers, results))
        else:
            ok &= all(res == "ok" for res in results)
            ok &= (status == "conflict") == ({w in left for w in writers} == {True, False})
print(ok)                                          # True

The complexity

The costs are round trips and outages, not steps:

• CP: every write waits for a majority to acknowledge, so write latency follows the slower replicas. During a partition, the minority side is down; if no side holds a majority, as with an even split, everyone is down.
• AP: writes return after a local acknowledgement. The bill arrives later as reconciliation logic and stale reads.

Where it goes wrong

• "Pick two of three." You cannot drop partition tolerance in a distributed system; the network decides when partitions happen.
• Labelling whole products CP or AP. Many systems let you choose per request, for example by setting read and write quorum sizes.
• Confusing CAP consistency with ACID consistency. One is about replicas agreeing; the other is about constraints holding inside a transaction.
• Choosing AP for money. Eventual consistency is a poor fit wherever two sides approving the same thing is a loss.

When it shows up in interviews

It comes up inside most system design questions as "what if a data centre loses connectivity?", in a URL shortener, a chat app or a payment service. Interviewers listen for the partition framing, a choice justified by the data, and awareness of quorums. The data-placement side of the same designs is covered in consistent hashing.

How to say it in an interview

"CAP only forces a choice during a network partition. Then a node that cannot reach its peers either refuses, which keeps every answer correct but makes that side unavailable, or answers from what it has, which stays available but lets the sides diverge and needs reconciliation afterwards. With quorums where reads plus writes exceed the replica count, the majority side can keep going and the minority refuses. I would choose per piece of data: balances and inventory lean consistent, counters and feeds lean available. And when there is no partition, the trade-off is latency against consistency."