Reading CAP and PACELC Correctly: Why "Pick 2 of 3" Is Wrong

Version note: The code in this post was built and run with C# 14 and .NET 10.

Guess First

Bookstore's data is replicated on three nodes (A, B, C). One day the link between C and the other two breaks: a network partition. Ada's phone is connected to C, her laptop to A. From the phone Ada adds a book to her cart, from the laptop she removes another book from the cart, and then she proceeds to payment on the phone.

Should the cart work during this time? The payment? Which books are in the cart once the partition is over? In an architecture meeting someone says "our system is AP (Available, Partition-tolerant), so both will work", or "our database is CP (Consistent, Partition-tolerant), so both will stop". Why are both statements incomplete?

A Short History of CAP

In his keynote at the PODC (Principles of Distributed Computing) conference in 2000, Eric Brewer put forward a conjecture: a web service that holds shared data cannot provide consistency, availability and partition tolerance all at once. Two years later Seth Gilbert and Nancy Lynch stated it with precise definitions and proved it in "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services". What we call the CAP (Consistency, Availability, Partition tolerance) theorem today is that proof, not Brewer's intuition. And the proof's definitions are much narrower than the everyday words.

The Precise Statement

In Gilbert and Lynch's definitions, C is the linearizability from the previous post (called "atomic consistency" in the paper): all operations can be arranged into a single order and each appears to happen at a single instant. A means every request received by a non-failing node in the system eventually produces a response; how long the response takes is not part of the definition, but "I refuse" does not count as a response. P means the network may lose arbitrarily many messages between nodes.

The theorem says: in an asynchronous network where messages can be lost, no algorithm provides both C and A. The idea of the proof fits in a few sentences. Split the network into two parts with no messages passing between them. A client writes to a node in the first part; by A, that node must accept the write and respond. Then a client reads from a node in the second part; by A, that node must respond too. But it cannot know about the write, because every message in between was lost. If it returns the old value, C is broken; if it does not respond, A is broken.

Why "Pick 2 of 3" Is Wrong

CAP is usually drawn as a triangle and systems are labeled CA (Consistent, Available), CP or AP. This summary has three problems.

First, P is not a choice. A partition is something that happens to the system: a switch failure, a wrong firewall rule, a node that misses heartbeats because of a long GC (garbage collector) pause. A system spread over several machines cannot choose "not to tolerate partitions"; the only thing it can choose is what to do when one happens. A "CA system" describes either a system running on a single machine or a system whose behavior during a partition is undefined.

Second, the choice is made only during a partition. Without a partition a system can be both linearizable and available; CAP says nothing about those times. Brewer stressed this himself in "CAP Twelve Years Later: How the 'Rules' Have Changed", published in IEEE (Institute of Electrical and Electronics Engineers) Computer in 2012: the "two of three" formulation is misleading, because partitions are rare and there is no reason to give up C or A when there is no partition.

Third, the choice is not made once for the whole system. The same system can choose C for some operations and A for others; the same database can run with different settings per request. That is why in his 2015 post "Please stop calling databases CP or AP" Kleppmann suggested dropping these labels altogether: many real systems provide neither C nor A in the CAP sense.

What CAP Does Not Say

Because CAP's definitions are narrow, so are its conclusions. The theorem says nothing about latency: the definition of A has no time bound, while in practice an answer that takes 30 seconds is no different from no answer. It says nothing about partial availability: during a partition the nodes on the majority side can stay linearizable and keep answering, with only the minority side refusing; in the CAP sense that counts as "not available", yet for most users the system works. It says nothing about models other than linearizability: causal consistency or read committed, which we saw on the map in the previous post, can be provided during a partition. And it talks about a single register; transactions, multiple keys and other kinds of failure (node crashes, disk loss) are out of scope.

So CAP should be read not as a classification tool but as an impossibility result: "if you want linearizability, accept that you cannot answer some requests during a partition". The rest is design, and those decisions are made operation by operation.

Deciding in Bookstore: Cart and Payment

Let us build the opening scenario. There are three nodes; Isolate cuts one node off from the others. The cart always answers, and once the partition is over the replicas are reconciled, as described in the Dynamo paper, by taking the union of the divergent versions. A payment is recorded only when a majority of nodes can be reached:

namespace Bookstore.Cap;

public sealed class Node(string name)
{
    public string Name { get; } = name;
    public HashSet<string> Cart { get; set; } = [];
    public List<string> Payments { get; } = [];
}

public sealed class Cluster
{
    private readonly HashSet<string> _isolated = [];

    public List<Node> Nodes { get; } = [new("A"), new("B"), new("C")];

    public void Isolate(string node) => _isolated.Add(node);
    public void Heal() => _isolated.Clear();

    // Nodes on the same side of the partition as "from"
    public List<Node> Reachable(string from) =>
        [.. Nodes.Where(n => _isolated.Contains(n.Name) == _isolated.Contains(from))];
}

// AP: every node answers; replicas are reconciled after the partition heals
public sealed class CartService(Cluster cluster)
{
    public void Add(string via, string book) => cluster.Reachable(via).ForEach(n => n.Cart.Add(book));
    public void Remove(string via, string book) => cluster.Reachable(via).ForEach(n => n.Cart.Remove(book));
    public string Show(string via) => string.Join(", ", cluster.Reachable(via)[0].Cart.Order());

    // Dynamo-style reconciliation: union of the divergent versions
    public void Reconcile()
    {
        HashSet<string> union = [.. cluster.Nodes.SelectMany(n => n.Cart)];
        cluster.Nodes.ForEach(n => n.Cart = [.. union]);
    }
}

// CP: a payment is recorded only with a majority of replicas
public sealed class PaymentService(Cluster cluster)
{
    public string Charge(string via, string orderId)
    {
        List<Node> reachable = cluster.Reachable(via);
        int majority = cluster.Nodes.Count / 2 + 1;
        if (reachable.Count < majority)
        {
            return $"503 no quorum ({reachable.Count}/{cluster.Nodes.Count})";
        }
        reachable.ForEach(n => n.Payments.Add(orderId));
        return $"201 charged {orderId} on {string.Join(",", reachable.Select(n => n.Name))}";
    }
}

using Bookstore.Cap;

Cluster cluster = new();
CartService cart = new(cluster);
PaymentService payments = new(cluster);

cart.Add("A", "ddia");
cart.Add("A", "clean-code");
Console.WriteLine($"before partition : {cart.Show("A")}");

cluster.Isolate("C");                       // network partition: {A, B} | {C}
cart.Add("C", "refactoring");               // Ada's phone talks to C
cart.Remove("A", "clean-code");             // Ada's laptop talks to A
Console.WriteLine($"during, via A    : {cart.Show("A")}");
Console.WriteLine($"during, via C    : {cart.Show("C")}");
Console.WriteLine($"payment via C    : {payments.Charge("C", "order-1042")}");
Console.WriteLine($"payment via A    : {payments.Charge("A", "order-1042")}");

cluster.Heal();
cart.Reconcile();
Console.WriteLine($"after reconcile  : {cart.Show("A")}");

before partition : clean-code, ddia
during, via A    : ddia
during, via C    : clean-code, ddia, refactoring
payment via C    : 503 no quorum (1/3)
payment via A    : 201 charged order-1042 on A,B
after reconcile  : clean-code, ddia, refactoring

During the partition both sides answered for the cart and the carts diverged: only ddia on A's side, three books on C's side. The payment was refused on C's side (minority, 1/3) and accepted on A's side. Ada's phone showed an error, but the same order was not paid twice on two different sides; for payment that is the right decision. For the cart, availability is the right choice: a customer who cannot add a book to the cart is a lost sale.

But look at the result of the reconciliation: clean-code, which Ada removed, came back. A union never loses adds, but it does not recognize removes either. The Dynamo paper states this behavior openly: for Amazon, losing an "add to cart" is worse than a removed item reappearing in the cart, so it was accepted deliberately. Choosing AP does not mean "everything works"; it means designing the semantics of reconciliation after the partition. In the eleventh post we will rewrite the same cart with a CRDT (Conflict-free Replicated Data Type) that merges removes correctly too.

PACELC: There Is a Choice Without a Partition Too

CAP's biggest gap is that it says nothing about the state systems spend most of their time in: normal operation without partitions. Daniel Abadi completed the picture with PACELC (if Partition: Availability or Consistency, Else: Latency or Consistency) in "Consistency Tradeoffs in Modern Distributed Database System Design", published in IEEE Computer in 2012: if there is a partition (P), choose between availability (A) and consistency (C); else (E), choose between latency (L) and consistency (C). The second choice is made every day, on every request: if you wait for replicas in other regions to acknowledge a write, you gain consistency and pay in latency.

To estimate the cost roughly, consider a setup with the leader in Frankfurt and replicas in Dublin and Istanbul. The round-trip times are assumptions; these are numbers you should measure in your own environment:

namespace Bookstore.Cap;

// The "else" branch of PACELC: no partition, but every acknowledgement costs a round trip
public static class Latency
{
    public static void Print()
    {
        // assumed round-trip times from the leader in Frankfurt, in ms
        Dictionary<string, double> rtt = new() { ["frankfurt"] = 0, ["dublin"] = 25, ["istanbul"] = 45 };
        double local = 1; // local disk write

        double[] sorted = [.. rtt.Values.Order()];
        int majority = rtt.Count / 2 + 1;
        Console.WriteLine($"EL  ack after local write   : {local} ms, followers lag behind");
        Console.WriteLine($"EC  ack after majority {majority}/{rtt.Count}  : {local + sorted[majority - 1]} ms");
        Console.WriteLine($"EC  ack after all replicas  : {local + sorted[^1]} ms");
    }
}

EL  ack after local write   : 1 ms, followers lag behind
EC  ack after majority 2/3  : 26 ms
EC  ack after all replicas  : 46 ms

Acknowledging after the local write takes 1 millisecond, but if the leader crashes at that moment the write may be lost, and readers on followers see the old value. Waiting for a majority takes 26 milliseconds and protects the write against the loss of one node. Waiting for all of them takes 46 milliseconds and puts the slowest region on the critical path of every write. This difference is paid on every write, partition or not. That is Abadi's point: the main reason many systems give up consistency is not CAP but latency in normal operation.

These letters label systems along two axes: PA (availability) or PC (consistency) during a partition, EL (latency) or EC (consistency) in normal operation. In the paper, with their default settings in 2012, Dynamo, Cassandra and Riak are classified as PA/EL; fully ACID (Atomicity, Consistency, Isolation, Durability) systems such as VoltDB/H-Store and Megastore as PC/EC; MongoDB as PA/EC; and Yahoo's PNUTS (Platform for Nimble Universal Table Storage) as PC/EL. Read these labels as an illustration of the reasoning, not as statements about today's versions of these systems.

Same Database, Different Letters

Another reason the labels mislead is that modern databases leave this decision to configuration, even to the individual request. In Cassandra one read on a table can use the ONE consistency level (the fastest replica's answer) while another uses QUORUM; the first behaves close to PA/EL, the second close to PC/EC. In MongoDB the writeConcern, readConcern and readPreference settings let you choose, on the same collection, between a fast but stale read from a secondary and a majority-acknowledged, linearizable read. In a SQL (Structured Query Language) Server availability group a synchronous-commit replica is on the EC side and an asynchronous-commit replica on the EL side; a report query sent to a readable secondary may additionally see stale data.

The practical consequence: "our database is CP" carries no information unless you say with which settings and for which operation. The right questions, for each operation, are: during a partition, should this operation be refused or answered with stale data? In normal operation, how many milliseconds are we willing to pay for it? Roughly, for Bookstore: payment, stock decrements and coupon redemption are PC/EC; the cart, product reviews and recommendations are PA/EL; catalog prices are EL on the read side and EC on the side that writes price changes. The upcoming System Design series will use this post as exactly that kind of decision lens in "Scaling the Data Layer: Replication, Sharding and SQL vs NoSQL".

Common Pitfalls

Labeling a database with a single letter. Statements like "MongoDB is AP" or "PostgreSQL is CA" ignore both the configuration and CAP's definitions. Talk about guarantees at the level of operations and settings.

Choosing "CA". A system distributed over a network cannot refuse partitions. The behavior of a system designed as "CA" during a partition is undefined and usually means both break.

Confusing CAP with a latency argument. When a team says "we chose eventual consistency because of CAP", the real reason is usually latency in PACELC's E branch. Saying so explicitly also makes clear when the decision should be revisited.

Choosing AP without designing reconciliation. When the partition is over, who merges the divergent data, and how? LWW (last-write-wins), union, asking the user? If this question has no answer, AP means silent data loss.

Confusing availability in the CAP sense with availability in the business sense. An SLA (Service Level Agreement) percentage is not the A in CAP. A CP system whose majority side keeps working can have high availability from a business point of view.

A Small Experiment

★☆☆ In the simulation, call Isolate("A") instead of Isolate("C"). On which side of the partition is Ada's phone (C) this time? On which side is the payment accepted, and what does the cart show after the partition? Why does it matter to distinguish the two sides as "majority" and "minority"?

★★☆ Add a fourth replica to Latency (Virginia, 90 ms). How many nodes is a majority now, and what is the latency of a majority acknowledgement? Explain the case where adding a replica does not lower write latency, or even raises it.

★★★ Write a reconciliation for CartService that keeps a version vector for every add and remove: a book removed on one side and untouched on the other must stay removed, but a book added concurrently on both sides must not count as added twice. Why is writing the reconciliation rules harder than you expect?

In this post we saw that during a partition some nodes must refuse to answer. But the question "which nodes are the majority, who is the leader?" itself requires agreement. In the next post we give that agreement its name: consensus, the FLP (Fischer, Lynch and Paterson) impossibility result, and how Raft does leader election and log replication.