https://arxiv.org/api/uRy1efAkVJDvM+nGaDiGIP3gDwU 2026-10-03T20:15:04Z 10 1 0 http://arxiv.org/abs/2409.14252v1 2024-09-21T21:50:13Z

Collaborative text editing algorithms allow several users to concurrently modify a text file, and automatically merge concurrent edits into a consistent state. Existing algorithms fall in two categories: Operational Transformation (OT) algorithms are slow to merge files that have diverged substantially due to offline editing; CRDTs are slow to load and consume a lot of memory. We introduce Eg-walker, a collaboration algorithm for text that avoids these weaknesses. Compared to existing CRDTs, it consumes an order of magnitude less memory in the steady state, and loading a document from disk is orders of magnitude faster. Compared to OT, merging long-running branches is orders of magnitude faster. In the worst case, the merging performance of Eg-walker is comparable with existing CRDT algorithms. Eg-walker can be used everywhere CRDTs are used, including peer-to-peer systems without a central server. By offering performance that is competitive with centralised algorithms, our result paves the way towards the widespread adoption of peer-to-peer collaboration software.

2024-09-21T21:50:13Z Accepted at 20th European Conference on Computer Systems (EuroSys 2025) Joseph Gentle Martin Kleppmann 10.1145/3689031.3696076