CAP and Consistency Models

Consistency models define what guarantees a replicated system gives about the values reads return, and the CAP theorem bounds which of those guarantees can coexist with availability under network partitions.

Definition

A consistency model is a contract between a replicated data store and its clients specifying the permissible outcomes of concurrent reads and writes; the CAP theorem states that in the presence of a network partition a distributed data store cannot provide both linearizable consistency and availability.

Scope

This topic covers the formal consistency models—linearizability, sequential consistency, causal consistency, and eventual consistency—and their ordering by strength; the CAP theorem and its precise statement and proof; and refinements such as PACELC that also account for the latency-consistency trade-off in the absence of partitions. It supplies the vocabulary for specifying and comparing replicated-system guarantees.

Core questions

• How do linearizability, sequential, causal, and eventual consistency differ in strength?
• What exactly does the CAP theorem forbid, and what does it permit?
• How do latency considerations refine the consistency trade-off when there is no partition?

Key theories

Linearizability and sequential consistency

Linearizability requires each operation to appear to take effect atomically at some instant between its invocation and response, consistent with real time; sequential consistency drops the real-time requirement, demanding only a single legal interleaving respecting each process's order.

The CAP theorem

Gilbert and Lynch proved that no replicated data store can guarantee both linearizable consistency and availability when the network may drop messages between replicas, forcing a choice during partitions.

PACELC refinement

PACELC extends CAP by noting that even without a partition a system trades latency against consistency, so designs are characterized by their behavior both during partitions and in normal operation.

Clinical relevance

Every distributed database and storage service must declare a consistency model, and the CAP and PACELC trade-offs explain why some systems prioritize availability while others prioritize consistency; understanding them is essential for choosing and operating data infrastructure.

History

Lamport defined sequential consistency in 1979 and Herlihy and Wing formalized linearizability in 1990; Brewer conjectured the CAP trade-off in 2000, Gilbert and Lynch proved it in 2002, and Abadi's 2012 PACELC reframing clarified that latency, not only partitions, drives consistency choices.

Debates

Is CAP often misinterpreted?

CAP is frequently summarized as 'pick two of three,' but the precise result only forces a consistency-availability choice during a partition; critics argue this oversimplification obscures the more relevant everyday latency-consistency trade-off captured by PACELC.

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Maurice Herlihy
• Jeannette Wing
• Leslie Lamport

Seminal works

• gilbert2002
• herlihy1990
• lamport1979

Frequently asked questions

Does CAP mean a system can only ever have two of consistency, availability, and partition tolerance?

Not quite. Partitions are a fact of networks, not a design choice, so the real decision is what to do during a partition: sacrifice strong consistency to stay available, or sacrifice availability to stay consistent. When there is no partition, a system can be both consistent and available.