In the field of collaborative applications, the ability to undo an earlier operation is a valuable feature. Shao, Li, and Gu have written a technically detailed paper on their algorithm, which is based on operational transformation (OT), for implementing selective undo with time complexity O(|H|), where H is the operation history. This is a significant improvement over earlier results found in the literature.

The early sections of the paper give introductory details and background, as well as a summary of earlier results. The fourth section provides general principles and correctness criteria. Operations are totally ordered through what is called the “effects relation.” The heart of the work is the admissibility-based transformation-undo (ABTU) algorithm. The fifth section contains eight carefully prepared subsections that explain the algorithm, and includes four algorithm variants that address issues associated with local and remote do/undo operations and their integration. The next section undergirds this paper’s rigor with relevant analysis of classic undo puzzles, correctness proofs, and details on the time and space complexity of ABTU (O(|H|) for both).

The paper is very well written and organized. It employs a good balance between readability and rigorous treatment of the subject matter. Researchers and practicing software engineers with an interest in collaborative applications are likely to benefit from this paper, and from the ABTU algorithm.