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

Strips of edits have identifiers.

Identifiers have a total order; when strips are collected from all clients each client can sort edits in to the total order and use that ordering to reconstruct the document.

Identifiers in Fugue trees are basically paths down the binary tree.

Insert: Find the index X to insert at, then construct an identifier between X and X-1. If X-1 has no right edge then add the node there. If X-1 has a right edge then add the node on the left edge of X. Broadcast the new node, the new node's parent ID, and if the node belongs to the left or right leaf of the parent.

Delete: create a message with a target node ID. This message replaces the node with a tombstone indicating it has been deleted at some point.

Tombstones are never deleted. They are skipped when traversing a tree but they may have children which are still alive. Tombstones may also be used as anchors when inserting new nodes.

Fugue is described and proved using a variant binary tree. There is also "Fugue-List" which uses a linear list structure but with similar identifier names. This variant is only described as pseudocode; its primarily based on a for-loop which navigates the lists in a way that simulates walking through identifiers that make up paths of a tree.

It looks like the paper treats each character of a string as its own cell with its own positions. Then the implementation is set with optimizing this by combining adjacent strings which have not become cut points. So the theory is like this:

F
 O
  O
   B
    A
     R

While implementations are left to work out optimizing this situation. Such as storing it as FOOBAR until an insertion happens between the two, which would require the strings be split and stitched again.

(For example, storing long spans of strings in a buffer and associating them within a piece table.)