RunTime-Assisted Convergence in Replicated Data Types
summary
Presents Quark, a runtime that enforces convergence for mergeable replicated data types by delaying merges (not edits) so arbitrary merge functions and unmodified state formats work; implemented in OCaml + Shiloh and evaluated with a simulated collaborative editor where users make ~4 edits/sec. Local edit latency stays under ~35 ms (zero-latency edits); measured merge staleness is ~10 ms with 10 editors and ~2 s with 60 editors (staleness trade-off). Experiments run on co‑located EC2 instances; geo‑latency effects are not measured.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:15Replicated Applications
- 1:01Mergeable Replicated Data Types (MRDTs)
- 1:35Example MRDT: Set
- 2:29Advantages
- 3:00What About Convergence?
- 4:54How To Get Convergence... Engineer Merge Properties?
- 5:54Another Approach... Restrict Concurrent Edits?
- 7:01Observation: Divergent States → Multiple LCAS
- 8:13Our Approach: Restrict Merges Instead of Edits
- 8:57Quark: RunTime-Assisted Convergence
- 10:30Restricted Merges are Less Disruptive
- 11:26Staleness: A Different Kind of Cost
- 12:24Implementation
- 12:47Evaluation: Collaborative Editing
- 13:38Evaluation Results: Edit Latency
- 14:29Evaluation Results: Merge Staleness
related talks
41mProgramming Distributed Systems
29mLet's replicate state together
45mAutomerge: A new foundation for collaboration software
01h 30mImplementing, verifying and debugging distributed event-based systems
52mThe Computer Science behind a modern distributed data store
20mExploiting Commutativity For Practical Fast Replication
01h 13mCRDTs: The hard parts
36mConflict-Free Replicated Datatypes (CRDT)