CAP Theorem

Suppose the product service of our store keeps its data in PostgreSQL replicated on two nodes, one in each data centre, so that the store survives the loss of a whole site. One afternoon the link between the two sites goes down, but both nodes are still alive and still receiving requests. A customer on site B asks for the stock of product 42, which was just updated on site A. Node B has two options: answer with what it has (possibly stale) or refuse to answer until it can talk to A again. There is no third option — and this is exactly what the CAP theorem formalises.

The CAP Theorem, proposed by Eric Brewer in 2000 and formally proven by Seth Gilbert and Nancy Lynch in 2002¹, states that a distributed system that replicates data across nodes cannot simultaneously guarantee all three of the following properties³:

The three properties

Consistency (C) : Every read returns the most recent write, or an error. All nodes see the same data at the same time — equivalent to linearisability (the system behaves as if there were a single copy of the data and every operation took effect at one instant). In a consistent system, it is impossible to read stale data.

Availability (A) : Every request received by a non-failing node receives a non-error response — even if the response may not contain the most recent write.

Partition Tolerance (P) : The system continues to operate despite arbitrary network partitions — message drops or delays between nodes. A partition splits the nodes into groups that can still run but cannot talk to each other. Partitions are a fact of life in any real distributed network; hardware failures, congestion, and physical distances all cause them.

A partition, step by step

The same scenario played twice: once by a CP system and once by an AP system.

sequenceDiagram
    participant CA as Client A
    participant N1 as Node 1 (majority side)
    participant N2 as Node 2 (isolated)
    participant CB as Client B
    Note over N1,N2: 3 replicas: Node 1 and Node 3 can still talk, Node 2 is cut off
    CA->>N1: write stock[42] = 0
    N1-xN2: replicate (link is down)
    N1-->>CA: OK
    CB->>N2: read stock[42]
    alt CP: choose consistency
        N2-->>CB: error: cannot reach majority
    else AP: choose availability
        N2-->>CB: stock[42] = 5 (stale)
    end
    Note over N1,N2: partition heals, replicas sync

Neither answer is "wrong": the CP node refuses rather than lie; the AP node answers with the best value it has. Which one is acceptable depends on the data, not on the technology.

System classes

CP — Consistent and Partition-Tolerant

During a partition, the system refuses requests rather than returning potentially stale data. When the partition heals, consistency is restored before serving again.

Examples: Apache ZooKeeper, etcd, PostgreSQL with synchronous replication, MongoDB (with majority write concern and primary reads, the defaults).

Use when: correctness is non-negotiable — financial transactions, inventory systems, identity stores.

flowchart LR
    CA(["Client A"]) -->|"1 · write stock = 0"| A[("Node A<br/>stock = 0")]
    A -.-x|"2 · replicate ✗ partition"| B[("Node B<br/>stock = 5")]
    CB(["Client B"]) -->|"3 · read stock"| B
    B -->|"4 · error: unavailable"| CB

AP — Available and Partition-Tolerant

During a partition, every node continues to respond, but nodes may diverge and return different data. After the partition heals, the system converges to a consistent state (eventual consistency).

Examples: Apache Cassandra, Amazon DynamoDB, CouchDB, DNS.

Use when: availability matters more than momentary accuracy — shopping carts, social media feeds, search indexes.

flowchart LR
    CA(["Client A"]) -->|"1 · write stock = 0"| A[("Node A<br/>stock = 0")]
    A -.-x|"2 · replicate ✗ partition"| B[("Node B<br/>stock = 5")]
    CB(["Client B"]) -->|"3 · read stock"| B
    B -->|"4 · stock = 5 (stale)"| CB
    A ==>|"5 · partition heals: sync"| B

CA — Consistent and Available

Assumes no partitions, which is only realistic for single-machine systems or tightly controlled LANs. Not a practical category for distributed systems.

Comparison table

The PACELC extension

The CAP theorem only addresses the partition scenario. PACELC (Daniel Abadi, 2010)² extends it by asking: even when there is no partition, what is the trade-off?

flowchart LR
    Q{"Is there a<br/>partition?"} -->|"yes · P"| PAC{"Availability<br/>or Consistency?"}
    PAC -->|A| PA["PA: answer, maybe stale"]
    PAC -->|C| PC["PC: refuse or wait"]
    Q -->|"no · E (else)"| ELC{"Latency<br/>or Consistency?"}
    ELC -->|L| EL["EL: answer before<br/>the replicas confirm"]
    ELC -->|C| EC["EC: wait for<br/>the replicas"]

The reason is replication: to be consistent, a write must wait for other replicas to acknowledge it (a network round-trip, possibly to another region); to be fast, it must answer before they do — and accept that a replica may briefly lag behind.

PACELC⁴ is more useful than CAP for making day-to-day database choices, because most of the time there is no partition — yet the latency/consistency trade-off is always present.

Practical implications for system design

E-commerce product catalogue → AP : Showing a product as in-stock when it has just gone out of stock is acceptable. A brief period of stale data does not harm correctness.

Shopping cart → AP : Adding an item to a cart that temporarily diverges across replicas is fine; the cart can reconcile on checkout.

Payment processing → CP : A double charge or missed debit cannot be reconciled after the fact. Consistency is required.

User authentication → CP : A revoked token must be immediately invalid across all nodes. Stale auth state is a security vulnerability.

Connections

• Consensus & Algorithms — how CP systems such as etcd actually stay consistent: majorities and Raft.
• Hands-on 8 — a Redis cache, an explicit choice of latency over consistency.
• Event-Driven Architecture — asynchronous events make services eventually consistent with each other.

Key takeaways

• CAP: when the network partitions, a replicated store must choose between consistency (refuse) and availability (answer, maybe stale).
• P is not optional, so the real choice is C or A during a partition; CA only exists on a single node.
• CAP's C is linearisability — not ACID's C.
• PACELC: even without a partition, replication forces a choice between latency and consistency.
• Choose per data domain and per configuration: payments and auth CP, catalogue and cart AP.