Comment by mweidner
19 hours ago
This was my impression as well. If you ignore the paper and just look at the source code - and carefully study Seph Gentle's Yjs-like RGA implementation [1] - I believe you find that it is equivalent to an RGA-style tree, but with a different rule for sorting insertions that have the same left origin. That rule is hard to describe, but with some effort one can prove that concurrent insertions commute; I'm hoping to include this in a paper someday.
Yes, I think it would be a good paper.
I made a tiny self contained implementation of this algorithm here if anyone is curious:
https://github.com/josephg/crdt-from-scratch/blob/master/crd...
FugueMax (or Yjs) fit in a few hundred lines of code. This approach also performs well (better than a tree based structure). And there's a laundry list of ways this code can be optimised if you want better performance.
If anyone is interested in how this code works, I programmed it live on camera in a couple hours:
https://www.youtube.com/watch?v=_lQ2Q4Kzi1I
This implementation approach comes from Yjs. The YATA (yjs) academic paper has several problems. But Yjs's actual implementation is very clever and I'm quite confident its correct.