The CAP Theorem and Consistency Models

The CAP theorem states that a distributed data store facing a network partition must sacrifice either consistency or availability, and consistency models specify exactly what guarantees a system gives about the visibility and ordering of updates.

Definition

The CAP theorem asserts that a networked shared-data system can guarantee at most two of consistency, availability, and partition tolerance simultaneously; a consistency model is a contract specifying what an application may observe about the order and visibility of reads and writes across replicas.

Scope

This topic covers the CAP theorem and its formalization, the practical reading that the real trade-off arises only during network partitions, and the resulting PACELC refinement. It covers the spectrum of consistency models — from strong (linearizable) consistency through causal consistency to eventual consistency — and the BASE style that contrasts with ACID. It treats how these models guide the design of replicated data stores. It excludes the consensus and commit protocols used to implement strong consistency, which are covered under distributed databases.

Core questions

• What exactly do consistency, availability, and partition tolerance mean in CAP?
• Why is the real choice between consistency and availability only forced during a partition?
• How do strong, causal, and eventual consistency differ in their guarantees?
• What does eventual consistency promise, and what does it not?
• How does the BASE philosophy contrast with ACID?

Key concepts

• consistency, availability, partition tolerance
• network partition
• linearizability / strong consistency
• causal consistency
• eventual consistency
• PACELC
• BASE versus ACID
• conflict resolution

Key theories

The CAP theorem

Formalized by Gilbert and Lynch, CAP shows that when the network partitions, a replicated store must choose between returning possibly stale data (availability) and refusing service to preserve a single consistent value (consistency); partition tolerance is not optional in real networks.

Consistency spectrum

Consistency models range from strong (linearizable) consistency, where reads always see the latest write, through causal consistency, which preserves cause-and-effect order, to eventual consistency, where replicas converge over time absent new writes.

BASE versus ACID

Highly available systems often adopt a BASE style — basically available, soft state, eventually consistent — deliberately relaxing the strong ACID guarantees to remain responsive under partitions and at scale.

Clinical relevance

CAP and consistency models frame the central design choice in distributed data systems: whether a store prioritizes always answering (availability) or always answering correctly (consistency) when the network fails, a decision that shapes the behavior and guarantees of every globally distributed application.

History

Eric Brewer conjectured the CAP trade-off around 2000; Gilbert and Lynch proved it formally in 2002. Amazon's Dynamo (2007) and Vogels's 2009 essay popularized eventual consistency in practice. Brewer's 2012 retrospective clarified that CAP forbids perfect consistency and availability only during partitions, and the PACELC formulation later added the latency-consistency trade-off in the partition-free case.

Debates

How fundamental is the consistency-availability trade-off

Early readings treated CAP as forcing a permanent choice between consistency and availability; later analyses, including Brewer's retrospective, argue the trade-off bites only during partitions and that systems can be largely consistent and available otherwise, reframing how strictly CAP constrains design.

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Werner Vogels

Seminal works

• gilbert2002
• brewer2012
• vogels2009

Frequently asked questions

Does CAP mean I can only ever have two of the three properties?

The popular 'pick two' phrasing is misleading. Partition tolerance is not really optional in a distributed system, so the genuine choice is between consistency and availability, and that choice only has to be made while a partition is actually occurring. When the network is healthy, a system can provide both consistency and availability.

What does eventual consistency actually guarantee?

It guarantees that if no new updates are made to a data item, all replicas will eventually converge to the same value. It does not guarantee when, nor that a read will reflect the most recent write, so applications using eventual consistency must tolerate temporarily stale or conflicting reads and often handle conflict resolution themselves.