| 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. |
I think it still comes across pretty clearly. I like the idea to think of a version in terms of the frontier, and it certainly feels like the right setting for all of this. Then it is just about how to implement replay efficiently, and such that it also works incrementally.
> "Independently of the application and particular CRDT"?
Yes, but I don't know if this even makes sense. Or maybe your more elaborate version theory already covers this. And I should really understand the plain text case first, before asking for a general method :-) It just seems that your method really is a general framework, based on:
* a set of operations
* an event graph where each event correspond to an operation
* replay
* the apply/retreat/advance method for efficient replay
And it seems to me there is a conceptual gap here between the set of operations and the event graph, and what replay actually does purely in terms of semantics. In order to define replay, you need to say what it means to execute operations that are concurrent, and this is the job of the CRDT, by making operations commutative, and that defines concurrent execution. But to implement apply/retreat/advance, you need a more complex thing than just the CRDT, let's call it an XCRDT (your "internal structure" in the paper). What are the laws of the XCRDT so that apply/retreat/advance work, and it does the same as the CRDT-semantics for replay? Knowing such laws might help when constructing the XCRDT from the CRDT.
Edit: Oh, and the XRCDT also somehow combines the original operations with the operations of the CRDT.