Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
Three words given definitions precise enough to prove they are incompatible - and a proof short enough to hold in your head.
Read the original ↗Twelve pages, one theorem, and a two-paragraph proof that almost nobody who cites it has read. What it proves is real, narrow, and useful. What it is used for - a three-way menu you pick two items from - is not in the paper, is not implied by it, and was disowned by the person whose conjecture it was inside a decade.
Included with a plan
This discussion is included with a plan. The first three lessons of every track are free, with their boards and videos. A plan unlocks every lesson, board, video, lab and paper for one price.
Related on chalk
The same idea as a board, lab, video or lesson.
- BoardThe Cut Phone Linethe partition itself: the moment the theorem is about, and the only moment it is about
- BoardThe Ledger Everyone Readsthe promise a store makes to a reader - the C in the theorem is the strictest row on this board and nothing weaker
- BoardConsistency and Consensuslinearizability defined slowly, which is what the paper's one-sentence definition of consistency actually means
- BoardWhen Machines Failthe asynchronous model the main theorem is proved in - no clocks, and no way to tell slow from dead
- BoardThe Copy Clerksreplicas running behind, which is what the available side of the choice looks like from a reader's chair
- BoardThe Two Ledgers Must Agreethe blocking coordinator: choosing consistency, and paying for it by refusing to answer
- LabThe cut phone lineanswer anyway or refuse - the theorem says these are the only two, and only during the partition
- LabThe ledger everyone readswhich promise you made; the paper's C is the top row and everything below it is outside the theorem
- LabThe copy clerksthe stale read the available side agrees to, priced in seconds
- LabThe two ledgers must agreethe coordinator that stops the world rather than disagree - the C side, run
- VideoCAP: the cut phone linethe partition, in ninety seconds, with the choice made in front of you
- VideoEvent-driven architecture: the ledger everyone readsthe promises, named, from linearizable downwards
- VideoDistributed transactions: the two ledgers must agreewhat refusing to answer costs when the crash lands between two writes
- LessonKV: everythingUses the board The Cut Phone Line
- LessonThe cut phone line (CAP, done properly)Uses the board The Cut Phone Line
- LessonA Book You Never Erase - the append-only ledger, reversals and derived balancesUses the board The Ledger Everyone Reads
- LessonThe Ledger Everyone Reads (event-driven & the log)Uses the board The Ledger Everyone Reads
- LessonConsistency and ConsensusUses the board Consistency and Consensus
- LessonBuild Your Own RaftUses the board Consistency and Consensus
- LessonRaft 02: Log ReplicationUses the board Consistency and Consensus
- LessonWhen Machines FailUses the board When Machines Fail
- LessonKV: quorumUses the board The Copy Clerks
- LessonThe copy clerks (database replication)Uses the board The Copy Clerks
- LessonThe Two Ledgers Must Agree (Distributed Transactions)Uses the board The Two Ledgers Must Agree
Further reading
Read the original for the full argument and its evidence.
- The paper ↗ACM SIGACT News 33(2), June 2002. Twelve pages. Read the definitions in Section 2 slowly and then Section 4, which is the half nobody quotes and the half that describes what you are probably building.
- CAP Twelve Years Later: How the Rules Have Changed ↗Brewer, 2012, retracting the framing his own conjecture became: partitions are rare, the choice is per-operation, and giving up consistency by default was never what he meant.
- Consistency Tradeoffs in Modern Distributed Database System Design ↗Abadi, IEEE Computer 2012. PACELC - the missing Else clause. Read it as the correction that lets you tell two systems apart when CAP calls them both the same thing.
- Keeping CALM: When Distributed Consistency Is Easy ↗Hellerstein and Alvaro. The other direction entirely: which computations need coordination at all. The answer - the non-monotonic ones - is a sharper design tool than CAP ever was.