Comment by exfalso

Around 6-7 years ago we started a collaborative editing project for prezi.com. The problem basically boiled down to concurrent editing of a big DOM-like data-structure. We looked at the little literature that was available at the time including OT and CRDTs, but quickly realized that none of the existing approaches were mature enough for our needs. All of them were stuck at "text editing", but we needed to edit these big object DAGs.

So we ended up essentially implementing what you laid out, an in-memory revision control system, although using a bit more formal methods to reason about divergence/convergence of clients. The most basic operation was the "diamond merge": given operation x:A->B, y:A->C, construct x':C->D, y':B->D such that x' . y == y' . x It also had to satisfy certain other algebraic laws, notably diamond composition, which allowed us to compose these merging operations whenever we wanted, guaranteeing that the clients will eventually converge to the same data state. It was quite neat! Shame that it's all proprietary.

Good old days. I remember, the most pesky operation was implementing a good undo-redo algorithm, it's quite tricky, even once you add inverses.