Joseph explains the algorithm on YouTube too: https://www.youtube.com/watch?v=rjbEG7COj7o
It's great work, combining the best of OT and CRDTs.
I find the formulation in the abstract slightly confusing. As far as I understand EG-Walker is a CRDT, an operation-based one.
Seph (author) also has a reference implementation in Typescript: https://github.com/josephg/eg-walker-reference
I've stated before that I think the main thing holding back collaborative text / sequence CRDTs is integration with a production database.
Eg-walker looks interesting because it might lend itself to be integrated into a database because the operations are immutable and only appended. However, to demonstrate the effectiveness of these algorithms library authors (see Yjs, DiamondTypes, etc) build stand-alone data structures (usually specialized search trees) that most databases already provide.
Personally, I've been trying to adapt a Piece Table[1] to be collaborative and stored in Triplit[2] which runs on both client and server and already implements logical clocks but I might see how well I can adapt this algorithm instead!
1. https://en.wikipedia.org/wiki/Piece_table 2. https://github.com/aspen-cloud/triplit
This seems to be a holy grail, to be honest! Super-simple database representations with barely any processing required on the "write path," instant startup, minimal memory requirements on both server and client without a need for CRDT data structures to be in memory, none of the O(n^2) complexity of OT. In fact, if I'm interpreting it correctly, it should be straightforward to get this working in a serverless environment without any notion of session fixation, nor active documents needing to be kept in memory.
I can see this completely reshaping the landscape of what's possible with collaborative documents!
There was a recent thread about the 2001 post that afaik eventually lead to this paper (diamond types is the rust implementation): https://news.ycombinator.com/item?id=41372833
Awesome, I'm been following Seph's work for many years! Always thoughtful and well-executed. Probably the most prolific and insightful engineer in the "collaborative text editing" universe.
I use ShareDB every day, which originated from Seph's excellent work on OT algorithms. Good stuff!
Do collaborative whiteboard like software use the same algorithms, or are there more suitable algorithms for picture collaborations?
Looks like amazing work, congrats!! Excited to see implementations in the wild, definitely would be keen to play around with.
If Martin Kleppmann is the author I know this stuff will be worth watching out for.
s/e.g./EG/
s/e.g./Eg/, which is how the paper stylizes it?