16. Consistency and CAP
1
The picture to keep in your head2
16.1 What does "consistent" actually mean?3
16.2 What is strong consistency?4
16.3 What is eventual consistency?5
16.4 What are read-your-writes and monotonic reads?6
16.5 What is a network partition?7
16.6 What does the CAP theorem actually say?8
16.7 What do CP and AP systems look like in practice?9
16.8 What is PACELC?10
16.9 How do quorums give tunable consistency?11
16.10 How do you choose consistency for each feature?12
Memory card and where the analogy breaks13
Practice: five levels14
Interview questions15
Solutions16
Sources17
Code lab16. Consistency and CAP
Sources
3 min read+10 XP
Source notes
- CAP conjecture: Eric Brewer, keynote at PODC 2000. Proof: Seth Gilbert and Nancy Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services", ACM SIGACT News, 2002. Brewer, "CAP Twelve Years Later: How the 'Rules' Have Changed", IEEE Computer, 2012.
- PACELC: Daniel J. Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design", IEEE Computer, February 2012 (https://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf). Classifications quoted (Dynamo-style systems as PA/EL by default; fully ACID systems such as VoltDB as PC/EC) are from that paper.
- Linearizability: Maurice Herlihy and Jeannette Wing, "Linearizability: A Correctness Condition for Concurrent Objects", ACM TOPLAS, 1990.
- Session guarantees (read-your-writes, monotonic reads and writes): Douglas Terry et al., "Session Guarantees for Weakly Consistent Replicated Data", PDIS 1994.
- Shopping cart as the motivating example for always-writable storage: DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store", SOSP 2007.
- CRDTs: Marc Shapiro et al., "Conflict-free Replicated Data Types", SSS 2011.
- The 120 ms Mumbai–Frankfurt round trip and spend rates are illustrative assumptions; arithmetic computed 2026-10-08.
- Level 3 and Level 4 code: tested 2026-10-08 (
code/ch16_consistency.py, all checks pass).