Thanks for this! Great writeup. I'm guessing xi's CRDT uses ideas from Raph Levien's work on combining OT and CRDTs? I've only given Raph's papers a cursory rea

Thanks for this! Great writeup. I'm guessing xi's CRDT uses ideas from Raph Levien's work on combining OT and CRDTs? I've only given Raph's papers a cursory read, but there seem to be a lot of similarities and it looks like he was mentoring you. Does it have an official name yet? Incidentally, I've also been working on an in-depth article on a particular CRDT: Victor Grishchenko's Causal Trees[1]. The original paper only uses the data structure for text, but I believe it can be extended to a variety of other data types. In brief, the basic convergent structure is a tree of immutable "atoms". This tree is stored in memory as a DFS in-order traversal. I treat each atom as an atomic operation ("insert char" or "delete char" in case of strings), and thus, every user action involves an O(N) mutation of the tree array to insert the new atom in the correct spot, followed by an O(N) re-read of the array to update the user-facing data. This requires the effect of each atom to be O(1) when read in DFS order, but with strings, this follows naturally. A CT string in memory looks a whole lot like your "union string" with explicit delete ops instead of tombstones, e.g. ["ins D","ins O","ins U","del","ins G"] which parses as DOG in O(N), except each atom does in fact have a unique ID and holds a reference to its causal atom — the character intended to be on its immediate left. (So no need for crazy coordinate transforms!) As with xi, you also get a full revision history which can be garbage collected if needed. My implementation is a work-in-progress, but I've already extended it to basic Bézier drawing and I'm really curious to see how it scales compared to a more OT-like CRDT such as yours. My guess is that CT won't work very well with large files on account of the full O(N) read/write requirement as well as the ~10x memory cost vs. C strings, but on the other hand, it seems that very few other CRDTs can be painlessly tweaked for use with other data types, and this would be a worthwhile tradeoff for me. CT also benefits from a mostly O(N) merge and O(N) past revision viewing, provided you keep to the reconstruct-data-in-linear-time-on-DFS-traversal invariant. Anyway, CRDTs are super cool! Interesting to see them being used in local contexts, but it totally makes sense, especially since consistency w/garbage collection isn't a concern. [1]: https://ai2-s2-pdfs.s3.amazonaws.com/6534/c371ef78979d7ed84b6dc19f4fd529caab43.pdf https://ai2-s2-pdfs.s3.amazonaws.com/6534/c371ef78979d7ed84b... [2]: https://github.com/archagon/crdt-playground https://github.com/archagon/crdt-playground