Maybe. Here's another way to think of the algorithm:

All the complexity comes about because we're trying to convert the insert / delete position from edits (expressed at their original version) to some later current version.

There's lots of ways of solving this problem. For example, we could build a data structure which contains metadata for every inserted item in a text document. For every inserted character, we store when the item was inserted and when (if ever) the item was deleted.

Then you could implement the algorithm in a simpler way. Lets say I'm trying to insert at position 1000, at some version V.

- We scan the list of characters from the start of the document, looking for the 1000th item which was actually in the document at version V.

- For each character in the list, we can tell if that item was inserted at version V by comparing V to the stored inserted / deleted at times.

This algorithm would be correct, and it avoids retreat / advance. The only problem with this approach is that it would be slow - because you're constantly scanning the document to convert insert positions. Inserting N items into a document take O(N^2) time.

The retreat / advance approach described in the paper is an optimization on top of this algorithm which performs the same work in O(N log N) time.

I wish we made this more clear in the paper. In an earlier draft we spent about 5 pages simply talking about version theory. The algorithm was then described using that theory with a stronger theoretical grounding. But I think that description may have been even more confusing.

> You say in the paper this should also work for other applications than plain text, but I guess then another CRDT has to be constructed to implement apply/retreat/advance. Would it be possible to formulate all of this independently of the application and particular CRDT, together with corresponding correctness theorems?

"Independently of the application and particular CRDT"? I don't know, we might have to think through how that would work for every CRDT. Do you have any personal favorites that would be worth thinking through?

For registers (eg in a variable, dictionary, hash map or array where indexes never change), you could implement a similar algorithm incredibly easily by just doing the version comparison operation on the graph. (The current value is the value set in the graph's frontier.) The retreat / advance optimisation isn't needed at all for registers.

For a list - for example, a list of layers in photoshop - we might need something more complex, since layers can be inserted / deleted like text and as a result the index of subsequent items changes. But layers can also be reordered - and that requires some thought. For rich text, there's an approach that I think would work but I haven't implemented it yet.

First paragraph: yes, exactly.

> OTs take an event..

This is how the early Jupiter OT works, yes. And most OT systems work like this. But there are also some papers on more recent OT systems which can work with more than 2 peers. Unfortunately, many of these systems have turned out to have convergence bugs and/or they are O(n^2). For our paper one of our example datasets takes tens of milliseconds to replay with CRDTs and egwalker but an hour of time with OT!

> the data structure is capable of representing two different versions…

With egwalker it’s important to distinguish between two different data structures. There’s a grow only set of original editing events. This is persisted to disk and replicated over the network. Then while actually replaying events or merging, we generate a second, temporary, in memory data structure which resembles a normal CRDT. (Except with an extra state field on each item like you said). This crdt state object isn’t persisted. It’s usually discarded as soon as the merge (transform) operation is complete. One big advantage of this approach is that this data structure does not need to represent all items ever inserted. Just the concurrent items, back to the most recent common branch. So it’s usually tiny. And that allows history to be pruned - which CRDTs typically don’t allow.

But yes, everything else is right!

You can just store a snapshot on disk (ie, the raw text) and load that directly. You only ever need to look at historical edits when merging concurrent changes into the local document state. (And thats pretty rare in practice).

Even when that happens, the algorithm only needs to look at operations as far back as the most recent "fork point" between the two branches in order to merge. (And we can compute that fork point in O(n) time - where n is the number of events that have happened since then). Its usually very very fast.

In an application like google docs or a wiki, the browser will usually never need to look at any historical changes at all in order to edit a document.