CAP Theorem

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 in concurrent programming. In a consistent system, it is impossible to read stale data.

Availability (A) : Every request receives a non-error response. The system remains operational as long as at least one node is running, 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. Partitions are a fact of life in any real distributed network; hardware failures, congestion, and physical distances all cause them.

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: PostgreSQL in distributed mode, MongoDB (default configuration), Apache ZooKeeper, etcd.

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

Node A ──── [partition] ──── Node B
   │                            │
Client                       Returns error
writes here                  (unavailable)

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.

Node A ──── [partition] ──── Node B
   │                            │
Client A sees              Client B sees
version 5                  version 4 (stale)
         ← converge after partition heals →

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?

If Partition:
  → choose between Availability and Consistency
Else (normal operation):
  → choose between Latency and Consistency

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.