CAP Theorem and PACELC

The CAP theorem states that a replicated data store cannot simultaneously guarantee linearizable consistency and availability while a network partition is in progress. It was conjectured by Eric Brewer and proved by Gilbert and Lynch. The theorem is narrow: its terms have specific formal meanings that differ from everyday usage, and it says nothing about behavior when the network is healthy.

Definitions

• Consistency (C). Every read returns the value of the most recent completed write. Formally this is linearizability: operations appear to take effect atomically at a single point between invocation and response. It is not the "C" of ACID. See consistency models.
• Availability (A). Every request received by a non-failing node must eventually produce a non-error response. The response need not contain the latest write. Availability in CAP applies to every non-failed node, not to the system as a whole.
• Partition tolerance (P). The system continues to operate despite the network dropping or delaying an arbitrary number of messages between nodes. A network partition splits nodes into groups that cannot communicate with each other.

Why the trade-off exists

Consider two replicas, N1 and N2, that are partitioned from each other. A client writes x = 2 to N1. Another client then reads x from N2.

sequenceDiagram
    participant W as Client A
    participant N1 as Node N1
    participant N2 as Node N2
    participant R as Client B
    Note over N1,N2: network partition, replication messages lost
    W->>N1: write x = 2
    N1-->>W: ok
    R->>N2: read x
    Note over N2: options: return stale x = 1 (gives up C) or refuse (gives up A)

N2 cannot know whether a newer write exists. It has two choices:

1. Return its local value x = 1. The system stays available but the read is stale, so it is not linearizable.
2. Return an error or block until the partition heals. The system stays consistent but N2 is not available.

No third option exists, because N2 cannot obtain the information it needs without communication.

Partition tolerance is not optional

Networks fail: switches, links, and whole availability zones become unreachable, and packets are delayed beyond any timeout. A distributed system that spans more than one machine cannot choose to have no partitions. The real choice is what to sacrifice when a partition occurs:

A single-node system has no partitions between replicas, so the theorem does not constrain it. "CA" as a category only describes a system that assumes partitions never occur.

CP and AP in real systems

The classification below describes default or typical behavior. Many systems are configurable.

A CP system does not become unavailable everywhere. The side of the partition that holds a majority can continue serving requests. Only the minority side is unavailable, which matches the CAP definition because the theorem only requires that some non-failing node cannot respond.

Worked example: five-node cluster split 3 and 2

A five-node majority-quorum store (for example etcd) is partitioned into groups of 3 and 2. A majority is 3 of 5 nodes.

• The group of 3 can still elect a leader and commit writes, because 3 acknowledgments form a majority. Clients that reach this group are served consistently.
• The group of 2 cannot reach a majority. It rejects writes and consistent reads. Clients that reach only this group receive errors or time out.
• No two groups can both commit conflicting writes, because any two majorities of 5 nodes share at least one node.

An AP store in the same situation lets both groups accept writes to the same key. After the partition heals, the replicas hold divergent versions, and the store must reconcile them (last-write-wins, version vectors with application merge, or CRDTs).

Common misconceptions

• "Pick any two of three." Partitions are not a property the designer chooses. The decision is between C and A once a partition happens.
• "CAP applies all the time." When there is no partition, a system can provide both consistency and availability. The trade-off that remains in that case is latency, covered by PACELC below.
• "AP means no consistency." AP systems typically offer weaker guarantees, such as eventual consistency, and often session guarantees. They converge after the partition heals.
• "A system is either CP or AP." Per-operation tuning is common. Quorum sizes, read consistency levels, and per-key or per-table settings move a system along the spectrum.
• CAP availability differs from uptime. A CP system can have high measured uptime because partitions are rare. CAP only describes behavior during one.

PACELC

Daniel Abadi proposed PACELC because CAP ignores the trade-off present when there is no partition. The statement reads:

If there is a Partition, choose between Availability and Consistency. Else, choose between Latency and Consistency.

The second half applies during normal operation. To make a write visible consistently, replicas must coordinate. Coordination costs round trips, and across regions a round trip costs tens to hundreds of milliseconds. A system can reduce latency by acknowledging writes before all replicas have them, or by serving reads from the nearest replica, at the cost of consistency.

flowchart TD
    A{"Partition?"} -->|"yes (P)"| B{"Give up?"}
    A -->|"no (E)"| C{"Optimize for?"}
    B -->|"availability"| PA["PA: serve requests, allow divergence"]
    B -->|"consistency"| PC["PC: refuse requests that cannot be consistent"]
    C -->|"latency"| EL["EL: respond before full replica coordination"]
    C -->|"consistency"| EC["EC: wait for replica coordination"]

Classification by PACELC

Classifications of specific products are approximations because configuration changes them.

Choosing in a design

• Use a CP design when incorrect data is worse than no data: account balances, inventory that must not oversell, leader election, locks, and configuration coordination.
• Use an AP design when serving a stale or divergent answer is acceptable and the system must remain writable: shopping carts, activity feeds, view counters, presence, and caches.
• Where AP is chosen for data with invariants, add reconciliation: last-write-wins, vector clocks, or CRDTs.
• State the decision per feature. One product usually contains both kinds of data.

Interview questions

• Why is partition tolerance not a real choice? Partitions happen in any networked system regardless of design intent. Dropping P means assuming the network never partitions, which only holds for a single node.
• Does a CP system stop serving all requests during a partition? No. The partition side that contains a quorum can continue. Only nodes that cannot reach a quorum reject or block requests.
• What does CAP say about a system with no partition? Nothing. PACELC covers this case: consistency then trades against latency because replica coordination takes network round trips.
• Is "C" in CAP the same as "C" in ACID? No. ACID consistency means transactions preserve application invariants. CAP consistency means linearizability of reads and writes on replicated data.
• How can an AP system still give users a consistent experience? Through session guarantees such as read-your-writes, sticky routing to one replica, and conflict resolution mechanisms that make replicas converge.