I agree with Raph that OT and CRDT are closer in concept than many people currently think. Each have some interesting advantages. If we find a good way to combine them, perhaps it would be possible to engineer a system that has a different combination of advantages than today's OT or CRDTs provide.
Aw I'm HN-famous! I'm sorry I didn't see this post sooner. I'd love to catch up for virtual coffee if you're interested - check your email.
I'm not sure if your tree structure is needed to efficiently transform N operations together. Another approach is to simply compose the operations together and transform by the composed operation set, using the property that with a proper tombstone-using text ot type it holds that IT(IT(x, A), B) == IT(x, A.B). (where IT=transform, `.`=compose). Mind you, this approach is still a bit slower than your solution. (I think you can make it O(N*(log N)^3) or something like that. But still faster than O(N^2).)
I don't think this is technically a CRDT - I think its still technically just OT, but OT that holds some additional properties. My favourite differentiating characteristic is that CRDTs bundle information from the document's history with the document snapshot itself. This lets you apply an operation with an older operational context. Obviously applying an old operation would be trivial with an OT system too if you had the history and could transform the operation - its just inefficient. So in a sense, {tp2-ot+document history} is a CRDT. Just, an inefficient one. As far as I can tell what you're proposing doesn't bundle the history - and you still need that history to transform.
It has some other really nice properties though, to the point that I had a pass implementing a p2p system using something like this a few years ago, using IT and ET functions. (My researcher friend Torben Weis independently discovered that method back in 2011 but didn't publish it). But the downside is that its slow. Your tree-based approach for operations themselves might be enough to make it viable. Very cool stuff!
