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

**Authors:** Matthew Weidner, Joseph Gentle, Martin Kleppmann  
**arXiv:** [2305.00583](https://arxiv.org/abs/2305.00583)  
**Date:** 2023-04-30  
**Summary page:** https://www.summarizepaper.com/en/paper/2305.00583v1/

## Key points

- Collaborative text editors rely on replicated lists to allow multiple users to edit a document simultaneously.
- Existing algorithms for these lists suffer from interleaved and corrupted text passages when concurrent insertions occur at the same position in the document.
- Fugue is the first algorithm that guarantees maximal non-interleaving, a new correctness property for replicated lists.
- Fugue comes in two variants: one based on a tree and another based on a list, both of which are semantically equivalent.
- Fugue offers performance comparable to state-of-the-art CRDT libraries for text editing, even with documents containing 10.5 million characters.
- Tree-Fugue's performance remained tolerable with an 18MB save size, less than two seconds to save or load, and 223MB memory usage.
- Tree-Fugue avoids interleaving of both forward and backward insertions to the maximum extent possible; concurrent edits end up in different subtrees that are traversed separately.
- Fugue represents a significant step forward in collaborative text editing by addressing an issue that has plagued replicated lists for years.

## Summary

Collaborative text editors have long relied on replicated lists to allow multiple users to edit a document simultaneously. However, existing algorithms for these lists suffer from a problem where concurrent insertions at the same position in the document can result in interleaved and corrupted text passages. This issue affects both CRDTs (Conflict-free Replicated Data Types) and Operational Transformation and has gone unnoticed for decades. In response, a team of researchers from Carnegie Mellon University, Technical University of Munich, and an independent contributor have developed Fugue - the first algorithm that guarantees maximal non-interleaving - a new correctness property for replicated lists. The Fugue algorithm comes in two variants: one based on a tree and another based on a list. The researchers proved that both variants are semantically equivalent; meaning they produce the same output given the same input. They also implemented Fugue and demonstrated that it offers performance comparable to state-of-the-art CRDT libraries for text editing. To test their implementation's efficiency, the team used Yjs and Tree-Fugue with documents containing 10.5 million characters - far longer than any typical text document. Despite this sizeable amount of data, Tree-Fugue's performance remained tolerable with an 18MB save size, less than two seconds to save or load, and 223MB memory usage. Furthermore, the researchers proved that Tree-Fugue is maximally non-interleaving by avoiding interleaving of both forward and backward insertions to the maximum extent possible; concurrent edits end up in different subtrees that are traversed separately. In conclusion, Fugue represents a significant step forward in collaborative text editing by addressing an issue that has plagued replicated lists for years. Its implementation provides comparable performance to existing solutions while guaranteeing maximal non-interleaving - ensuring that edited documents remain readable without corruption or interleaved passages.