CAP Theorem

The CAP theorem, formulated by Eric Brewer, is a foundational result in distributed systems. It states that during a network partition, a distributed data store must choose between consistency and availability — it cannot have both.

How It Works

The three properties are:

• Consistency (C): Every read receives the most recent write or an error. All nodes agree on the current value.
• Availability (A): Every request receives a non-error response, though it may not reflect the latest write.
• Partition tolerance (P): The system continues to operate despite messages being dropped or delayed between nodes.

Because network partitions are unavoidable in real distributed systems, partition tolerance is effectively mandatory. The real choice is therefore between consistency and availability when a partition happens. A CP system (e.g., HBase, MongoDB in certain configurations) rejects requests to preserve correctness; an AP system (e.g., Cassandra, DynamoDB) keeps serving requests and reconciles later.

Why It Matters

CAP frames a decision every architect of a distributed database must make. It explains why some systems return stale data and others refuse to answer during failures. The theorem is often misread as a fixed three-way pick; in practice the trade-off only bites during partitions, and modern systems offer tunable consistency to choose per operation.

The PACELC extension adds nuance: even without partitions, systems trade latency against consistency.

Related Terms

See eventual consistency, BASE, ACID, and replication for how systems respond to the CAP constraints.