CRDTs: The hard parts
summary
Explains concrete failures and fixes for CRDT text and tree editors: shows interleaving anomalies that jumble concurrent inserts (Logoot and LSEQ fail, TreeDoc/Woot costly, RGA has milder cases), gives an RGA-based fix and a timestamped move-on-tree algorithm that avoids cycles by undoing/red oing to insert out-of-order ops, and a list-move design built from last-writer-wins registers plus list IDs. Reports measured results: a 100 KB LaTeX history with 300k changes compresses from ~150 MB JSON to ~700 KB custom (and processes ~600 ops/sec). Also demonstrates 150 MB → 700 KB compression techniques.
AI-written summary · about
chapters (10)
- 0:00Introduction to CRDTs
- 4:32Operational Transformation
- 8:42Convergence and Consistency
- 11:12Interleaving Anomalies
- 18:54RGA Algorithm Details
- 22:50List Item Movement
- 31:20Moving Character Ranges
- 34:00Tree Data Structure Moves
- 49:12Efficiency and Compression
- 58:20Q&A and Conclusion
related talks
34mUsing CRDTs Beyond Text Editors
48mCRDTs: From sequential to concurrent executions
36mConflict-Free Replicated Datatypes (CRDT)
40mPractical Demystification of CRDT
01h 30mImplementing, verifying and debugging distributed event-based systems
21mCRDTs for Mortals
39mEventually Consistent Data Structures
15mIncremental Processing of Structured Data in Datalog