Collaborative Undo done right

Many people using gobby complain that it does not support Undo, and some do not even use it therefore. Of course, they are right. It is not only convenient but may also save you lots of data in case you accidentally delete it. However, it is not easy to implement it in a collaborative editor because between your own do and undo operation pairs others might have altered the document. It is thus not reverted to a previous state as with a single user editor. We got suggestions to add some sort of "primitive" Undo like just undoing the last operation, no matter from whom it was. I didn't like that, though, because I prefer to either do things correctly or not at all.

Fortunately, other people also thought about how to achieve collaborative Undo. I read some papers [1] describing an algorithm (adOPTed) that not only achieves convergence, meaning that two users don't end up with a different document after having applied some operations concurrently (which the obby algorithm (called Jupiter) obviously also achieves), but also allows Undo/Redo (which Jupiter does not when more than two users are involved). This is however not the one-and-only solution. There are other approaches to collaborative Undo (or resolving collisions in general), like the AbiCollab one. adOPTed has some nice properties though:

• It has enough information to not only undo your own but also any other's operation. Actually, when a user wants to Undo something, it just says "I am doing an Undo now" and the others calculate the required operation. This especially allows to easily restore user colors when a deletion is being undone (without allowing arbitrary insertion of text colored with another user's color). It could also be used to undo vandalism issued by another user.
• You can always undo and redo your operations, independent of what others have done in between. However, it might happen that an undo has no effect (for example, if you type something, another one deletes it and you press undo then). I wonder by the way what a user expects in that case: Imagine you are typing two letters, and another user deletes the second one. When you press Undo now, would you expect nothing to happen (because another one already "manually" undid your latest operation) or would you expect that the first letter also disappears (because of exactly the same reason)?
• It doesn't need a server to make some final decisions or to keep things in order. You just have to make the other participants receive your requests somehow. Also, there are no conflict situations or something requiring additional round-trips.

However, as always, everything has its price:

• My implementation requires already a lot of CPU power in my simple test cases to calculate the required transformations, especially when there are lots of operations between a do/undo pair.
• As every user calculates the undo operation by itself, every user needs to keep track of every request made by any user. This also requires to send the whole request log to a joining user. Of course, this can be limited to the latest N operations, but it is still a considerable amount of data (especially when many users are working together) and restricts the number of operations people can undo.

My proof of concept featuring Undo and Redo is here. However, you probably won't understand the interesting part of that code without having read the papers referenced above (which you should do as well if you are interested in more details, by the way). There a still a couple of issues before that can be used in a real-world environment, though. I think the performance problems mentioned above can be fixed by caching transformed requests, so that it does not have to compute the same requests all over again. Another problem that needs to be solved is a dynamic amount of users. My test code only works for a fixed number of users. The difficulty is to find out when it is safe to forget about operations from a user that has left the editing session, to save memory and bandwidth.

I hope to get that done really soon now so that it can be used in Infinote and perhaps even Gobby (I have not yet decided whether I want to implement that in Gobby because it is still a considerable amount of work).

I am off to Ireland at the 23th of July and am visiting some friends near Osnabrück right after that, but when I am back home (presumably at 12th of August) I really hope to get something usable (read: a gedit plugin) before my third semester at university begins in October. Unfortunately, I cannot make it to GUADEC this year because I have to be at university that week, but I really look forward to finally get there next year.

[1] Achieving Convergence with Operational Transformation in Distributed Groupware Systems (by Abdessamad Imine et al.)
An Integrating, Transformation-Oriented Approach to Concurrency Control and Undo in Group Editors (by Matthias Ressel, Rul Gunzenhäuser and Doris Nitsche-Ruhland)
Reducing the problems of group undo (by Matthias Ressel and Rul Gunzenhäuser)