Earlier quoted context omitted.
Ok, I started reading the paper now, and this seems to be a really cool method. I didn't understand all the details of apply/retreat/advance yet, though. I am wondering, the EG graph is a very general construct, and the events themselves (Insert(i, c) and Delete(i)) are very natural as well. You say in the paper this should also work for other applications than plain text, but I guess then another CRDT has to be cons…
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 sto…
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.