CAP Theorem for Developers: What It Says and Why PACELC Matters More

On October 21, 2018, GitHub lost the link between its US East Coast network hub and its main East Coast data center for 43 seconds. That was enough. Orchestrator, the tool that manages GitHub’s MySQL topology, promoted new primaries on the West Coast, while a short window of writes had already landed on the East Coast primaries and never left. Each side now held writes the other didn’t have, and GitHub spent 24 hours and 11 minutes in degraded service stitching them back together, because it chose “to prioritize data integrity over site usability and time to recovery.”¹

That’s the CAP theorem with the theory peeled off. When the network splits a distributed system, every node that can still hear requests has to pick: answer and risk being wrong, or refuse and stay right. This post covers what that choice is, what it isn’t, and the other trade-off that costs you far more often: the one you make when the network is fine.

What Does the CAP Theorem Actually Say?

Eric Brewer stated it as a conjecture in his PODC keynote in July 2000.² Seth Gilbert and Nancy Lynch proved it in 2002, and ten years later they restated it in one sentence: “In a network subject to communication failures, it is impossible for any web service to implement an atomic read/write shared memory that guarantees a response to every request.”³

Each letter in that sentence has a narrow meaning, and most CAP arguments are people using different ones.

Consistency means linearizability. Every read sees the most recent completed write, as if there were exactly one copy of the data. It’s not the C in ACID, which is about invariants inside a transaction. Availability means every request that reaches a non-failing node gets a non-error response, with no deadline attached. Partition tolerance means the system keeps its promises even when the network drops any number of messages between nodes.

Here’s the picture I’ll use for the rest of the post. A bank has two branches and one joint account with 500 in it. The branches keep separate ledgers and phone each other before every withdrawal, so both ledgers always agree. Then a backhoe cuts the phone line. Alice walks into branch A and asks for 400. At the same moment Bob walks into branch B and asks for 400. Each teller has exactly two moves: refuse (that’s C) or pay (that’s A). Waiting for the line to come back counts as refusing, just slowly.

Can a System Be CA?

No, not if it runs on more than one machine. You don’t get to opt out of partitions, because the network decides when they happen, not you. Partition tolerance isn’t a feature you pick; it’s the weather.

The “pick two of three” slogan is what makes CA sound like a real option. Brewer himself wrote in 2012 that the “2 of 3” formulation “was always misleading because it tended to oversimplify the tensions among properties.”⁴ A single Postgres box looks CA only because there’s no network inside it to fail. Add one replica and you’re back at the bank, with a phone line that can be cut.

My admitted failure: the first version of this post listed CA as a valid design choice, for systems “in a small, reliable network.” That’s the exact misreading Brewer spent his 2012 paper correcting. It also told you that Spanner stays consistent during partitions thanks to atomic clocks, which is half right and makes the wrong half sound like magic.

What About Spanner, Which Claims to Be Both?

Brewer wrote a whole paper about this in February 2017, by then working at Google.⁵ His answer: Spanner is “technically a CP system.” When a partition cuts a Paxos group’s leader off from its quorum, writes to that group stall, so the minority side loses availability. What Spanner earns is the label “effectively CA,” because its measured availability is better than five 9s and network problems caused under 8% of its incidents.

The interesting part is why. Brewer says TrueTime “does not significantly help achieve CA.” What helps is that every Spanner packet travels over Google’s private network, and each data center typically has at least three independent fibers into it. The clocks buy consistent snapshots and external consistency. The availability comes from owning the cables, which isn’t advice most of us can follow.

So CA is a probability claim, not a design. In Brewer’s 2012 words, “choosing CA should mean that the probability of a partition is far less than that of other systemic failures.”⁴ Unless you run your own fiber, assume the backhoe exists.

What Do the Tellers Do When the Line Goes Dead?

Let’s write the bank down. This is a toy (Python 3, no dependencies), but it runs, and the output below is real.

1
def withdraw(self, account, amount):
2
    if self.line_up:
3
        if amount > self.balance[account]:
4
            raise ValueError("insufficient funds")
5
        self.balance[account] -= amount
6
        self.peer.balance[account] -= amount   # synchronous: both ledgers or neither
7
        return amount
8
    if self.mode == "CP":
9
        raise Unavailable("can't reach the other branch, come back later")
10
    if self.mode == "BOUNDED":
11
        paid = sum(a for acc, a in self.pending if acc == account)
12
        if paid + amount > self.limit:          # limit = 200 per branch
13
            raise Unavailable(f"offline limit is {self.limit}")
14
    self.balance[account] -= amount            # AP: pay now, reconcile later
15
    self.pending.append((account, amount))
16
    return amount

Cut the line, send Alice to branch A and Bob to branch B, have each ask for 400 and settle for 200, then reconnect and replay the pending withdrawals on both sides:

CP       Alice refused 400: can't reach the other branch, come back later
CP       Bob refused 400: can't reach the other branch, come back later
CP       balance after the line comes back: 500
AP       Alice gets 400
AP       Bob gets 400
AP       balance after the line comes back: -300
BOUNDED  Alice refused 400: offline limit is 200
BOUNDED  Alice gets 200
BOUNDED  Bob refused 400: offline limit is 200
BOUNDED  Bob gets 200
BOUNDED  balance after the line comes back: 100

(I trimmed the CP retries at 200, which fail the same way.) The CP branches keep the books perfect and serve nobody. The AP branches serve everybody and leave the bank chasing 300 it doesn’t have.

The third mode is the useful one, and it comes straight from Brewer’s 2012 paper. ATMs really work this way: during a partition they keep dispensing cash, but only up to some limit k, “where k might be $200.” The invariant (balance never below zero) holds as long as the limit times the number of branches stays under the balance, and whatever slips through gets fixed afterward with compensation, like an overdraft fee. Brewer’s recipe has three steps: detect the partition, enter an explicit partition mode that limits some operations, and run recovery when the line comes back.⁴

That’s the part the “pick two” slogan hides. You don’t choose C or A once, for the whole database. You choose per operation, and you can choose something in between.

Is DynamoDB an AP Database?

Mostly no, and the confusion comes from the name. The 2007 Dynamo paper describes an internal Amazon store built for the shopping cart, where “an ‘Add to Cart’ operation can never be forgotten or rejected.”⁶ Dynamo used sloppy quorums, hinted handoff, and vector clocks, and it merged conflicting carts on read. The paper admits the cost in one line: “deleted items can resurface.” Its common setting was N=3 replicas, R=2, W=2. That’s AP thinking all the way down.

DynamoDB, the AWS service launched in 2012, is a different system. Its 2022 paper says the team combined Dynamo’s scalability with SimpleDB’s consistency.⁷ Each partition is a replication group spread across Availability Zones, run by Multi-Paxos, and “only the leader replica can serve write and strongly consistent read requests.” Eventually consistent reads can come from any replica. Cut the leader off and writes for that partition wait for a new one: that’s the CP side of the counter.

Inside one Region you choose per read. Across Regions, AWS turned the CAP choice into a flag you set once:

1
import boto3
2

3
ddb = boto3.client("dynamodb", region_name="us-east-2")
4

5
# eventual is the default; strong costs twice the read capacity
6
ddb.get_item(TableName="accounts", Key={"id": {"S": "joint"}}, ConsistentRead=True)
7

8
# MRSC: the table must be empty, and the mode can never be changed afterward
9
ddb.update_table(
10
    TableName="accounts",
11
    ReplicaUpdates=[{"Create": {"RegionName": "us-east-1"}}],
12
    GlobalTableWitnessUpdates=[{"Create": {"RegionName": "us-west-2"}}],
13
    MultiRegionConsistency="STRONG",
14
)

The default for global tables is multi-Region eventual consistency (MREC): replication is asynchronous, usually under a second, and concurrent writes to the same item are resolved by “last writer wins.”⁸ Multi-Region strong consistency (MRSC) replicates every write synchronously to another Region before acknowledging it, needs exactly three Regions (or two plus a witness), and doesn’t support transactions or TTL.⁹ One is the AP teller, the other is the CP teller, and AWS makes you decide at creation time. I like that. It forces the conversation before launch instead of during the incident.

How Does Cassandra Let You Tune It?

Cassandra descends from the Dynamo paper and keeps the per-request dial. Every write goes to all replicas; the consistency level only decides how many acknowledgments the coordinator waits for. If the replicas you write to and the replicas you read from overlap (W + R > RF), reads see acknowledged writes.¹⁰

1
-- cqlsh, RF = 3: wait for 2 of 3 replicas on both reads and writes
2
CONSISTENCY QUORUM;
3
SELECT balance FROM accounts WHERE id = 'joint';
4

5
-- compare-and-set runs Paxos under the hood; keep it for the writes that can't race
6
UPDATE accounts SET balance = 100 WHERE id = 'joint' IF balance = 500;

With RF=3 and QUORUM, the side of a partition holding one replica can’t serve that key, so you’ve picked the CP teller. Drop to ONE and you get the AP teller back. The IF clause is a lightweight transaction, and the Cassandra docs warn it carries “a non-negligible performance cost, because Paxos is used.”¹¹ Even QUORUM on both sides doesn’t give you full linearizability by Gilbert and Lynch’s definition, as Daniel Abadi points out, but it’s close enough for most data that isn’t money.

Why Should You Stop Calling Databases CP or AP?

Martin Kleppmann made this case in May 2015, and it still holds.¹² Take the most common setup in the world: one leader, asynchronous followers. Clients cut off from the leader can’t write, so it isn’t CAP-available. Reads from a lagging follower can be stale, so it isn’t CAP-consistent either. By the strict definitions it’s neither, “just P.” Kleppmann shows the same for ZooKeeper’s default settings.

There’s a second problem. CAP models exactly one fault, a lost message. Nodes crash and disks fill up. A long GC pause looks exactly like a partition from the outside. Gilbert and Lynch note that a node can’t tell a lost message from a slow one, so a system can serve a wrong answer “despite the lack of partitions.”³ Every partition detector is a timeout, and every timeout is a guess.

So label operations, not products. DynamoDB’s eventually consistent read and its strongly consistent read hit the same table and land on opposite sides of CAP. Spanner’s snapshot reads keep working on both sides of a partition while its writes stall.⁵ “Postgres is CP” tells you nothing until you know whether replication is synchronous and where the reads go (the trade-offs between statement, WAL, logical, and trigger-based replication matter more here than the brand on the box).

CAP vs PACELC: What Happens When the Network Is Fine?

Partitions are rare. Latency happens on every request. Daniel Abadi turned that into PACELC in February 2012: “if there is a partition (P), how does the system trade off availability and consistency (A and C); else (E), when the system is running normally in the absence of partitions, how does the system trade off latency (L) and consistency (C)?”¹³

Abadi’s argument is that the ELC half explains more real designs than CAP does. Back to the bank on a normal day: if every withdrawal waits for a phone call to the other branch, every customer pays for that call, outage or not. Brewer does the back-of-the-envelope math for Spanner: light needs about 10 ms to cover 1,000 miles, and no clever clock beats the speed of light.⁵ Abadi’s point is that Dynamo-style stores weaken consistency mostly to avoid that round trip, not because CAP forced them to.

The first three rows are Abadi’s 2012 classification, and the last three follow from the Brewer paper and AWS docs cited above. PNUTS is the odd one: it gives up consistency on a normal day for speed, then gives up availability during a partition. That’s a legitimate pair of choices, and CAP alone can’t even describe it.

How Should You Use CAP When Designing a System?

Start with the operations, not the database. For each write path, ask what a node should do when it can’t reach the others. Adding to a cart: answer, merge later. Debiting a balance: refuse, or bound it the way the ATM does. Incrementing a like counter: answer, and use a counter that merges cleanly instead of last-writer-wins, because LWW quietly throws away one of the two writes. That’s fine for a profile picture and a disaster for money.

Then write the recovery plan before you need it. GitHub’s failover tooling made an availability choice (promote the West Coast) that the business didn’t want when it saw the result (integrity first), and the cleanup took a day. Decide which side of a split keeps taking writes, how the other side’s writes get replayed, and who gets paged to approve it. Then rehearse it: AWS Fault Injection Service can isolate a global-table Region on purpose, which beats discovering your answer at 22:52 UTC on a Sunday.⁹

Next time someone in a design review says “we’re AP,” ask two things: for which operation, and what happens to the writes on the losing side? If nobody knows, your failover script will decide for you.