[mvaerle]

I was also wondering about the difference between patch theory and this. I wonder if one of the reasons for operational transformation is that it is more feasible in semi-realtime environments, for example because transforming the operations is (computationally) easier than doing a merge on the data itself.

[jerf]

I can't speak for Google's system, but with the system I had envisioned "merge" time would have been proportional to the amount of patches diverged, which would always have been tiny. The common case is that you go to apply another user's patch and it applies cleanly. You have to be ready for conflicts but they will generally be rare, even if your latency is fairly large. Remember you actually have to be stomping directly on top of another user's work for the patch to have a problem; possible, certainly, would occur in practice, but not normal.

(Careful design of the patch commutation algorithms could further reduce the problems you face, this and "pasting in a huge swathe of text" being the two basic "huge" operations available to a user in realtime. Imagine one user highlights a huge swathe of text and deletes it while another is trying to add a character or two. Normally this could be a conflict, but depending on how you represent the delete, you might be able to make it so the delete simply eats all further edits to the deleted text. In fact in my system this was actually a major problem due to some other issues (in my system you could limit your visible scope down to, say, a specific "chapter" and then I have a UI problem if that entire chapter gets deleted), but this wouldn't affect Google Wave anywhere near as badly, unless it also has narrowing available.)