An algorithm for selective undo of any operation in collaborative applications
Bin Shao, Du Li, Ning Gu · 2010
Selective undo allows users to undo any operation in the history and is considered a key feature in collaborative applications. Operational transformation (OT) is a powerful tool for implementing selective undo because it can be used to rearrange operations in a history in arbitrary orders. Despite the significant progress over the past two decades, however, there is still a space for improvements. Most existing works take time quadratic or even exponential in the size of the operation history H to undo an operation. Although this might be acceptable for real-time collaboration, it would be suboptimal in mobile and asynchronous collaborative applications in which a long history may accumulate. In addition, it is important to prove an algorithm with regard to the correctness criteria it assumes. This paper proposes a novel OT-based algorithm that provides integrated do and selective undo. The algorithm achieves time complexity of O(|H|) in both do and undo by keeping the history in a special operation effects relation order. Its correctness is formally proved with regard to formalized, provable conditions that are extended from a recent theoretical framework.