On this page
CAP and Consistency Models
CAP is not a "choose two" scenario—network partitions are inevitable, and when they occur, you must choose between consistency and availability. From linearizability to eventual consistency, consistency is not a switch but a spectrum, with each choice carrying specific engineering costs and applicable scenarios.
CAP Theorem (Brewer 2000)
CAP is not about "choosing two out of Consistency, Availability, and Partition Tolerance." Eric Brewer's original intent was: Network partitions are inevitable; when they occur, you must choose between consistency and availability.
The precise definitions of these three terms in a distributed context:
- Consistency: Equivalent to Linearizability—all operations behave as if they are executed atomically in some global order. Read operations must always return the result of the most recent write. This is not "eventual consistency" or "read-your-writes"—it is the strongest formal definition.
- Availability: Every non-failing node must respond to requests with a non-error response. Note—this does not mean "returning the latest data," but rather "returning a response rather than an error/timeout." Returning stale data still counts as available.
- Partition Tolerance: The system continues to operate despite arbitrary network partitions. A network partition occurs when message loss or latency between some nodes exceeds a threshold.
Therefore, a more accurate statement is: When the network is healthy, you can choose CA (strong consistency + high availability). When a network partition occurs, you must sacrifice either C or A—it is impossible to guarantee both "all nodes see new data" and "all nodes can respond immediately."
Why CA is Impossible When P Occurs
The simplest example: Two nodes, A and B, with a broken network connection forming a partition. A client writes x=1 to A. Now another client reads x from B.
- If B immediately returns the old value (ensuring availability) → Inconsistency (sacrificing C)
- If B refuses to respond until it synchronizes with A (ensuring consistency) → Unavailability (sacrificing A)
There is no magic—this is a law of physics. The message delay between A and B can be infinite in the worst case.
PACELC Extension
CAP only discusses "what happens during a partition." PACELC adds the other half: When the network is normal (no partition), you must trade off Latency and Consistency—because normal message round-trips also take time. Strong consistency operations (such as linearizable reads) require waiting for a majority of nodes to acknowledge even if the network is perfect → resulting in higher latency.
Consistency Spectrum (From Strong to Weak)
Linearizability (Strong Consistency, Atomic Consistency)
Definition: Each operation appears to be executed atomically at some instant between its invocation and its return. All operations have a global order, and this order is consistent with real-time—if operation A returns before operation B starts, then A must precede B in the global order.
Systems satisfying linearizability: etcd (ReadIndex + Raft), ZooKeeper (read leader after sync), Google Spanner (TrueTime).
Sequential Consistency
Slightly weaker than linearizability: All operations have a global order, but this order does not need to respect real-time—as long as each client's own operation order is preserved.
That is: Client 1's write(1) comes before write(2), and Client 2's read can see 2 before write(2) (even if write(2) was invoked after the read)—as long as Client 1's operation order is 1→2. This is common in practice: asynchronous replication to followers means Client 2 might see the new value first.
Causal Consistency
Weaker than sequential consistency: It only guarantees that operations with causal relationships are seen in the same order on all nodes, while concurrent operations can appear in any order.
Causal relationship definition (Lamport's happens-before): If operation A happens before B (on the same client), or the result of A is observed by B and somehow influences B (e.g., B reads the value written by A), then A→B. A→B means all nodes must see A before B.
For concurrent operations with no causal relationship: The order does not matter and is eventually resolved via CRDTs or version vectors.
Implementation: Vector clocks (Dynamo/Riak), Lamport timestamps (MongoDB replica set's lastWriteDate).
Eventual Consistency
The weakest guarantee: If no new writes occur, all replicas will eventually converge to the same value. It does not guarantee "how fast" or "what will be seen in the interim."
Common in DNS, CDNs, and multi-leader asynchronous replication (MySQL replication lag).
Formal Differences Between Models
| Model | Global Order | Respects Real-Time | Causal Guarantee | Concurrency Handling |
|---|---|---|---|---|
| Linearizability | Yes | Yes | Yes | N/A (all operations ordered) |
| Sequential | Yes | No | Yes | N/A |
| Causal | Partial (causal chains) | N/A | Yes | Version Vectors/CRDT |
| Eventual | No | N/A | No | LWW/CRDT |
Practical Costs
Strong consistency = Higher latency + Lower availability:
- Latency: Linearizable reads require waiting for a majority of nodes to respond (Raft ReadIndex + heartbeat confirmation of leader identity) → 1-2 RTTs
- Availability: Partitioned linearizable systems must reject writes (etcd becomes read-only in a minority partition)
- Scalability: All writes must go through the leader (log replication in Raft/Paxos) → Write throughput is limited by a single node
Why many systems choose eventual consistency: Amazon Dynamo's design philosophy—if a shopping cart service becomes unavailable due to consistency requirements, the loss is direct sales revenue. DNS, the world's largest distributed database, chooses consistency delays of minutes to hours in exchange for extreme availability.
References
- Paper: "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services" (Gilbert & Lynch, 2002 — Formal proof of CAP)
- Paper: "Consistency Tradeoffs in Modern Distributed Database System Design" (PACELC, 2012)
- Paper: "Linearizability: A Correctness Condition for Concurrent Objects" (Herlihy & Wing, 1990)
Keywords: CAP, PACELC, linearizability, sequential consistency, causal consistency, eventual consistency, happens-before