# Whatâs Fugue

Fugue is a new CRDT text algorithm, presented in _[The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing](https://arxiv.org/abs/2305.00583)_ by [Matthew Weidner](https://arxiv.org/search/cs?searchtype=author&query=Weidner%2C+M) et al., nicely solves **the interleaving problem**.

## The interleaving problem

The interleaving problem was proposed in the paper _[Interleaving anomalies in collaborative text editors](https://martin.kleppmann.com/2019/03/25/papoc-interleaving-anomalies.html)_ by Martin Kleppmann et al.

An example of interleaving:

- A type "Hello " from left to right/right to left
- B type "Hi " from left to right/right to left
- The expected result: "Hello Hi " or "Hi Hello "
- The interleaving result may look like: "HHeil lo"
  - This happens when typing from right to left in RGA.

![An example of an interleaving anomaly when using [fractional indexing](https://madebyevan.com/algos/crdt-fractional-indexing/) CRDT on text content.
Source: **Martin Kleppmann, Victor B. F. Gomes, Dominic P. Mulligan, and Alastair R. Beresford. 2019. Interleaving anomalies in collaborative text editors. [https://doi.org/10.1145/3301419.3323972](https://doi.org/10.1145/3301419.3323972)](./images/richtext0.png)

An example of an interleaving anomaly when using [fractional indexing](https://madebyevan.com/algos/crdt-fractional-indexing/) CRDT on text content.
Source: \*\*Martin Kleppmann, Victor B. F. Gomes, Dominic P. Mulligan, and Alastair R. Beresford. 2019. Interleaving anomalies in collaborative text editors. [https://doi.org/10.1145/3301419.3323972](https://doi.org/10.1145/3301419.3323972)

The [Fugue paper](https://arxiv.org/abs/2305.00583) summarizes the current state of the interleaving problems in the table.

![Source: Weidner, M., Gentle, J., & Kleppmann, M. (2023). The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing. *ArXiv*. /abs/2305.00583](./images/richtext1.png)

Source: Weidner, M., Gentle, J., & Kleppmann, M. (2023). The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing. _ArXiv_. /abs/2305.00583

The interleaving problem sometimes are unsolvable when there are more than 2 sites. See [Fugue](https://arxiv.org/abs/2305.00583) paper Appendix B, Proof of Theorem 5 for detailed explanation.

![The case where the interleaving problem is unsolvable
Source: Weidner, M., Gentle, J., & Kleppmann, M. (2023). The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing. *ArXiv*. /abs/2305.00583](./images/richtext2.png)

The case where the interleaving problem is unsolvable
Source: Weidner, M., Gentle, J., & Kleppmann, M. (2023). The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing. _ArXiv_. /abs/2305.00583

However, we can still minimize the chance of interleaving. Fugue introduces the concept of **maximal non-interleaving** and solves it with an elegant algorithm that is easy to optimize. The definition of _maximal non-interleaving_ makes a lot of sense to me and leaves little room for ambiguity. I won't reiterate the definition here. But the basic idea is first to solve forward interleaving by leftOrigin. If there is still ambiguity, then solve the backward interleaving by rightOrigin. (The leftOrigin and rightOrigin refer to the ids of the original neighbors when the character is inserted, just like Yjs)