The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing

Existing algorithms for replicated lists, which are widely used in collaborative text editors, suffer from a problem: when two users concurrently insert text at the same position in the document, the merged outcome may interleave the inserted text passages, resulting in corrupted and potentially unreadable text. The problem has gone unnoticed for decades, and it affects both CRDTs and Operational Transformation. This paper presents Fugue, the first algorithm that guarantees maximal non-interleaving, our new correctness property for replicated lists. We present two variants of the Fugue algorithm, one based on a tree and the other based on a list, and prove that they are semantically equivalent. We also implement Fugue and demonstrate that it offers performance comparable to state-of-the-art CRDT libraries for text editing.