CRDTs: From sequential to concurrent executions
summary
Explains concrete CRDT implementations and tradeoffs: counters as per-site counters with pointwise max merge (G-counter/Pn-counters) so merges are idempotent; registers using version vectors for multi-value registers to detect concurrency and optionally break ties with wall clocks; sets choose add-wins vs remove-wins tradeoff (remove-wins needs more metadata); dissemination modes compare delta-state vs op-based dissemination (deltas cut bandwidth, ops need reliable group delivery). Shows real systems using these techniques (Riak/Redis research, Lightcone) and that transactions expressed as commutative updates can always converge.
AI-written summary · about
chapters (12)
- 0:00Start
- 1:43The Isochronic Map
- 4:13Small Lambda and the Big Lambda
- 8:19Normal Sequential Behavior
- 8:35Sequential Execution
- 13:39Principle of Permutation Equivalence
- 17:05Merge Operation
- 18:56Sequential Executions
- 22:26Preserve the Sequential Semantics
- 28:32Sequential Semantics
- 37:57Implementation Styles
- 46:05Vector Clocks
related talks
36mConflict-Free Replicated Datatypes (CRDT)
39mEventually Consistent Data Structures
40mPractical Demystification of CRDT
01h 13mCRDTs: The hard parts
43mAn Approach For The Internet Of Things
36mCRDT Architecture and Group Systems
34mUsing CRDTs Beyond Text Editors
29mAbout Combining Functional Reactive Programming and Replicated Data Types