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

Matthew Weidner and Martin Kleppmann M. Weidner is with Carnegie Mellon
University. M. Kleppmann is with the Technical University of Munich.

###### Abstract

Most 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 defines maximal non-
interleaving, our new correctness property for replicated lists. We introduce
two related CRDT algorithms, Fugue and FugueMax, and prove that FugueMax
satisfies maximal non-interleaving. We also implement our algorithms and
demonstrate that Fugue offers performance comparable to state-of-the-art CRDT
libraries for text editing.

###### Index Terms:

Distributed data structures, replica consistency, collaborative text editing,
Conflict-free Replicated Data Types (CRDTs), operational transformation.

##  1 Introduction

Collaborative text editors such as Google Docs allow several users to
concurrently modify a document, while ensuring that all users' copies of the
document converge to the same state. Even though algorithms for collaborative
text editing have been studied for over three decades [1, 2, 3], a formal
specification of the required behavior only appeared as recently as 2016 [4].
We argue that this specification is incomplete. There is an additional
correctness property that is important in practice, but which has been
overlooked by almost all prior research on this topic: _non-interleaving_.
Informally stated, this property requires that when sections of text are
composed independently from each other (perhaps while the users are offline),
and the edits are subsequently merged, those sections are placed one after
another, and not intermingled in the final document. (We give a formal
definition in Section 4.2.)

There are two main families of algorithms for collaborative text editing:
Conflict-free Replicated Data Types (CRDTs) [5, 6], and Operational
Transformation (OT) [1, 3]. Perhaps surprisingly, almost all existing text
collaboration algorithms we surveyed, both CRDT and OT, suffer from
interleaving.

To address this situation, this paper makes the following contributions:

  * •

We survey a selection of CRDT and OT algorithms for collaborative text
editing, and highlight interleaving anomalies with many of them (Section 2.4).

  * •

We show that a previous attempt to address the issue [7] is flawed: its
definition of non-interleaving is impossible to satisfy, and the algorithm
proposed in that paper does not converge (Section 2.5).

  * •

We extend the formal specification by Attiya et al. [4] with a new property,
which we call _maximal non-interleaving_ (Section 4.2). This definition is
subtle: we show that an alternative, simpler definition is also impossible to
satisfy (Section 4.2).

  * •

We introduce _Fugue_ and _FugueMax_ , two novel CRDT algorithms for
collaborative text editing. Fugue is simpler but falls slightly short of
achieving maximal non-interleaving, while we prove that FugueMax satisfies
maximal non-interleaving (Section 3).

  * •

We provide an optimized open source implementation of Fugue, and show that it
achieves performance comparable to the state-of-the-art Yjs library on a
realistic text-editing trace (Section 5).

##  2 Background and Related Work

Collaborative text editing originated with the work of Ellis and Gibbs [1],
who also introduced Operational Transformation (OT) as a technique for
resolving concurrent edits. This approach was formalized by Ressel et al. [8],
and further developed by Sun et al. [9] and many other papers. The OT
algorithm Jupiter [2] later became the basis for real-time collaboration in
Google Docs [10]. Following bugs in several OT algorithms, which failed to
converge in some situations [11, 12], Conflict-free Replicated Data Types
(CRDTs) were developed as an alternative approach [5]. The first CRDT for text
editing was WOOT [13], which was followed by Treedoc [14], Logoot [15], RGA
[16], and others.

These algorithms allow multiple users, each with their own copy of the
document, to concurrently edit the text. Although these algorithms are usually
presented in the context of text editing, they can easily be generalized
beyond text: instead of a list of characters, the algorithm could manage a
list of other objects, such as items on a to-do list, or rows in a
spreadsheet. We therefore also say that these algorithms implement a
replicated list object [4].

###  2.1 System Model

In collaborative text editors, each user session (e.g., a tab in a web
browser) maintains a replica of the list of characters. On user input, the
user's local replica of the document is updated by inserting or deleting
characters in this list, and each such insertion or deletion is called an
_operation_. A user's operations are immediately applied to their local
replica, without waiting for network communication with any other nodes, in
order to provide responsive user interaction independently of network latency.
This model also allows disconnected operation: if a user edits the document
while offline, their client buffers the operations they generate and sends
them to collaborators when they next connect.

Assuming users eventually come online, every operation is eventually
propagated to other replicas, and each replica integrates remote operations
into its local state as they are received. At a minimum, this process must
ensure _convergence_ : any two replicas that have processed the same set of
operations must be in the same state, even if they received the operations in
a different order. A more detailed specification of a replicated list is given
by Attiya at al. [4]; we summarize it in the proof of Theorem 1 in Section 3.

Algorithms for collaborative text editing differ in the assumptions they make
about the network between replicas. For example, the OT algorithm Jupiter [2]
assumes that all operations pass through a central server that sequences and
transforms those operations. On the other hand, CRDTs (including our Fugue
algorithm in Section 3) generally assume a causal broadcast protocol [5].
Causal broadcast can be implemented in a peer-to-peer network without assuming
any central server or consensus protocol [17, 18], making this model suitable
for decentralized systems. The causal broadcast protocol handles
retransmission of dropped messages, and ensures that when a replica comes
online, it receives all the operations it missed while offline.

`m`

`i`

`l`

`k`

`\n`

0.210.320.460.660.91

`m`

`i`

`l`

`k`

`\n`

`e`

`g`

`g`

`s`

`\n`

0.210.320.460.660.700.740.790.830.860.91

`m`

`i`

`l`

`k`

`\n`

`b`

`r`

`e`

`a`

`d`

`\n`

0.210.320.460.660.720.750.770.800.840.880.91

`m`

`i`

`l`

`k`

`\n`

`\n`

`e`

`b`

`r`

`g`

`e`

`g`

`a`

`s`

`d`

`\n`

0.210.320.460.660.700.720.740.750.770.790.800.830.840.860.880.91User A:User
B:merged: Figure 1: Interleaving when character positions are taken from the
rational numbers $\mathbb{Q}$.

###  2.2 The interleaving problem

Several replicated list CRDTs, including Treedoc [14], Logoot [15], and LSEQ
[19], assign to each list element a unique identifier from a dense, totally
ordered set. The sequence of list elements is then obtained by sorting the IDs
in ascending order. To insert a new list element between two adjacent elements
with IDs $\mathit{id}_{1}$ and $\mathit{id}_{2}$ respectively, the algorithm
generates a new unique ID $\mathit{id}_{3}$ such that
$\mathit{id}_{1}<\mathit{id}_{3}<\mathit{id}_{2}$, where $<$ is the total
order on identifiers.

Say another user concurrently inserts an element with ID $\mathit{id}_{4}$
between the same pair of elements $(\mathit{id}_{1},\mathit{id}_{2})$ such
that $\mathit{id}_{1}<\mathit{id}_{4}<\mathit{id}_{2}$. The minimum
requirement of $\mathit{id}_{3}\neq\mathit{id}_{4}$ is easy to achieve (e.g.,
by including in each ID the unique name of the replica that generated it), but
whether $\mathit{id}_{3}<\mathit{id}_{4}$ or $\mathit{id}_{3}>\mathit{id}_{4}$
is an arbitrary choice.

When two users concurrently insert several new elements in the same ID
interval, the result is an effect illustrated in Figure 1. (The figure uses a
rational number as each ID, whereas actual algorithms use a path through a
tree, but the resulting behavior is similar.) The diagram shows the state of a
text document containing a shopping list, initially containing the word
``milk'' and a newline character. User A inserts a line break and ``eggs'',
while concurrently user B inserts a line break and ``bread''. The merged
result contains ``milk'', a blank line, and then the word ``ebrgegasd''.

We argue that this behavior is obviously undesirable. Nevertheless, none of
the affected papers even mention the issue, and although it had been
informally known to people in the field for some time, it was not documented
in the research literature until 2018 [20, 21]. Attiya et al.'s specification
[4] allows interleaving like in Figure 1.

ShoppingShopping$\cdot$ bananasShopping$\cdot$ cakeShopping$\cdot$
apples$\cdot$ bananasShopping$\cdot$ bread$\cdot$ cakeShoppingFruit:$\cdot$
apples$\cdot$ bananasShoppingBakery:$\cdot$ bread$\cdot$
cakeShoppingBakery:Fruit:$\cdot$ bread$\cdot$ apples$\cdot$ cake$\cdot$
bananasUser A:User B:merged: Figure 2: Each user prepends items to their
shopping list. When the edits are merged in an algorithm that allows
interleaving of backward insertions, the result may place the items in an
illogical order, such as listing bread in the fruit category.

###  2.3 Interleaving of forward and backward insertions

In some replicated list algorithms, whether interleaving can occur or not
depends on the order in which the elements are inserted into the list. In the
common case, when a user writes text, they insert characters in forward
direction: that is, ``bread'' is inserted as the character sequence ``b'',
``r'', ``e'', ``a'', ``d''. However, not all writing is in forward direction:
sometimes users hit backspace to fix a typo, or move their cursor to a
different location in the document and continue typing there.

Besides inserting characters in forward direction, it is also possible to
insert in backward direction. The extreme case of typing text in reverse order
character by character (typing ``bread'' as ``d'', ``a'', ``e'', ``r'', ``b'')
is unlikely to occur in practical text editing scenarios. However, a plausible
scenario of backward insertion is illustrated in Figure 2. In this example,
two users add items to a shared shopping list while offline. Each user
prepends new items to the beginning of the list, finally adding a category
header (``fruit'' or ``bakery'') for the items they added. When the users
merge their changes, an algorithm that allows interleaving of backward
insertions may place the items in a surprising order. This behavior is less
bad than the fine-grained character-by-character interleaving of Figure 1, but
it is nevertheless not ideal. It would be preferable to keep all of each
user's insertions as one contiguous string, regardless of the order in which
the elements were inserted.

When OT/CRDT algorithms for replicated lists are used for data other than
text, backward insertion is more likely to occur. For example, in a
spreadsheet or to-do list, new rows/items might regularly be inserted at the
top, one at a time. If we can avoid both forward and backward interleaving, we
also improve the behavior of these multi-user applications.

TABLE I: Various algorithms' susceptibility to interleaving anomalies. Key: $\medblackcircle$ = interleaving can occur; $\medcircle$ = we have not been able to find examples of interleaving; $\medcircle\checkmark$ = proven not to interleave; $\lightning$ = algorithm may incorrectly reorder characters. Examples of anomalies appear in Appendix A. Family | Algorithm |  forward interleaving (one replica) |  backward interleaving (one replica) |  backward interleaving (multi-replica)
---|---|---|---|---
OT | adOPTed [8] | $\medblackcircle$ | $\medcircle$ | $\medblackcircle$
| Jupiter [2] | $\medblackcircle$ | $\medcircle$ | $\medcircle$
| GOT [3] | $\medblackcircle$ | $\lightning$ | $\lightning$
| SOCT2 [22] | $\medblackcircle$ | $\medblackcircle$ | $\medblackcircle$
| TTF [23] | $\medblackcircle$ | $\medcircle$ | $\medblackcircle$
CRDT | WOOT [13] | $\medblackcircle$ | $\medcircle$ | $\medcircle$
| Logoot [15] | $\medblackcircle$ | $\medblackcircle$ | $\medblackcircle$
| LSEQ [19] | $\medblackcircle$ | $\medblackcircle$ | $\medblackcircle$
| Treedoc [14] | $\medblackcircle$ | $\medblackcircle$ | $\medblackcircle$
| RGA [16] | $\medcircle\checkmark$ | $\medblackcircle$ | $\medblackcircle$
| Yjs [24] | $\medcircle\checkmark$ | $\medcircle$ | $\medblackcircle$
| YjsMod [25] | $\medcircle$ | $\medcircle$ | $\medcircle$
| Sync9 [26] | $\medcircle$ | $\medcircle$ | $\medcircle$
| Fugue | $\medcircle\checkmark$ | $\medcircle\checkmark$ | $\medcircle\checkmark$
| FugueMax | $\medcircle\checkmark$ | $\medcircle\checkmark$ | $\medcircle\checkmark$

###  2.4 Algorithms that exhibit interleaving

The interleaving problem was first noticed in CRDTs such as Logoot and LSEQ
because they are particularly prone to the problem; experiments with
implementations of these algorithms are easily able to trigger interleaving in
practice [27]. However, when we started looking at the issue more closely, we
found that interleaving is surprisingly prevalent among both OT and CRDT
algorithms for collaborative text editing. Our findings are summarized in
Table I, and examples of each instance of interleaving are detailed in
Appendix A.

Occurrence of interleaving is often nondeterministic, and the probability of
exhibiting interleaving varies depending on the algorithm: for example, in
some algorithms it depends on the exact order in which concurrently sent
network messages are received, and in some it depends on random numbers
generated as part of the algorithm.

In some algorithms, interleaving occurs only if multiple replicas participate
in one of the concurrent editing sessions; this is indicated in the column
labeled ``multi-replica'' in Table I. This can happen, for example, if a user
starts some work on one device and then continues on another device (producing
an editing session that spans two devices), while independently another user
works offline on the same document on a third device. It can also occur in
systems with ephemeral replica IDs, such as a web application that generates a
fresh ID for every browser tab refresh.

In the cases marked $\medcircle$ in Table I we conjecture non-interleaving,
but we have not proved it. Only in the cases marked $\medcircle\checkmark$ has
non-interleaving been proven. RGA forward non-interleaving was proved by
Kleppmann et al. [20], Yjs forward non-interleaving is proved in an in-
progress paper, and our own algorithms Fugue and FugueMax are verified in
Section 4.

The only existing algorithms for which we have not found interleaving examples
are Sync9 [26], and a modification of Yjs proposed by Seph Gentle (``YjsMod'')
[25]. At the time of writing, there are no research papers describing these
algorithms, and no proofs of correctness; the only published material is
source code and informal documentation [26, 25]. Fugue was developed
independently from both of these algorithms, while FugueMax uses a technique
from YjsMod (see Section 4.3). There are similarities between Fugue and Sync9,
and based on discussions with the authors of Sync9 we conjecture that they
have equivalent merging behavior, but we leave a detailed comparison to future
work.

###  2.5 Previous attempt to ensure non-interleaving

Kleppmann et al. [7] previously identified the interleaving problem. That work
has two serious flaws:

  1. 1.

The definition of non-interleaving in that paper cannot be satisfied by any
algorithm.

  2. 2.

The CRDT algorithm proposed in that paper, which aims to be non-interleaving,
is incorrect – it does not converge. An example of non-convergence, which was
found by Chandrassery [28], is given in Appendix A.3.

They define non-interleaving as follows (paraphrased):

> Suppose two sets of list elements $X$ and $Y$ satisfy:
>
>   * •
>
> All elements in $X$ were inserted concurrently to all elements in $Y$.
>
>   * •
>
> The elements were inserted at the same location in the document, that is:
> after applying the insertions for $X\cup Y$ and their causal predecessors,
> $X\cup Y$ are contiguous in the list order.
>
>

>
> Then either $X$ appears before $Y$ or vice-versa. That is, either $\forall
> x\in X,y\in Y.\,x\prec y$ or $\forall x\in X,y\in Y.\,y\prec x$, where
> $\prec$ is the order of elements in the final list.

To show that no replicated list algorithm can satisfy this definition, it is
sufficient to give a counterexample. Starting from an empty list, suppose four
replicas concurrently each insert one element. After applying these four
insertions, the list state must be some ordering of these four elements; let
the order be $abcd$. Then $X=\\{a,c\\}$ and $Y=\\{b,d\\}$ satisfy the two
hypotheses, but they are interleaved. Since this situation could arise with
any algorithm, it cannot be prevented.

In Section 4.2 we give a new definition of non-interleaving that can be
implemented.

##  3 The Fugue algorithm

We now introduce _Fugue_ (pronounced [fju:g]), a new algorithm for replicated
lists and collaborative text editing. It is named after a form of classical
music in which several melodic lines are interwoven in a pleasing way. We
analyze Fugue's non-interleaving properties in Section 4, and we evaluate
implementations in Section 5.

We describe Fugue as an operation-based CRDT [5], although it can easily be
reformulated as a state-based CRDT. The external interface of Fugue is an
ordered sequence of values, e.g., the characters in a text document. Since the
same value may appear multiple times in a list, we use _element_ to refer to a
unique instance of a value. Then the operations on the list are:

  * •

$\mathsf{insert}(i,x)$: Inserts a new element with value $x$ at index $i$,
between existing elements at indices $i-1$ and $i$. All later elements (index
$\geq i$) shift to an incremented index.

  * •

$\mathsf{delete}(i)$: Deletes the element at index $i$. All later elements
(index $\geq i+1$) shift to a decremented index.

Note that we omit operations to mutate or move elements; these can be
implemented by combining a replicated list with other CRDTs [29]. We also omit
optimizations that compress consecutive runs of insertions or deletions; these
can be added later without affecting the core algorithm. At a high level the
algorithm works as follows:

##### State

The state of each replica is a tree in which each non-root node is labeled
with a unique ID and a value. Each non-root node is marked as either a _left_
or _right_ child of its parent, but the tree is not necessarily binary: a
parent can have multiple left children or right children, as illustrated in
Figure 3. The tree does not need to be balanced.

rootcabedf Figure 3: One possible Fugue structure for the list abcdef. Observe
that a and b are both left children of c; they are sorted lexicographically by
their elements' IDs.

Each non-root node in the tree corresponds to an element in the list (e.g., a
character in the text document). The list order is given by the depth-first
in-order traversal over this tree: first recursively traverse a node's left
children, then visit the node's own value, then traverse its right children.
_Same-side siblings_ —nodes with the same parent and the same side—are
traversed in lexicographic order of their IDs; the exact construction of IDs
and their order is not important.

##### Insert

To implement $\mathsf{insert}(i,x)$, a replica creates a new node, labeled
with a new unique ID and value $x$, at an appropriate position in its local
tree: if the element at index $i-1$ has no right children, the new node
becomes a right child of the element at index $i-1$; otherwise, the new node
is added as a left child of the next element in the traversal order. Figure 4
illustrates how this choice is made, and Theorem 1 shows that this approach
results in the desired behavior. The replica then uses a causal broadcast
protocol to send the new node, its parent, and its side (left or right child)
to other replicas, which add the node to their own local trees.

(a)(b)rootrootcagbedfcaghbedf Figure 4: (a) Inserting a new element g between
a and b. When a has no right children, making g a right child of a places it
immediately after a in the traversal. (b) Inserting a second new element h
between a and g. When g is a descendant of a, we make h a left child of g.

A replica will not create a new node where it already has a same-side sibling,
i.e., it will try to keep the tree binary. However, multiple replicas may
concurrently insert nodes at the same position, creating same-side siblings
like a and b in Figure 3.

##### Delete

To implement $\mathsf{delete}(i)$, a replica looks up the node at index $i$ in
the current list state, then causally broadcasts a message containing that
element's ID. All replicas then replace that node's value with a special value
$\bot$, flagging it as deleted (i.e., making it a _tombstone_). Nodes with
this value are skipped when computing the external list state (e.g., for the
purpose of computing indices of list elements); however, their non-deleted
descendants are still traversed normally, and a deleted node may still be used
as a parent of a new node.

We cannot remove a deleted element's node entirely: it may be an ancestor to
non-deleted nodes, including nodes inserted concurrently. In Section 5 we
discuss ways of mitigating memory usage from tombstones.

1

2types:

3 $\mathsf{RID}$, type of replica identifiers

4
$\mathsf{ID}:=(\mathsf{RID}\times\mathbb{N})\cup\\{\mathop{\hbox{$\mathsf{null}$}}\nolimits\\}$,
type of element IDs

5 $\mathbb{V}$, type of values

6 $\bot$, a marker for deleted nodes

7 $\\{L,R\\}$, type of a child node's side (left or right)

8
$\mathsf{NODE}:=\mathsf{ID}\times(\mathbb{V}\cup\\{\bot\\})\times\mathsf{ID}\times\\{L,R\\}$,
tree node tuples $(\mathit{id},\mathit{value},\mathit{parent},\mathit{side})$

9

10 per-replica CRDT state:

11 $\mathit{replicaID}\in\mathsf{RID}$: the unique ID of this replica

12
$\mathit{tree}\subseteq\mathsf{NODE}\times\mathsf{ID}[]\times\mathsf{ID}[]$: a
set of tree node triples
$(\mathit{node},\mathit{leftChildren},\mathit{rightChildren})$, initially
$\\{(\mathit{root},[],[])\\}$ where
$\text{{root}}=(\mathop{\hbox{$\mathsf{null}$}}\nolimits,\bot,\mathop{\hbox{$\mathsf{null}$}}\nolimits,\mathop{\hbox{$\mathsf{null}$}}\nolimits)$

13 $\mathit{counter}\in\mathbb{N}$: a counter for generating element IDs,
initially 0

14

15 function $\mathop{\hbox{$\mathsf{values}$}}\nolimits():\mathbb{V}[]$

16 return _$\mathop{\hbox{$\mathsf{traverse}$}}\nolimits(\mathsf{null})$_

17

18 function
$\mathop{\hbox{$\mathsf{traverse}$}}\nolimits(\mathit{nodeID}:\mathsf{ID}):\mathbb{V}[]$

19 $\mathit{values}\leftarrow[]$

20 $(\mathit{node},\mathit{leftChildren},\mathit{rightChildren})\leftarrow$
the unique triple $\in\mathit{tree}$ such that $node.id=\mathit{nodeID}$

21 for  _$\mathit{childId}\in\mathit{leftChildren}$_ do
$\mathit{values}\leftarrow\mathit{values}+\mathop{\hbox{$\mathsf{traverse}$}}\nolimits(\mathit{childId})$

22 if  _$node.value\neq\bot$_ then
$\mathit{values}\leftarrow\mathit{values}+[\mathit{node.value}]$

23 for  _$\mathit{childId}\in\mathit{rightChildren}$_ do
$\mathit{values}\leftarrow\mathit{values}+\mathop{\hbox{$\mathsf{traverse}$}}\nolimits(\mathit{childId})$

24 return _$\mathit{values}$_

25

26 function
$\mathop{\hbox{$\mathsf{insert}$}}\nolimits(i:\mathbb{N},x:\mathbb{V})$

27 $\mathit{id}\leftarrow(\mathit{replicaID},\mathit{counter})$;
$\mathit{counter}\leftarrow\mathit{counter}+1$

28 $\mathit{leftOrigin}\leftarrow$ node for $(i-1)$-th value in
$\mathop{\hbox{$\mathsf{values}$}}\nolimits()$, or $\mathit{root}$ if $i=0$

29 $\mathit{rightOrigin}\leftarrow$ next node after $\mathit{leftOrigin}$ in
the tree traversal that includes tombstones

30 if
_$\nexists\mathit{id}^{\prime},v^{\prime}.\,\,(\mathit{id}^{\prime},v^{\prime},\mathit{leftOrigin}.\mathit{id},R)\in\mathit{tree}$_
then

31 $\mathit{node}\leftarrow(\mathit{id},x,\mathit{leftOrigin.id},R)$ // right
child of $\mathit{leftOrigin}$; see Figure 4(a)

32 else

33 $\mathit{node}\leftarrow(\mathit{id},x,\mathit{rightOrigin.id},L)$ // left
child of $\mathit{rightOrigin}$; see Figure 4(b)

34 broadcast _$(\mathop{\hbox{$\mathsf{insert}$}}\nolimits,node)$_ by causal
broadcast

35

36 on delivering $(\mathop{\hbox{$\mathsf{insert}$}}\nolimits,\mathit{node})$
by causal broadcast

37 $(\mathit{parent},\mathit{leftSibs},\mathit{rightSibs})\leftarrow$ the
unique triple $\in\mathit{tree}$ such that
$\mathit{parent.id}=\mathit{node}.\mathit{parent}$

38 if  _$\mathit{node.side}=R$_ then

39 $i\leftarrow$ least index such that
$\mathit{node.id}<\mathit{rightSibs}[i]$

40 insert $\mathit{node.id}$ into $\mathit{rightSibs}$ at index $i$

41 else

42 $i\leftarrow$ least index such that $\mathit{node.id}<\mathit{leftSibs}[i]$

43 insert $\mathit{node.id}$ into $\mathit{leftSibs}$ at index $i$

44 $\mathit{tree}\leftarrow\mathit{tree}\cup\\{(\mathit{node},[],[])\\}$

45

46

47 function $\mathop{\hbox{$\mathsf{delete}$}}\nolimits(i:\mathbb{N})$

48 $\mathit{node}\leftarrow$ node for $i$-th value in
$\mathop{\hbox{$\mathsf{values}$}}\nolimits()$

49 broadcast _$(\mathop{\hbox{$\mathsf{delete}$}}\nolimits,node.id)$_ by
causal broadcast

50

51 on delivering $(\mathop{\hbox{$\mathsf{delete}$}}\nolimits,id)$ by causal
broadcast

52 $(\mathit{node},\textunderscore,\textunderscore)\leftarrow$ the unique
triple $\in\mathit{tree}$ such that $node.id=id$

53 $node.value\leftarrow\bot$

54

55

Algorithm 1 Pseudocode for the Fugue algorithm.

##### Pseudocode

Algorithm 1 gives pseudocode for Fugue. The
$\mathop{\hbox{$\mathsf{values}$}}\nolimits$ and
$\mathop{\hbox{$\mathsf{traverse}$}}\nolimits$ functions are side-effect-free.
The $\mathop{\hbox{$\mathsf{insert}$}}\nolimits$ and
$\mathop{\hbox{$\mathsf{delete}$}}\nolimits$ functions construct an operation
message that is disseminated to all replicas via a causal broadcast protocol
[17, 18]; we assume that this protocol immediately delivers the message to the
sender without waiting for any network communication. Each replica updates its
tree when it receives the operation message by causal broadcast.

######  Theorem 1.

Algorithm 1 satisfies the strong list specification of Attiya et al. [4].

###### Proof:

For any execution, we must show that there is a total order $\prec$ over all
list elements (across all replicas), such that:

  1. (a)

At any time, calling $\mathsf{values}()$ on a replica returns the list of
values corresponding to all elements for which the replica received
$\mathsf{insert}$ messages, minus the elements for which it received
$\mathsf{delete}$ messages, in order $\prec$.

  2. (b)

Suppose a replica's $\mathsf{values}()$ query yields values corresponding to
elements $[a_{0},a_{1},\dots,a_{n-1}]$ just before the insert generator
$\mathsf{insert}(i,x)$ is called. Then the inserted element $e$ satisfies
$a_{0},a_{1},\dots,a_{i-1}\prec e\prec a_{i},a_{i+1},\dots,a_{n-1}$.

Let $\prec$ be the total order given by the depth-first in-order traversal on
the union of all replicas' local trees (with tombstone nodes overriding nodes
with the originally inserted value). To show (a), note that by the causal
order delivery assumption, a $\mathsf{delete}$ message is received after its
corresponding $\mathsf{insert}$ message. Therefore, on any given replica, the
set of tree nodes with $\mathit{value}\neq\bot$ are those nodes that have been
inserted but not deleted on that replica. These are exactly the nodes whose
values are returned by $\mathsf{values}()$, in the same order as $\prec$
because the same traversal is used.

To show (b), note that $\mathit{leftOrigin}$ and $\mathit{rightOrigin}$ are
consecutive elements in the tree traversal, and $\mathit{leftOrigin}=a_{i-1}$,
the non-tombstone node immediately preceding the insertion position. If
$\mathit{leftOrigin}$ has no right children, inserting the new node as a right
child of $\mathit{leftOrigin}$ makes the new node the immediate successor of
$\mathit{leftOrigin}$ in the tree traversal. If $\mathit{leftOrigin}$ does
have right children, $\mathit{rightOrigin}$ must be a descendant of
$\mathit{leftOrigin}$, and $\mathit{rightOrigin}$ must have no left children
(since otherwise $\mathit{leftOrigin}$ and $\mathit{rightOrigin}$ would not be
consecutive), and therefore inserting the new node as a left child of
$\mathit{rightOrigin}$ ensures the traversal visits the new child between
$\mathit{leftOrigin}$ and $\mathit{rightOrigin}$. In either case, the newly
inserted element appears between $a_{i-1}$ and $a_{i}$ in the traversal, as
required. ∎

…ing\n*bananas\n*apples\nFruit:\n*cake\n*bread\nBakery: Figure 5: Fugue tree
after executing the editing history in Figure 2. Since the two users'
insertions are in separate subtrees, a depth-first traversal does not
interleave them.

##  4 Formalizing Non-Interleaving

We have proven that Fugue satisfies the strong list specification (Theorem 1).
We now show that it also avoids the interleaving problem described in Section
2 except in specific, rare situations where some interleaving is inevitable.

Specifically, we show that a variant of Fugue, FugueMax, is _maximally non-
interleaving_ : FugueMax avoids interleaving of both forward and backward
insertions, to the maximum extent possible. We then show that Fugue differs
from FugueMax only rarely while allowing a simpler algorithm.

Intuitively, non-interleaving holds because concurrent edits end up in
different subtrees, which are traversed separately. This is illustrated in
Figure 5, which shows the Fugue representation of the editing history in
Figure 2.

###  4.1 Preliminary Definitions

In an execution using a replicated list, the _left origin_ of an element is
the element directly preceding its insertion position at the time of
insertion. Specifically, if the element was inserted by an
$\mathsf{insert}(i,x)$ call, then its left origin was at index $i-1$ at the
time of this call. If there was no such element ($i=0$), then its left origin
is a special symbol $\mathit{start}$. This definition coincides with the
$\mathit{leftOrigin}$ variable in Algorithm 1, except using $\mathit{start}$
instead of $\mathit{root}$. We sometimes denote the left origin of $A$ by
$A.\mathit{leftOrigin}$.

Dually to the definition of left origin, we define the _right origin_ of an
element to be the element directly following its insertion position at the
time of insertion, or the special symbol $\mathit{end}$ if no following
element exists. Specifically, the right origin is the element directly
following the left origin in _the list including tombstones (deleted
elements)_ , like the $\mathit{rightOrigin}$ variable in Algorithm 1. This
choice simplifies the analysis by letting us ignore deletions.

Define the _left-origin tree_ to be the tree of list elements in which each
element's parent is its left origin. Observe that the tree is rooted at
$\mathit{start}$, because every element was inserted either at the beginning
of the list, or after some existing element (i.e. an existing tree node). This
tree's definition is similar to causal trees [30] and timestamped insertion
trees [4].

Similarly, define the _right-origin tree_ to be the tree of list elements in
which each element's parent is its right origin. This tree is rooted at
$\mathit{end}$.

If list element $A$ had already been inserted at the time when list element
$B$ was inserted, we say that $A$ is _causally prior_ to $B$, and $B$ is
_causally later_ than $A$ (regardless of whether $A$ or $B$ were subsequently
deleted again). In particular, the left and right origins of a list element
are always causally prior to that element. When $A$ is neither causally prior
nor causally later than $B$, we say that $A$ and $B$ are _concurrent_. This
relation defines a partial order over list elements, and the causal broadcast
protocol in Algorithm 1 delivers the insertion operations for those list
elements in a linear extension of this partial order.

###  4.2 Defining Maximal Non-Interleaving

We already saw that the definition of non-interleaving by Kleppmann et al. [7]
is impossible to satisfy (Section 2.5). Finding a satisfiable definition
requires some care. Let us first consider non-interleaving for forward
insertions, like those in Figure 1.

######  Definition 2.

A replicated list algorithm is _forward non-interleaving_ if it satisfies the
strong list specification [4] and the following holds for all list elements
$A$ and $B$ in all possible list states: if $A$ is the left origin of $B$, and
$B$ appears earlier in the list than any other element that has $A$ as left
origin, then $A$ and $B$ are consecutive list elements.

This definition captures the idea that elements $A,B$ inserted in a forward
sequence should be consecutive—no other elements may interleave with the
sequence $AB$. In particular, this holds when $B$ is the _only_ element that
has $A$ as left origin. Once multiple elements $B,C$ have left origin $A$, we
cannot place all of them immediately after $A$. But we can still guarantee
that sequences inserted after $B$ and $C$ respectively are not interleaved:

######  Lemma 3.

Let a replicated list algorithm satisfy forward non-interleaving as defined in
Definition 2. Then it is also satisfies Kleppmann et al.'s definition of
forward non-interleaving [20, §4]: if two sequences $B_{1}...B_{m}$ and
$C_{1}...C_{n}$ are inserted from left to right concurrently at the same
starting position, then all $B_{j}$ are on the same side of all $C_{i}$ in the
final list order.

###### Proof:

Let $\prec$ be the global total order on list elements guaranteed by the
strong list specification. Without loss of generality, $B_{1}\prec C_{1}$. We
need to show that $B_{2},\dots,B_{m}\prec C_{1}$.

It is possible for a replica to be in a state that contains $C_{1}$, $B_{2}$,
and all causally prior elements (including $B_{1}$), but no others. Since
$C_{1}$ was inserted concurrently to $B_{1}$, $B_{2}$ is the only element in
this state that is causally later than $B_{1}$. Thus it is the only element
with left origin $B_{1}$. Then by forward non-interleaving, $B_{1}$ and
$B_{2}$ are consecutive. Together with $B_{1}\prec C_{1}$, this implies
$B_{2}\prec C_{1}$. Because this relation holds for one possible replica in
one state, the strong list specification requires it to hold in the final list
order.

A similar argument shows that $B_{3},\dots,B_{m}\prec C_{1}$. ∎

It is tempting to define ``backward non-interleaving'' analogously to forward
non-interleaving (replacing left origins with right origins), then define
``non-interleaving'' as the conjunction of forward and backward non-
interleaving.

Replica 1:Replica 2:Replica 3:insert(0, $A$)$\rightarrow$ _``A''_ insert(0,
$B$)$\rightarrow$ _``B''_ insert(0, $C$)$\rightarrow$
_``C''__``AC''__``BC''__``ABC''_ insert(1, $X$)$\rightarrow$
_``AXC''__``AXBC''_ Figure 6: An execution in which it is impossible to
achieve both forward and backward non-interleaving, but maximal non-
interleaving is possible.

However, there are exceptional executions in which forward non-interleaving
_forces_ us to interleave backward insertions. Figure 6 gives an example:
Starting from an empty list, three replicas concurrently insert $A$, $B$, and
$C$. Replica 3 receives all three elements and puts them in some order;
without loss of generality, it is $A\prec B\prec C$. Replica 1 receives $A$
and $C$, then inserts $X$ in between those elements to obtain $AXC$. Finally,
Replica 1 receives $B$.

Since $X$ is the only element with left origin $A$, forward non-interleaving
requires them to be consecutive: _AX_. Also, the strong list specification
requires that since $A\prec B\prec C$ on Replica 3, all other replicas must
place those elements in the same order. Thus the final list order must be
_AXBC_. But then $X$ and $C$ are not consecutive, even though $X$ is the only
element with right-origin $C$. This rules out the above version of backward
non-interleaving.

We do still want to mandate backward non-interleaving whenever it is possible.
When forward and backward non-interleaving are in conflict with each other, we
let forward non-interleaving take precedence, since forward (left-to-right)
insertions are more common in text editors.

######  Definition 4.

A replicated list algorithm is _maximally non-interleaving_ if it satisfies
the strong list specification [4] and the following holds for all list
elements $A$ and $B$ in all possible list states:

  1. (1)

(Forward non-interleaving) If $A$ is the left origin of $B$, and $B$ appears
earlier in the list than any other element that has $A$ as left origin, then
$A$ and $B$ are consecutive list elements.

  2. (2)

If $B$ is the right origin of $A$, and $A$ appears later in the list than any
other element that has $B$ as right origin, then $A$ and $B$ are consecutive
list elements, _unless_ Lemma 5 below says otherwise.

  3. (3)

If $A$ and $B$ have the same left origin and the same right origin, then the
element with the lower ID appears earlier in the list.

######  Lemma 5.

Given a replicated list algorithm that satisfies the strong list specification
and forward non-interleaving (condition (1)). Suppose $B$ is the right origin
of $A$, and $A$ appears later in the list than any other element that has $B$
as right origin, _but_ :

  1. i.

$A$ and $B$ have different left origins; and

  2. ii.

there is a $C$ in the current list state such that $A.\mathit{leftOrigin}\prec
C\prec B$ and $C$ is not a descendant of $A.\mathit{leftOrigin}$ in the left-
origin tree.

Then $A\prec C\prec B$, so $A$ and $B$ are not consecutive list elements.

We will prove Lemma 5 in the next section. For now, observe that the lemma
forces $X\prec B\prec C$ in the example of Figure 6. Thus the list order
_AXBC_ is allowed by maximal non-interleaving: the fact that $X$ and $C$ are
not consecutive is permitted due to the exception in condition (2).

Condition (3) is an arbitrary choice; two elements with the same left origin
and the same right origin were inserted concurrently at the exact same place,
so there is no reason to order them in a particular way. It turns out that
this arbitrary choice is the _only_ remaining degree of freedom after assuming
(1) and (2): we show in Section 4.5 that maximal non-interleaving uniquely
determines the list order.

Replica 1:Replica 2:Replica 3:insert(0, $A$)$\rightarrow$ _``A''_ insert(0,
$B$)$\rightarrow$ _``B''_ insert(0, $C$)$\rightarrow$
_``C''__``AC''__``AB''__``BC''__``ABC''_ insert(1, $X$)$\rightarrow$ _``AXC''_
insert(1, $Y$)$\rightarrow$
_``AYB''__``AXBC''__``AXYBC''__``AYBC''__``AXYBC''__``AYBC''__``AXYBC''_
Figure 7: An extension of the execution in Figure 6, demonstrating the
conditions of maximal non-interleaving. _start_ $A$$B$$C$$X$$Y$_end_
$A$$B$$C$$Y$$X$ Figure 8: Left- and right-origin trees for Figure 7. The Fugue
tree in this example is equivalent to the left-origin tree (all elements are
right children of their parent).

Figure 7 shows how maximal non-interleaving determines the list order in a
more complex execution; see Figure 8 for the final left- and right-origin
trees. We start as in Figure 6 with three replicas inserting $A$, $B$, and $C$
concurrently into an empty list. These three elements have the same left and
right origins (_start_ and _end_ respectively), so condition (3) requires them
to be in ID order; without loss of generality, assume $A\prec B\prec C$.
Replica 1 then receives $\\{A,C\\}$ and inserts $X$ between them, while
concurrently Replica 2 receives $\\{A,B\\}$ and inserts $Y$ between them. We
have already seen in Figure 6 that in the state _AXBC_ on Replica 1, condition
(1) requires _AX_ to be consecutive, and thus $X\prec B$ in the list order.
Moreover, $Y$ is the only element with right origin $B$, so condition (2)
requires _YB_ to be consecutive (nothing contradicts this requirement).
Finally, $X$ is the only element with right origin $C$, but since condition
Lemma 5 requires $X\prec B\prec C$, it is an exception from condition (2), and
thus _XC_ is not required to be consecutive. Thus, the only list order that
satisfies maximal non-interleaving in this example is _AXYBC_.

###  4.3 From Fugue to FugueMax

It turns out that in executions like Figure 7, Fugue might _not_ satisfy
maximal non-interleaving. Indeed, the previous paragraph explained that
maximal non-interleaving implies $X\prec Y$. But in the Fugue tree (Figure 8's
left side), $X$ and $Y$ are same-side siblings, hence traversed in the
lexicographic order of their IDs. This order might be $Y\prec X$.

We can repair this issue by changing the order of right-side siblings in the
Fugue tree: when right-side siblings $X$ and $Y$ have different right origins
$C\neq B$, we sort $X$ and $Y$ by the _reverse_ order of their right origins.
For example, in Figure 8's Fugue tree, $B\prec C$, so we should order $X\prec
Y$. That allows $Y$ to be consecutive with $B$, the leftmost right origin. We
learned of this reverse-right-origin technique from Gentle's modified Yjs
[25].

######  Definition 6.

_FugueMax_ is the replicated list algorithm that is identical to Fugue except
that its tree traversal visits right-side siblings in the _reverse_ order of
their right origins, breaking ties using the lexicographic order of their IDs.

Concretely, FugueMax's algorithm is identical to Fugue's Algorithm 1 except:

  1. 1.

When generating a right child (Line 1), the node is additionally tagged with
its right origin:
$\mathit{node}\leftarrow(\mathit{id},x,\mathit{leftOrigin.id},R,\mathbf{\mathit{rightOrigin.id}})$.

  2. 2.

On delivering a right child (Line 1), it uses the sibling order described
above: $i\leftarrow$ the least index such that
$\mathit{node.rightOrigin}\succ\mathit{rightSibs}[i].\mathit{rightOrigin}$ or
$\big{(}\mathit{node.rightOrigin}=$
$\mathit{rightSibs}[i].\mathit{rightOrigin}$ and
$\mathit{node.id}<\mathit{rightSibs}[i]\big{)}$, where $\succ$ is the existing
list order and $<$ is the lexicographic order on node IDs.

The proof that Fugue satisfies the strong list specification (Theorem 1) works
identically for FugueMax.

We show in Section 4.4 that FugueMax is maximally non-interleaving and that
Fugue is forward non-interleaving. We believe that Fugue's simpler algorithm
is worth its additional interleaving. Indeed, to create a situation where
Fugue and FugueMax differ, there must be right-side siblings with different
right origins; this requires multiple interacting concurrent updates, like in
Figure 7. These situations should be rare in practice. Also, in any such
situation, some interleaving is inevitable even in FugueMax—e.g., $X$ and $C$
are not consecutive in Figure 7.

###  4.4 FugueMax is Maximally Non-Interleaving

The goal of this section is to prove that FugueMax is maximally non-
interleaving (Theorem 9).

Recall that a depth-first pre-order traversal of a tree follows the rule:
visit a node, then traverse its children in some order (whereby all
descendants of a child are visited recursively before moving on to the next
child).

######  Lemma 7.

A replicated list algorithm that satisfies the strong list specification is
forward non-interleaving if and only if its list order is some depth-first
pre-order traversal of the left-origin tree.

###### Proof:

$(\Longleftarrow)$: In any list state, let $A$ and $B$ be list elements such
that $A$ is the left origin of $B$, and $B$ appears earlier in the list than
any other element that has $A$ as left origin. In the left-origin tree, $B$ is
the child of $A$ that appears earliest in the list. Thus the list's depth-
first pre-order traversal will visit $B$ immediately after $A$: $A$ and $B$
are consecutive list elements.

$(\Longrightarrow)$: To show that the list order is a depth-first pre-order
traversal of the left-origin tree, it suffices to prove:

  1. (a)

If $A$ is the parent of $B$ in the left-origin tree, then $A\prec B$ in the
list order.

  2. (b)

If $A$ and $D$ are siblings in the tree and $A\prec D$, then the entire
subtree rooted at $A$ precedes $D$ in the list order.

For statement (a), $A$ is the left origin of $B$, so $A\prec B$ by the strong
list specification.

For statement (b), first observe that $D$ is not causally later than $A$. We
show this by contradiction: assume $D$ is inserted in a list state that
already contains $A$. Since $A$ and $D$ are siblings in the left-origin tree,
$D.\mathit{leftOrigin}=A.\mathit{leftOrigin}$, and $A.\mathit{leftOrigin}\prec
A$ in the list order. At the time $D$ is inserted, $D.\mathit{leftOrigin}$ and
$D$ must be consecutive, implying $D\prec A$, which contradicts $A\prec D$.

Next, let $B$ be a child of $A$ in the left-origin tree. It is possible for a
replica to be in a state that contains $B$, $D$, and all causally prior
elements (including $A$), but no others. Every element $E\notin\\{B,D\\}$ in
this state is causally prior to either $B$ or $D$; however, if $E$ is causally
later than $A$, then $E$ cannot be causally prior to $D$, since this would
contradict the previous paragraph's finding that $A$ is not causally prior to
$D$. Therefore, any element of this state that is causally later than $A$ and
not equal to $B$ must be causally prior to $B$. Any element whose left origin
is $A$ must be causally later than $A$. Hence $B$ appears earlier in the list
than any other element whose left origin is $A$. By forward non-interleaving,
$A$ and $B$ are consecutive in this state. Thus $B\prec D$.

One can similarly prove that $B\prec D$ whenever $B$ is a grandchild, great-
grandchild, etc. of $A$, using induction on the depth of $B$. Hence all of the
elements in the subtree rooted at $A$ appear before $D$ in the list order. ∎

###### Proof:

By Lemma 7, the list order must be some depth-first pre-order traversal of the
left-origin tree. In any such traversal, $C$ appears later in the list order
than the entire subtree rooted at $A.\mathit{leftOrigin}$, because it appears
later than $A.\mathit{leftOrigin}$ and is not part of its subtree. In
particular, $A\prec C$. Meanwhile, $C\prec B$ by assumption. ∎

######  Lemma 8.

In any state of FugueMax (resp., Fugue), we have the following facts about
left origins.

  1. (a)

The left origin of an element $D$ is given by: starting at $D$, walk up the
FugueMax tree until you encounter a node that is a right child of its parent;
that node's parent is $D$'s left origin.

  2. (b)

Let $A$ and $B$ be list elements such that $A\prec B$. Then $B$ is a
descendant of $A$ in the FugueMax tree if and only if $B$ is a descendant of
$A$ in the left-origin tree.

###### Proof:

(a). Let $E$ be the alleged left origin for $D$. In the state just after
inserting $D$, list elements $E$ and $D$ are consecutive in FugueMax's tree
traversal. Since FugueMax satisfies the strong list specification (by the same
proof as Theorem 1), $E$ must be $D$'s left origin.

(b). $(\Longleftarrow)$: Assume $B$ is a child of $A$ in the left-origin tree,
that is, $B$ was immediately after $A$ in the list order when $B$ was
inserted. Then the FugueMax algorithm either made $B$ a right child of $A$ in
the FugueMax tree (if $A$ had no right child at the time of inserting $B$), or
a left child of a right descendant of $A$ (if $A$ had at least one right
child). In either case, $B$ is a descendant of $A$ in the FugueMax tree. By
induction we generalize to the case when $B$ is a descendant of $A$ in the
left-origin tree, using a similar argument at each tree level.

$(\Longrightarrow)$: Assume $B$ is a descendant of $A$ in the FugueMax tree
and $A\prec B$. If $B$ is a left child of its parent, $B$ appears before its
parent in the list order, so the parent cannot be $A$. Walking up the tree
from $B$, since there is an element before $B$ in the list order, we must
eventually reach an element that is a right child of its parent $P$. By (a),
$P$ must be the left origin of $B$. Either $P=A$, in which case $B$ is a child
of $A$ in the left-origin tree, or (by induction) $P$ is a descendant of $A$
in the left-origin tree. ∎

######  Theorem 9.

FugueMax satisfies conditions (1), (2), and (3) of Definition 4. Hence
FugueMax is maximally non-interleaving.

###### Proof:

Condition (1). Let $A$ and $B$ have the form in condition (1): $A$ is the left
origin of $B$, and $B$ appears earlier in the list than any other element that
has $A$ as left origin. We must prove that $A$ and $B$ are consecutive.

By Lemma 8(a), in the FugueMax tree, $B$ is the earliest among all nodes that
are either a right child of $A$ or a left descendant of a right child of $A$.
This is precisely the first node that FugueMax's tree traversal visits when
traversing the right children of $A$. Thus the traversal visits $B$
immediately after $A$: they are consecutive.

Condition (2). Let $A$ and $B$ have the form in condition (2): $B$ is the
right origin of $A$, $A$ appears later in the list than any other element that
has $B$ as right origin, and conditions (i) and (ii) in Lemma 5 are not both
true. We must prove that $A$ and $B$ are consecutive.

First suppose (i) is false, so that $A$ and $B$ have the same left origins. By
Lemma 8(b), $B$ is a descendant of $A.\mathit{leftOrigin}$ in the FugueMax
tree, so $A.\mathit{leftOrigin}$ must have at least one right child in the
FugueMax tree. Thus, when $A$ was inserted between $A.\mathit{leftOrigin}$ and
$B$, FugueMax's $\mathsf{insert}$ function made $A$ a left child of $B$.

Because $A$ is the last element in the list order with right origin $B$, $A$
is also the last to be traversed of the left children of $B$ in the FugueMax
tree. Hence if $A$ has no right children of its own, then FugueMax's tree
traversal visits $B$ immediately after $A$: they are consecutive. Otherwise,
let $D$ be a right child of $A$ such that $A$ did not have any other right
child when $D$ was inserted. Immediately before the insertion of $D$, $A$ did
not have a right-side child, so $A$ and $B$ were consecutive. Hence $D$'s
right origin is $B$ and $A\prec D$, contrary to assumption.

Next, suppose (i) is true and $A$ and $B$ are not consecutive. We must prove
that there exists a $C$ of the form given in (ii). Since $A$ and $B$ are not
consecutive, there exist one or more elements in between $A$ and $B$; take $C$
to be an in-between element that is not causally later than any other element
between $A$ and $B$. We have $A.\mathit{leftOrigin}\prec C\prec B$ because
$A.\mathit{leftOrigin}\prec A$. It remains to prove that $C$ is _not_ a
descendant of $A.\mathit{leftOrigin}$ in the left-origin tree.

We use proof by contradiction: assume that $C$ is a descendant of
$A.\mathit{leftOrigin}$ in the left-origin tree. Thus $C$ is either a
descendant of $A$ or a sibling (it cannot be a descendant of a sibling, since
otherwise the sibling would be a causally prior element between $A$ and $B$).

Case $C$ is a descendant of $A$ in the left-origin tree. In this case, $C$ is
causally later than both $A$ and $B$ and was inserted in between them. Because
$A$ appears later in the list than any other element that has $B$ as right
origin, $C$'s right origin is not $B$; instead, it must be some other element
between $A$ and $B$. But then $C$'s right origin is an in-between element that
is causally prior to $C$, contradicting our choice of $C$.

Case $C$ is a sibling of $A$ in the left-origin tree. That is, $A$ and $C$
have the same left origins.

At the time of $A$'s insertion, $A.\mathit{leftOrigin}$ and $B$ were
consecutive, and $A$ was inserted between them. By (i), $B$'s left origin is
not $A.\mathit{leftOrigin}$; thus, $B$ is not a descendant of
$A.\mathit{leftOrigin}$ in the left-origin tree; and by Lemma 8(b), $B$ is not
a descendant of $A.\mathit{leftOrigin}$ in the FugueMax tree either. Therefore
$A.\mathit{leftOrigin}$ did not have any right children in the FugueMax tree
at the time when $A$ was inserted, and FugueMax's $\mathsf{insert}$ function
made $A$ a right child of $A.\mathit{leftOrigin}$.

$C$ is also a right child of $A.\mathit{leftOrigin}$ in the FugueMax tree: it
is a descendant by Lemma 8(b); and if it were not a child, then its FugueMax
parent would be a causally prior in-between element. Also, by assumption,
$C$'s right origin is not $B$.

Thus $A$ and $C$ are right-side siblings in the FugueMax tree with different
right origins. This situation is similar to elements $X$ and $Y$ in Figure 8.
FugueMax's tree traversal then visits them in the reverse order of their right
origins. Since $A\prec C$, this implies that $C$'s right origin appears before
$B$ in the list order. But then $C$'s right origin is a causally prior in-
between element, again contradicting our choice of $C$.

Condition (3). Let $A$ and $B$ have the same left origin and the same right
origin. Then FugueMax's $\mathsf{insert}$ function assigned them the same
parent and side. FugueMax traverses these same-side siblings, with equal right
origins, in order by ID. ∎

###  4.5 Uniqueness of Maximally Non-Interleaving Order

We finish by showing that maximal non-interleaving uniquely determines the
list order. Specifically, any maximally non-interleaving replicated list
induces the same total order on elements as FugueMax. This reinforces our
claim that FugueMax is ``maximally'' non-interleaving—any additional
nontrivial constraints would be impossible to satisfy.

######  Theorem 10.

Let $L$ be a replicated list algorithm that is maximally non-interleaving.
Then $L$ is semantically equivalent to FugueMax. That is, in any execution,
$L$ orders its list of elements according to FugueMax's global total order
$\prec$ on elements.

###### Proof:

We will show that conditions (1), (2), and (3) of Definition 4 force $L$ to
use a specific list order. Since FugueMax is maximally non-interleaving, this
list order must be the same as FugueMax's.

First, condition (1) and Lemma 7 imply that $L$'s list order is some depth-
first pre-order traversal of the left-origin tree. Thus the only remaining
degree of freedom for $L$'s list order is the order of siblings within the
left-origin tree.

So, let $P$ be any element of $L$ or $\mathit{start}$, and let $S_{P}$ be the
set of list elements whose left origin is $P$. Consider the forest of $S_{P}$
elements in which each element's parent is its right origin, except that an
element has no parent if its right origin is not in $S_{P}$, or if its right
origin is $\mathit{end}$.

For any parent-child edge $(A,B)$ in $S_{P}$, $A$ and $B$ have the same left
origin ($P$). Thus $A$ and $B$ are _not_ an exception to condition (2). A
mirrored version of the proof of Lemma 7 shows that $L$'s list order, when
restricted to any tree $T$ in $S_{P}$'s forest, must be a depth-first post-
order traversal of $T$. (A depth-first post-order traversal satisfies the
rule: traverse a node's children in some order, then visit the node.) Siblings
within $T$ must be ordered by their IDs: they have the same left origins ($P$)
and right origins (their parent), so condition (3) applies. Conditions (2) and
(3) thus fully determine the order of elements in the same right-origin tree
$T$.

It remains to specify the relative order of $S_{P}$ elements that are in
different trees. We claim:

  1. (a)

If $D$ and $E$ are tree roots in $S_{P}$ with $D\prec E$, then the entire tree
rooted at $D$ (in $S_{P}$) appears before the entire tree rooted at $E$ in the
list order.

  2. (b)

$L$ orders the tree roots in $S_{P}$ identically to how FugueMax sorts a
node's right-side children: in the reverse order of their right origins,
breaking ties by ID. (One can show that the tree roots in $S_{P}$ are
precisely the right-side children of $P$ in FugueMax's tree.)

To prove these claims, we first argue that all tree roots in $S_{P}$ were
inserted concurrently. Indeed, in any state that already contains a tree root
(more generally, an element with left origin $P$), the element $R$ immediately
following $P$ must also have left origin $P$, because $L$'s list order is a
depth-first pre-order traversal of the left-origin tree. A new element
inserted into this state with left origin $P$ will have right origin $R\in
S_{P}$, so it is not a tree root in $S_{P}$.

We prove the two claims above in turn:

(a) Let $A$ and $D$ be tree roots in $S_{P}$ such that $D\prec A$ in $L$, and
let $B$ be a child of $A$. By the previous paragraph, $D$ is not causally
later than $A$. Then the claim follows by a mirrored version of the last two
paragraphs in Lemma 7's proof (using condition (2) in place of forward non-
interleaving).

(b) Let $D$ and $E$ be distinct tree roots in $S_{P}$. If $D$ and $E$ have the
same right origins, then by condition (3), $L$ must order them by ID.
Otherwise, let $R_{D}$ and $R_{E}$ be their right origins, and assume
$R_{E}\prec R_{D}$. We need to show that $D\prec E$.

It is possible for a replica to be in a state $\sigma$ that contains $D$, $E$,
and all causally prior elements, but no others. Since $E$ was inserted
directly between $P$ and $R_{E}$, no elements causally prior to $E$ are
between $P$ and $R_{E}$. Likewise, no elements causally prior to $D$ are
between $P$ and $R_{D}$, hence none are between $P$ and $R_{E}\prec R_{D}$.
Thus, $D$ and $E$ are the only elements in state $\sigma$ that can be between
$P$ and $R_{E}$.

$D$ and $E$ are indeed between $P$ and $R_{E}$: because all tree roots in
$S_{P}$ were inserted concurrently, $D$ and $E$ are the only elements in
$\sigma$ with left origin $P$; thus they immediately follow $P$ in $L$'s
depth-first pre-order traversal of the left-origin tree. So, state $\sigma$
contains either $\mathit{PDER_{E}}$ or $\mathit{PEDR_{E}}$ as a contiguous
subsequence. Condition (2) forces $L$ to use $\mathit{PDER_{E}}$: $E$ is the
last element in the list order with $R_{E}$ as its right origin, and there is
no $C$ that could grant us an exception, so $E$ and $R_{E}$ must be
consecutive. (By the same argument, _YB_ must be consecutive in Figure 7.)
Hence $D\prec E$. ∎

Observe that the above proof gives an alternate characterization of FugueMax's
list order:

  1. 1.

First, order elements by a depth-first pre-order traversal of the left-origin
tree.

  2. 2.

Second, order siblings within that tree by a depth-first post-order traversal
of their right-origin forest.

  3. 3.

Third, order roots within this forest that have different right origins by the
reverse order of their right origins. (In Fugue, instead order them by ID.)

  4. 4.

Fourth, order roots within this forest that have the same right origin, and
all other siblings in the forest, by ID.

We chose to present FugueMax (resp., Fugue) as a double-sided tree for
simplicity. But one could just as well use an algorithm based on the above
characterization.

##  5 Implementation and Evaluation

We implemented two variations of Fugue, and one of FugueMax, in TypeScript.
Each is written as a custom CRDT for the Collabs library [31]; Collabs
provides causal order delivery and other utilities.

The variations are:

  * •

Fugue: An optimized implementation of Algorithm 1 in 1132 lines of code. It
uses practical optimizations inspired by Yjs [32] and RGASplit [33]. In
particular, it condenses sequentially-inserted tree nodes into a single
``waypoint'' object instead of one object per node, and it uses Protocol
Buffers to efficiently encode update messages and saved documents. Collabs
v0.6.1 uses this implementation for its list CRDTs.

  * •

Fugue Simple: A direct implementation of Algorithm 1 in 298 lines of code. It
represents the state as a doubly-linked tree with one object per node, and it
uses GZIP'd JSON encodings.

  * •

FugueMax Simple: A direct implementation of Algorithm 1 with FugueMax's
modifications (see Section 4.3) in 435 lines of code.

###  5.1 Benchmarks

We evaluated our implementations using a modified version of Jahns's crdt-
benchmarks [34]. Our Fugue and FugueMax implementations, benchmark code, and
raw data are available on GitHub.111https://github.com/mweidner037/fugue

All experiments used Node.js v18.15.0 running on an Ubuntu 22.04.3 LTS desktop
with a 4-core Intel i7 CPU @1.90GHz and 16GB RAM. For each metric, we
performed 5 warmup trials followed by 10 measured trials; tables show mean
$\pm$ standard deviation for the 10 measured trials.

We also compared to existing implementations in the crdt-benchmarks
repository:

  * •

Automerge-Wasm (v0.5.0) is a CRDT with a JSON data model, implemented in Rust
and compiled to WebAssembly.222https://github.com/automerge/automerge Its list
CRDT is based on RGA [16].

  * •

Yjs (v13.6.8) is a JavaScript CRDT library [24]. Its list datatype is based on
YATA [35], and it is known for its good performance [32].

  * •

Y-Wasm (v0.16.10) is a Rust-to-WebAssembly variant of
Yjs.333https://github.com/y-crdt/y-crdt

Tables II and III show results from a benchmark that replays a real-world
text-editing trace [36], in which every keystroke of the writing process for
the LaTeX source of a 17-page paper [37] was captured. It consists of 182,315
single-character insert operations and 77,463 single-character delete
operations, resulting in a final document size of 104,852 characters (not
including tombstones). Each implementation processed the full trace
sequentially on a single replica. Results for additional benchmarks, including
microbenchmarks with concurrent operations, can be found in our GitHub
repository.

TABLE II: Saved document metrics. The plain text (without CRDT metadata or tombstones) is 105 kB in size. Implementation | Save size | Save time | Load time
---|---|---|---
Fugue |  $168\pm 0$ kB |  $20\pm 1$ ms |  $13\pm 2$ ms
Fugue Simple |  $1{,}021\pm 0$ kB |  $583\pm 5$ ms |  $334\pm 3$ ms
FugueMax Simple |  $1{,}237\pm 0$ kB |  $788\pm 11$ ms |  $522\pm 7$ ms
Automerge-Wasm |  $129\pm 0$ kB |  $180\pm 0$ ms |  $2{,}746\pm 6$ ms
Yjs |  $160\pm 0$ kB |  $17\pm 1$ ms |  $63\pm 6$ ms
Y-Wasm |  $160\pm 0$ kB |  $5\pm 1$ ms |  $15\pm 0$ ms

Table II considers the final saved document including CRDT metadata. In a
typical collaborative app, this saved document would be saved (possibly on a
server) at the end of each user session, and loaded at the start of the next
session. Thus save size determines disk/network usage, while save/load time
determines user-perceived save and startup latencies.

We see that Fugue is comparable to state-of-the-art Yjs on all three metrics,
and the CRDT metadata is only 60% of the literal text's size. Fugue Simple and
FugueMax Simple are worse but still usable in practice. FugueMax Simple has a
larger save size than Fugue Simple because it must additionally track right-
side children's right origins.

TABLE III: Metrics for replaying a character-by-character text editing trace with 260k operations. Implementation | Memory usage (MB) | Network bytes/op | Ops/sec (1,000s)
---|---|---|---
Fugue | $2.4\pm 0.0$ | $46\pm 0$ | $94\pm 5$
Fugue Simple | $64.8\pm 0.0$ | $151\pm 0$ | $17\pm 0$
FugueMax Simple | $71.9\pm 0.0$ | $188\pm 0$ | $16\pm 0$
Automerge-Wasm | – | $126\pm 0$ | $52\pm 0$
Yjs | $3.3\pm 0.2$ | $29\pm 0$ | $39\pm 0$
Y-Wasm | – | $29\pm 0$ | $7\pm 0$
TABLE IV: Metrics for the real text trace repeated 100 times sequentially. The literal text has size 10,485 kB. We exclude implementations that use excessive time or memory. Implementation | Save size (kB) | Save time (ms) | Load time (ms) | Memory usage (MB)
---|---|---|---|---
Fugue | $17{,}845\pm 0$ | $1{,}405\pm 35$ | $640\pm 8$ | $223\pm 0$
Yjs | $15{,}989\pm 0$ | $479\pm 35$ | $2{,}316\pm 423$ | $294\pm 17$

Table III shows performance metrics for live usage by a single user. Memory
usage shows the increase in heap used444Measured with Node.js’s
process.memoryUsage().heapUsed after garbage collection. We exclude
WebAssembly libraries because they do not use the JavaScript heap. (While
resident set size measures WebAssembly memory usage, it had frequent outliers
and gave implausible values for Automerge-Wasm.) from the start to the end of
the trace and thus approximates each list CRDT's in-memory size. Network
bytes/op shows the average size of the per-op messages sent to remote
collaborators. Ops/sec shows the average operation throughput; it reflects the
time to process an op and encode a message for remote collaborators. For
example, Fugue achieves 94,000 ops/sec, an average of 11 µs per operation.

We again see that Fugue is practical and comparable to Yjs. In particular, its
memory usage is only a few MB—about 23 bytes per character, or 13 bytes per
characters-including-tombstones. This refutes a common criticism of CRDTs for
collaborative text editing: namely, that they have too much per-character
memory overhead [38]. The memory overhead is worse for Fugue Simple (618
bytes/char) and FugueMax Simple (685 bytes/char), but the total is still well
within modern memory limits. For all Fugue variants, the network usage and
operation throughput are far from being bottlenecks, given that a typical user
types at $\approx 10$ chars/sec and a typical collaborative document has
$<100$ simultaneous users.

(a) Saved document size.

(b) Memory usage.

Figure 9: Metrics as a function of progress through the real text trace.

Figures 9(a) and 9(b) show how save size and memory usage vary throughout the
text editing trace. The size of the plain text (without CRDT metadata or
tombstones) is given for comparison. Observe that both metrics track the plain
text's size at a modest multiple, and save size even decreases when text is
deleted, despite tombstones.

Finally, Table IV shows selected metrics for the same text-editing trace but
repeated 100 times. The final document contains 10.5 million
characters—several times longer than Tolstoy's _War and Peace_. Nonetheless,
Fugue's performance remains tolerable: 18MB save size, less than 2 seconds to
save or load, and 223MB memory usage. Additionally, average network usage and
throughput (not shown) remain within a $2\times$ factor of Table III.

##  6 Conclusion

Interleaving of concurrent insertions at the same position is an undesirable
but largely ignored problem with many replicated list algorithms that are used
for collaborative text editing. Indeed, most CRDT and OT algorithms that we
surveyed exhibit interleaving anomalies. We also found that existing
definitions of non-interleaving are impossible to satisfy.

In this paper, we proposed a new definition, maximal non-interleaving. We also
introduced the Fugue and FugueMax list CRDTs and proved that FugueMax
satisfies maximal non-interleaving, while Fugue is simpler and falls only
slightly short of it. Our optimized implementation of Fugue has performance
comparable to the state-of-the-art Yjs library.

In future work we plan to formally analyze Sync9 [26] and Gentle's modified
version of the Yjs algorithm [25]. We conjecture that Sync9 is semantically
equivalent to Fugue, while the modified Yjs is semantically equivalent to
FugueMax. If this is indeed the case, then the modified Yjs is also maximally
non-interleaving. These algorithms are also CRDTs; in future work it would be
interesting to investigate whether maximally non-interleaving Operational
Transformation algorithms exist.

## Acknowledgments

We thank Seph Gentle for insightful discussions and feedback on a draft of
this paper. Matthew Weidner is supported by an NDSEG Fellowship sponsored by
the US Office of Naval Research. Martin Kleppmann is funded by the Volkswagen
Foundation and crowdfunding supporters including Rohit Kulshreshtha, Mintter,
and SoftwareMill.

## References

  * [1] C. A. Ellis and S. J. Gibbs, ``Concurrency control in groupware systems,'' in _ACM International Conference on Management of Data (SIGMOD)_ , 1989, pp. 399–407.
  * [2] D. A. Nichols, P. Curtis, M. Dixon, and J. Lamping, ``High-latency, low-bandwidth windowing in the Jupiter collaboration system,'' in _8th Annual ACM Symposium on User Interface and Software Technology (UIST)_ , 1995, pp. 111–120.
  * [3] C. Sun, X. Jia, Y. Zhang, Y. Yang, and D. Chen, ``Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems,'' _ACM Transactions on Computer-Human Interaction_ , vol. 5, no. 1, pp. 63–108, Mar. 1998.
  * [4] H. Attiya, S. Burckhardt, A. Gotsman, A. Morrison, H. Yang, and M. Zawirski, ``Specification and complexity of collaborative text editing,'' in _2016 ACM Symposium on Principles of Distributed Computing (PODC)_. ACM, 2016, p. 259–268.
  * [5] M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski, ``Conflict-free replicated data types,'' in _13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)_ , 2011, pp. 386–400.
  * [6] N. Preguiça, C. Baquero, and M. Shapiro, _Encyclopedia of Big Data Technologies_. Springer, 2018, ch. Conflict-Free Replicated Data Types (CRDTs).
  * [7] M. Kleppmann, V. B. F. Gomes, D. P. Mulligan, and A. R. Beresford, ``Interleaving anomalies in collaborative text editors,'' in _6th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC)_. ACM, Mar. 2019.
  * [8] M. Ressel, D. Nitsche-Ruhland, and R. Gunzenhäuser, ``An integrating, transformation-oriented approach to concurrency control and undo in group editors,'' in _ACM Conference on Computer Supported Cooperative Work (CSCW)_ , 1996, pp. 288–297.
  * [9] C. Sun and C. Ellis, ``Operational transformation in real-time group editors: Issues, algorithms, and achievements,'' in _ACM Conference on Computer Supported Cooperative Work (CSCW)_ , 1998, pp. 59–68.
  * [10] J. Day-Richter, ``What's different about the new Google Docs: Making collaboration fast,'' Sep. 2010. [Online]. Available: https://drive.googleblog.com/2010/09/whats-different-about-new-google-docs.html
  * [11] A. Imine, P. Molli, G. Oster, and M. Rusinowitch, ``Proving correctness of transformation functions in real-time groupware,'' in _8th European Conference on Computer Supported Cooperative Work (ECSCW)_ , 2003, pp. 277–293.
  * [12] G. Oster, P. Urso, P. Molli, and A. Imine, ``Proving correctness of transformation functions in collaborative editing systems,'' INRIA, Tech. Rep. RR-5795, 2005. [Online]. Available: https://hal.inria.fr/inria-00071213/
  * [13] ——, ``Data consistency for P2P collaborative editing,'' in _ACM Conference on Computer Supported Cooperative Work (CSCW)_ , 2006, pp. 259–268.
  * [14] N. Preguiça, J. M. Marques, M. Shapiro, and M. Letia, ``A commutative replicated data type for cooperative editing,'' in _29th IEEE International Conference on Distributed Computing Systems (ICDCS)_. IEEE, 2009, pp. 395–403.
  * [15] S. Weiss, P. Urso, and P. Molli, ``Logoot: A scalable optimistic replication algorithm for collaborative editing on P2P networks,'' in _29th IEEE International Conference on Distributed Computing Systems_ , 2009, pp. 404–412.
  * [16] H.-G. Roh, M. Jeon, J.-S. Kim, and J. Lee, ``Replicated abstract data types: Building blocks for collaborative applications,'' _Journal of Parallel and Distributed Computing_ , vol. 71, no. 3, pp. 354–368, 2011.
  * [17] K. P. Birman, A. Schiper, and P. Stephenson, ``Lightweight causal and atomic group multicast,'' _ACM Transactions on Computer Systems_ , vol. 9, no. 3, pp. 272 – 314, Aug. 1991.
  * [18] C. Cachin, R. Guerraoui, and L. Rodrigues, _Introduction to Reliable and Secure Distributed Programming_ , 2nd ed. Springer, 2011.
  * [19] B. Nédelec, P. Molli, A. Mostefaoui, and E. Desmontils, ``LSEQ: An adaptive structure for sequences in distributed collaborative editing,'' in _ACM Symposium on Document Engineering (DocEng)_. ACM, 2013, pp. 37–46.
  * [20] M. Kleppmann, V. B. F. Gomes, D. P. Mulligan, and A. R. Beresford, ``OpSets: Sequential specifications for replicated datatypes (extended version),'' 2018\. [Online]. Available: https://arxiv.org/abs/1805.04263
  * [21] C. Sun, D. Sun, Agustina, and W. Cai, ``Real differences between OT and CRDT for co-editors,'' Oct. 2018. [Online]. Available: https://arxiv.org/abs/1810.02137
  * [22] M. Suleiman, M. Cart, and J. Ferrié, ``Serialization of concurrent operations in a distributed collaborative environment,'' in _ACM International Conference on Supporting Group Work (GROUP)_. ACM, Nov. 1997, pp. 435–445.
  * [23] G. Oster, P. Molli, P. Urso, and A. Imine, ``Tombstone transformation functions for ensuring consistency in collaborative editing systems,'' in _9th IEEE International Conference on Collaborative Computing_ , 2006.
  * [24] K. Jahns, ``Yjs,'' GitHub repository, Dec. 2022. [Online]. Available: https://github.com/yjs/yjs
  * [25] S. Gentle, ``Reference CRDTs,'' GitHub repository, Oct. 2021. [Online]. Available: https://github.com/josephg/reference-crdts
  * [26] G. Little and M. Toomim, ``Sync9: a peer-to-peer synchronizer,'' URL: https://braid.org/algorithms/sync9, archived at https://perma.cc/W2DL-38RF, source code at https://github.com/braid-org/braidjs/blob/21df3b0/sync9/sync9.js, 2021.
  * [27] M. Kleppmann, ``Insertion interleaving test,'' Feb. 2018. [Online]. Available: https://github.com/ept/insert-interleaving
  * [28] A. R. Chandrassery, Personal communication, 2021.
  * [29] M. Kleppmann, ``Moving elements in list CRDTs,'' in _7th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC)_. ACM, 2020.
  * [30] V. Grishchenko, ``Citrea and Swarm: Partially ordered op logs in the browser: Implementing a collaborative editor and an object sync library in JavaScript,'' in _1st Workshop on Principles and Practice of Eventual Consistency (PaPEC)_. ACM, 2014.
  * [31] M. Weidner, H. Qi, M. Kjaer, R. Pradeep, B. Geordie, Y. Zhang, G. Schare, X. Tang, S. Xing, and H. Miller, ``Collabs: A flexible and performant crdt collaboration framework,'' 2023.
  * [32] K. Jahns, ``Are CRDTs suitable for shared editing?'' Blog post, Aug. 2020. [Online]. Available: https://blog.kevinjahns.de/are-crdts-suitable-for-shared-editing/
  * [33] L. Briot, P. Urso, and M. Shapiro, ``High responsiveness for group editing CRDTs,'' in _19th International Conference on Supporting Group Work (GROUP)_. ACM, Nov. 2016, pp. 51–60.
  * [34] K. Jahns, ``CRDT benchmarks,'' 2022, https://github.com/dmonad/crdt-benchmarks/.
  * [35] P. Nicolaescu, K. Jahns, M. Derntl, and R. Klamma, ``Near real-time peer-to-peer shared editing on extensible data types,'' in _19th International Conference on Supporting Group Work (GROUP)_. ACM, Nov. 2016, pp. 39–49.
  * [36] M. Kleppmann, ``Benchmarking resources for Automerge,'' 2020. [Online]. Available: https://github.com/automerge/automerge-perf
  * [37] M. Kleppmann and A. R. Beresford, ``A conflict-free replicated JSON datatype,'' _IEEE Transactions on Parallel and Distributed Systems_ , vol. 28, no. 10, pp. 2733–2746, Apr. 2017.
  * [38] D. Sun, C. Sun, A. Ng, and W. Cai, ``Real differences between OT and CRDT in correctness and complexity for consistency maintenance in co-editors,'' _Proceedings of the ACM on Human-Computer Interaction_ , vol. 4, no. CSCW1, May 2020.

##  Appendix A Problems with various algorithms

###  A.1 Examples of interleaving

We give brief justifications of the interleaving claims ($\medblackcircle$) in
Table I. Terminology and notation are as in the source cited for each
algorithm. For each algorithm we give a minimal example, in each case starting
with an empty text document:

  * •

One user inserts $a$ followed by $b$, while concurrently another user inserts
$x$. An algorithm exhibits forward interleaving (Definition 2) if a possible
merged outcome is $\mathit{axb}$.

  * •

One user inserts $b$, and then prepends $a$ before $b$; concurrently another
user inserts $x$. An algorithm exhibits backward interleaving if a possible
merged outcome is $\mathit{axb}$.

####  A.1.1 adOPTed and TTF forward interleaving

adOPTed [8] and TTF [23] use essentially the same transformation function for
concurrent insertions. We use the notation from TTF: an insertion operation is
denoted $\mathit{ins}(p,c,s)$, where $p$ is the index at which to insert, $c$
is the inserted character, and $s$ is the ID of the site (i.e., replica) on
which the operation was generated.

To demonstrate forward interleaving, replica $A$ generates
$\mathit{ins}(1,a,A)$ followed by $\mathit{ins}(2,b,A)$. Concurrently, replica
$B$ generates $\mathit{ins}(1,x,B)$. Assume $A<B$ and consider the execution
at $B$:

  1. 1.

$B$ executes $\mathit{ins}(1,x,B)$, so the document is $x$.

  2. 2.

When $B$ receives $\mathit{ins}(1,a,A)$, it computes
$T(\mathit{ins}(1,a,A),\mathit{ins}(1,x,B))=\mathit{ins}(1,a,A)$
since $1=1\wedge A<B$, so it inserts $a$ before $x$, yielding $\mathit{ax}$.

  3. 3.

When $B$ receives $\mathit{ins}(2,b,A)$, it computes
$T(\mathit{ins}(2,b,A),\mathit{ins}(1,x,B))=\mathit{ins}(3,b,A)$
since $2>1$, so it inserts $b$ after $x$, yielding $\mathit{axb}$.

####  A.1.2 adOPTed/TTF backward interleaving (multi-replica)

To demonstrate backward interleaving, we use three replicas, $A$, $B$, and $C$
with $A<B<C$. First $C$ generates $\mathit{ins}(1,b,C)$, which is sent to $A$,
and then $A$ generates $\mathit{ins}(1,a,A)$. Concurrently, $B$ generates
$\mathit{ins}(1,x,B)$. Consider the execution at replica $B$:

  1. 1.

$B$ executes $\mathit{ins}(1,x,B)$, so the document is $x$.

  2. 2.

When $B$ receives $\mathit{ins}(1,b,C)$, it computes
$T(\mathit{ins}(1,b,C),\mathit{ins}(1,x,B))=\mathit{ins}(2,b,C)$
since $1=1\wedge C>B$, so it inserts $b$ after $x$, yielding $\mathit{xb}$.

  3. 3.

When $B$ receives $\mathit{ins}(1,a,A)$, it computes
$T(\mathit{ins}(1,a,A),\mathit{ins}(1,x,B))=\mathit{ins}(1,a,A)$
since $1=1\wedge A<B$, so it inserts $a$ before $x$, yielding $\mathit{axb}$.

####  A.1.3 Jupiter forward interleaving

Jupiter [2] is based on a single server that determines a total order of all
operations, and it always transforms a client operation and a server operation
with respect to each other. When there are multiple clients and an operation
from one client has been transformed and applied by the server, that
transformed operation is considered a server operation from the point of view
of the other clients (even though the operation actually originated on a
client).

The Jupiter paper [2] does not explicitly specify the transformation function
for concurrent insertions, it only describes it verbally as: ``We arbitrarily
chose to put server text first if both [i.e. server and client] try to insert
at the same spot.'' We show that even this informal definition implies that
the algorithm exhibits forward interleaving.

Starting with an empty document, assume that client $A$ generates
$\mathit{ins}(1,a)$ followed by $\mathit{ins}(2,b)$, and concurrently client
$B$ generates $\mathit{ins}(1,x)$. Consider the execution at the server:

  1. 1.

Assume that client $A$'s $\mathit{ins}(1,a)$ is the first operation to reach
the server, so the server simply applies it, resulting in the document $a$.

  2. 2.

Next, client $B$'s $\mathit{ins}(1,x)$ reaches the server. Since
$\mathit{ins}(1,a)$ was concurrently applied by the server, we have two
concurrent insertions at the same position. Per the rule for such insertions,
the server's character, that is $a$, is placed first, and the client's $x$
second. This means $B$'s operation is transformed to $\mathit{ins}(2,x)$ and
the server's document now reads $\mathit{ax}$.

  3. 3.

Finally, client $A$'s $\mathit{ins}(2,b)$ reaches the server. Concurrently,
the server has now performed $\mathit{ins}(2,x)$, which is the transformed
form of $B$'s operation. Again we have two concurrent insertions at the same
position, in this case at index 2. Per the rule above we place the server's
character $x$ first, and the client's character $b$ second. This means $A$'s
operation is transformed to $\mathit{ins}(3,b)$ and the server's document now
reads $\mathit{axb}$, exhibiting forward interleaving.

If the rule is changed to place the client's insertion first and the server's
insertion second in the case of concurrent insertions at the same position,
the algorithm exhibits backward interleaving instead of forward interleaving.

####  A.1.4 GOT forward interleaving

Strictly speaking, GOT is an OT control algorithm that is not specific to
text; here we use GOT in conjunction with the transformation functions for
text editing that are specified in the same paper [3]. For insertions, those
functions are an inclusion transformation $IT\\_II$ and an exclusion
transformation $ET\\_II$.

To demonstrate forward interleaving, replica $A$ generates
$\mathit{Insert}[a,1]$ followed by $\mathit{Insert}[b,2]$, while concurrently
replica $B$ generates $\mathit{Insert}[x,1]$. Let the total order on these
operations be
$\mathit{Insert}[a,1]<\mathit{Insert}[x,1]<\mathit{Insert}[b,1]$; this order
is possible in the GOT timestamping scheme. Consider the execution of
operations at a replica that receives them in ascending order, so that we can
skip the undo/do/redo process. That replica will go through the following
steps:

  1. 1.

Receive $\mathit{Insert}[a,1]$. We now have $HB=[\mathit{Insert}[a,1]]$, and
the document is $a$.

  2. 2.

Receive $\mathit{Insert}[x,1]$. This operation is concurrent with all
operations in $HB$, so it is transformed as follows:

$\displaystyle EO_{\mathit{new}}$
$\displaystyle=LIT(\mathit{Insert}[x,1],HB[1,1])$
$\displaystyle=IT\\_II(\mathit{Insert}[x,1],\mathit{Insert}[a,1])$
$\displaystyle=\mathit{Insert}[x,2]$

resulting in $HB=[\mathit{Insert}[a,1],\mathit{Insert}[x,2]]$ and the document
$\mathit{ax}$.

  3. 3.

Receive $\mathit{Insert}[b,2]$. This operation is dependent on $HB[1]$ and
concurrent with $HB[2]$, so it is transformed as follows:

$\displaystyle EO_{\mathit{new}}$
$\displaystyle=LIT(\mathit{Insert}[b,2],HB[2,2])$
$\displaystyle=IT\\_II(\mathit{Insert}[b,2],\mathit{Insert}[x,2])$
$\displaystyle=\mathit{Insert}[b,3]$

so $HB=[\mathit{Insert}[a,1],\mathit{Insert}[x,2],\mathit{Insert}[b,3]]$ and
the document is $\mathit{axb}$.

We discuss behavior of backward insertions in GOT in Appendix A.2.

####  A.1.5 SOCT2, Logoot, and LSEQ

Forward and backward interleaving in implementations of SOCT2 [22], Logoot
[15], and LSEQ [19] are demonstrated in an open source repository [27].

####  A.1.6 WOOT forward interleaving

The WOOT algorithm derives a partial order from the left and right origins of
each inserted character, and then defines the document to be a unique linear
extension of this partial order [13]. The notation $\mathit{ins}(a\prec x\prec
b)$ means that the character $x$ is inserted between $a$ and $b$. $c_{b}$
marks the beginning and $c_{e}$ marks the end of the document. When a replica
receives an operation from another replica, a recursive function IntegrateIns
determines where the insertion should be placed.

To demonstrate forward interleaving, replica $A$ generates
$\mathit{ins}(c_{b}\prec a\prec c_{e})$ to insert $a$, followed by
$\mathit{ins}(a\prec b\prec c_{e})$ to insert $b$. Concurrently, $B$ generates
$\mathit{ins}(c_{b}\prec x\prec c_{e})$ to insert $x$. Assume the ordering on
the inserted characters' IDs is $a<_{\mathit{id}}x<_{\mathit{id}}b$. Consider
the execution at replica $B$:

  1. 1.

To apply $\mathit{ins}(c_{b}\prec x\prec c_{e})$, calling
$\mathrm{IntegrateIns}(x,c_{b},c_{e})$ results in the document $x$.

  2. 2.

To apply $\mathit{ins}(c_{b}\prec a\prec c_{e})$, calling
$\mathrm{IntegrateIns}(a,c_{b},c_{e})$ computes $S^{\prime}=x$ and
$L=c_{b}xc_{e}$. The loop stops at $i=1$ because $x>_{\mathit{id}}a$, so we
recursively call the function $\mathrm{IntegrateIns}(a,c_{b},x)$, resulting in
the document $ax$.

  3. 3.

To apply $\mathit{ins}(a\prec b\prec c_{e})$, calling
$\mathrm{IntegrateIns}(b,a,c_{e})$ computes $S^{\prime}=x$ and
$L=c_{b}xc_{e}$. The loop stops at $i=2$ because $x<_{\mathit{id}}b$, so we
recursively call the function $\mathrm{IntegrateIns}(b,x,c_{e})$, resulting in
the document $\mathit{axb}$.

####  A.1.7 Treedoc forward and backward interleaving

To demonstrate forward interleaving in Treedoc [14], replica $A$ generates
$\mathit{insert}(p_{a},a)$ followed by $\mathit{insert}(p_{b},b)$, while
concurrently replica $B$ generates $\mathit{insert}(p_{x},x)$. These
operations are assigned position identifiers $p_{a}=[(1:d_{a})]$,
$p_{b}=[1(1:d_{b})]$, and $p_{x}=[(1:d_{x})]$, where $d_{a}$, $d_{b}$, and
$d_{x}$ are disambiguators. Assume $d_{a}<d_{x}$; then the order on position
identifiers is $p_{a}<p_{x}<p_{b}$, resulting in the document _axb_.

To demonstrate backward interleaving in Treedoc, replica $A$ generates
$\mathit{insert}(p_{b},b)$ and then prepends $\mathit{insert}(p_{a},a)$, while
concurrently replica $B$ generates $\mathit{insert}(p_{x},x)$. These
operations are assigned position identifiers $p_{b}=[(0:d_{b})]$,
$p_{a}=[0(0:d_{a})]$, and $p_{x}=[(0:d_{x})]$, where $d_{b}$, $d_{a}$, and
$d_{x}$ are disambiguators. Assume $d_{x}<d_{b}$; then the order on position
identifiers is $p_{a}<p_{x}<p_{b}$, resulting in the document _axb_.

####  A.1.8 RGA backward interleaving

To demonstrate backward interleaving in RGA [16], replica $A$ generates
$\mathit{Insert}(1,b)$ followed by prepending $\mathit{Insert}(1,a)$, while
concurrently replica $B$ generates $\mathit{Insert}(1,x)$. The insertion of
$b$ is assigned an s4vector of $\vec{v}_{b}=\langle 0,A,1,0\rangle$, the
insertion of $a$ an s4vector of $\vec{v}_{a}=\langle 0,A,2,0\rangle$, and the
insertion of $x$ an s4vector of $\vec{v}_{x}=\langle 0,B,1,0\rangle$. Assuming
$A<B$, the order on these s4vectors is
$\vec{v}_{b}\prec\vec{v}_{x}\prec\vec{v}_{a}$. The left cobject (i.e., left
origin) of all three operations is nil, and therefore the three elements are
placed in their list in descending s4vector order, resulting in the document
_axb_.

####  A.1.9 Yjs backward interleaving (multi-replica)

Yjs [24] exhibits interleaving only in a limited case: when insertions occur
in backward order across multiple replica IDs. The following code demonstrates
such interleaving in Yjs version 13.6.8. Our code repository contains a
runnable copy of this code.

    // Set up three replicas
    const Y = require(’yjs’)
    let doc1 = new Y.Doc(); doc1.clientID = 1
    let doc2 = new Y.Doc(); doc2.clientID = 2
    let doc3 = new Y.Doc(); doc3.clientID = 3

    // Replica 3 inserts ’b’
    doc3.getArray().insert(0, [’b’])

    // Replica 1 inserts ’a’ before ’b’
    Y.applyUpdateV2(doc1,
      Y.encodeStateAsUpdateV2(doc3,
        Y.encodeStateVector(doc1)))
    doc1.getArray().insert(0, [’a’])

    // Replica 2 concurrently inserts ’x’
    doc2.getArray().insert(0, [’x’])

    // Prints the merged document: "axb"
    Y.applyUpdateV2(doc1,
      Y.encodeStateAsUpdateV2(doc2,
        Y.encodeStateVector(doc1)))
    console.log(doc1.getArray().toArray().join(’’))

###  A.2 GOT character reordering

We found that in the case of concurrent backward insertions, GOT exhibits an
anomaly that is worse than interleaving: it reorders characters so that they
appear in a different order from what the user typed, violating the replicated
list specification. In the following example, replica $A$ inserts $ab$ in
backward order, while $B$ concurrently inserts $x$, and the resulting document
reads $xba$ — the $a$ and $b$ are reordered! Like in Appendix A.1.4, we refer
to the combination of the GOT control algorithm with the transformation
functions specified in the same paper [3].

Assume replica $A$ generates $\mathit{Insert}[b,1]$ followed by
$\mathit{Insert}[a,1]$, while concurrently replica $B$ generates
$\mathit{Insert}[x,1]$. Let the total order on these operations be
$\mathit{Insert}[x,1]<\mathit{Insert}[b,1]<\mathit{Insert}[a,1]$, which is
consistent with causality. Consider the execution of operations at a replica
that receives them in ascending order. That replica will go through the
following steps:

  1. 1.

Receive $\mathit{Insert}[x,1]$. We now have the history buffer
$HB=[\mathit{Insert}[x,1]]$, and the document is $x$.

  2. 2.

Receive $\mathit{Insert}[b,1]$. This operation is concurrent with all
operations in $HB$, so it is transformed as follows:

$\displaystyle EO_{\mathit{new}}$
$\displaystyle=LIT(\mathit{Insert}[b,1],HB[1,1])$
$\displaystyle=IT\\_II(\mathit{Insert}[b,1],\mathit{Insert}[x,1])$
$\displaystyle=\mathit{Insert}[b,2]$

resulting in $HB=[\mathit{Insert}[x,1],\mathit{Insert}[b,2]]$ and the document
$\mathit{xb}$.

  3. 3.

Receive $\mathit{Insert}[a,1]$. Now $HB[1]$ is concurrent to the new
operation, but $HB[2]$ causally precedes it. Therefore
$EOL=[\mathit{Insert}[b,2]]$ and

$\displaystyle EOL^{\prime}$
$\displaystyle=[LET(\mathit{Insert}[b,2],HB[1,1]^{-1})]$
$\displaystyle=[ET\\_II(\mathit{Insert}[b,2],\mathit{Insert}[x,1])]$
$\displaystyle=[\mathit{Insert}[b,1]]$ $\displaystyle
O^{\prime}_{\mathit{new}}$
$\displaystyle=LET(\mathit{Insert}[a,1],EOL^{\prime-1})$
$\displaystyle=ET(\mathit{Insert}[a,1],\mathit{Insert}[b,1])$
$\displaystyle=\mathit{Insert}[a,1]$ $\displaystyle EO_{\mathit{new}}$
$\displaystyle=LIT(O^{\prime}_{\mathit{new}},HB[1,2])$
$\displaystyle=IT\\_II(IT\\_II(\mathit{Insert}[a,1],\mathit{Insert}[x,1]),$
$\displaystyle\hskip 43.0pt\mathit{Insert}[b,2])$
$\displaystyle=IT\\_II(\mathit{Insert}[a,2],\mathit{Insert}[b,2])$
$\displaystyle=\mathit{Insert}[a,3]$

When $EO_{\mathit{new}}$ is applied, we obtain the incorrect document state
$xba$.

The GOT paper [3, Definition 9] specifies that the transformation functions
must satisfy a reversibility requirement, $IT(ET(O_{a},O_{b}),O_{b})=O_{a}$.
However, the insert/insert transformation functions in Section 9 of the same
paper do not meet this requirement. Let $O_{a}=\mathit{Insert}[a,1]$ and
$O_{b}=\mathit{Insert}[b,1]$. Then

$\displaystyle IT(ET(O_{a},O_{b}),O_{b})$
$\displaystyle\quad=IT\\_II(ET\\_II(\mathit{Insert}[a,1],\mathit{Insert}[b,1]),\mathit{Insert}[b,1])$
$\displaystyle\quad=IT\\_II(\mathit{Insert}[a,1],\mathit{Insert}[b,1])$
$\displaystyle\quad=\mathit{Insert}[a,2]\neq O_{a}$

We believe that this issue is not a typo or a similarly easy fix, but rather a
deeper conceptual problem with the GOT algorithm.

_``a''__``a''_ insert(1, $e$)$\rightarrow$ _``ae''_ $\mathit{ins}_{e}=$
$(e,t_{e},t_{a},\emptyset)$ insert(1, $c$)$\rightarrow$ _``ac''_
$\mathit{ins}_{c}=$ $(c,t_{c},t_{a},\emptyset)$ insert(1, $d$)$\rightarrow$
_``ade''_ $\mathit{ins}_{d}=$ $(d,t_{d},t_{a},\\{t_{e}\\})$
_``ace''__``acde''_ insert(1, $b$)$\rightarrow$ _``abce''_ $\mathit{ins}_{b}=$
$(b,t_{b},t_{a},\\{t_{c},t_{e}\\})$ ?? Figure 10: Execution that leads to
divergence in Kleppmann et al. [7]'s non-interleaving variant of RGA.

###  A.3 Non-interleaving RGA does not converge

As explained in Section 2.5, Kleppmann et al. [7] previously attempted to
design a non-interleaving text CRDT, but this algorithm does not converge. We
now give an example of this problem, which was found by Chandrassery [28].

The algorithm is a variant of Attiya et al. [4]'s timestamped insertion tree
(which is a reformulation of RGA [16]). Each insertion operation includes the
ID of a _reference element_ (after which the new character should be
inserted), and additionally this algorithm includes the set of existing
characters with the same reference element. When determining the order of
characters with the same reference element, this additional metadata is taken
into account.

The correctness of the algorithm depends on a strict total ordering relation
$<$ that determines the order in which characters with the same reference
element should appear in the document. However, it is possible to construct
executions in which three insertion operations $x$, $y$, and $z$ are ordered
$x<y$, $y<z$, and $z<x$, violating the asymmetry property of the total order.
If $<$ is not a total order, the order of characters in the document is
ambiguous, and so the algorithm cannot guarantee that replicas converge to the
same state.

Figure 10 shows an execution that triggers the problem. Each insertion
operation is a tuple $(a,t,r,e)$ where $a$ is the character being inserted,
$t$ is the timestamp (unique ID) of the operation, $r$ is the timestamp of the
reference character (immediate predecessor at the time the operation was
generated), and $e$ is the set of siblings (operations with the same reference
character at the time the operation was generated).

Assume $t_{e}<t_{c}<t_{d}<t_{b}$. To determine the total order of operations,
we first apply the rule that $\mathit{op}_{1}<\mathit{op}_{2}$ if
$\mathit{op}_{1}$'s timestamp appears in $\mathit{op}_{2}$'s siblings, which
gives us:

$\displaystyle\mathit{ins}_{e}=(e,t_{e},t_{a},\emptyset)$
$\displaystyle<(d,t_{d},t_{a},\\{t_{e}\\})=\mathit{ins}_{d}$
$\displaystyle\mathit{ins}_{c}=(c,t_{c},t_{a},\emptyset)$
$\displaystyle<(b,t_{b},t_{a},\\{t_{c},t_{e}\\})=\mathit{ins}_{b}$
$\displaystyle\mathit{ins}_{e}=(e,t_{e},t_{a},\emptyset)$
$\displaystyle<(b,t_{b},t_{a},\\{t_{c},t_{e}\\})=\mathit{ins}_{b}$

Next, we compare $\mathit{ins}_{b}$ and $\mathit{ins}_{d}$ using the rule for
concurrent operations:

$\displaystyle\min(\\{t_{b}\\}\cup\\{t_{c},t_{e}\\}-\\{t_{e}\\})=t_{c}$
$\displaystyle\min(\\{t_{d}\\}\cup\\{t_{e}\\}-\\{t_{c},t_{e}\\})=t_{d}$
$\displaystyle t_{c}<t_{d},\text{ therefore:
}\mathit{ins}_{b}<\mathit{ins}_{d}$

Finally, we compare $\mathit{ins}_{c}$ and $\mathit{ins}_{d}$ using the rule
for concurrent operations:

$\displaystyle\min(\\{t_{c}\\}\cup\emptyset-\\{t_{e}\\})=t_{c}$
$\displaystyle\min(\\{t_{d}\\}\cup\\{t_{e}\\}-\emptyset)=t_{e}$ $\displaystyle
t_{e}<t_{c},\text{ therefore: }\mathit{ins}_{d}<\mathit{ins}_{c}$

We now have $\mathit{ins}_{c}<\mathit{ins}_{b}$,
$\mathit{ins}_{b}<\mathit{ins}_{d}$, and $\mathit{ins}_{d}<\mathit{ins}_{c}$.
This violates the requirement that $<$ is a total order. Therefore, the order
of characters in the document is not uniquely determined, and we cannot
guarantee that replicas will converge to the same state.