Collaborative text editing with Eg-Walker: Better, faster, smaller

#1

Post by czx111331 » Fri, Sep 27, 2024, 12:53 PM UTC

Collaborative text editing with Eg-Walker: Better, faster, smaller
arxiv.org

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#2

Post by matlin » Fri, Sep 27, 2024, 2:31 PM UTC

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

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#3

Post by 1attice » Fri, Sep 27, 2024, 3:14 PM UTC

s/e.g./EG/

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#4

Post by canadiantim » Fri, Sep 27, 2024, 3:29 PM UTC

Looks like amazing work, congrats!! Excited to see implementations in the wild, definitely would be keen to play around with.

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#5

Post by eclectic29 » Fri, Sep 27, 2024, 3:43 PM UTC

If Martin Kleppmann is the author I know this stuff will be worth watching out for.

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#6

Post by benjismith » Fri, Sep 27, 2024, 3:53 PM UTC

matlin wrote: post #2

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…

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!

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#7

Post by britannio » Fri, Sep 27, 2024, 4:01 PM UTC

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.

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#8

Post by deathanatos » Fri, Sep 27, 2024, 4:10 PM UTC

1attice wrote: post #3

s/e.g./EG/

s/e.g./Eg/, which is how the paper stylizes it?

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#9

Post by abdullahkhalids » Fri, Sep 27, 2024, 5:10 PM UTC

Do collaborative whiteboard like software use the same algorithms, or are there more suitable algorithms for picture collaborations?

Re: Collaborative text editing with Eg-Walker: Better, faster, smaller

#10

Post by auggierose » Fri, Sep 27, 2024, 5:17 PM UTC

britannio wrote: post #7

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.