Abstract
Undoing operations is an indispensable feature for many collaborative applications, mainly collaborative editors. It provides the ability to restore a correct state of the shared data after erroneous operations. In particular, selective undo allows users to undo any operation and is based on rearranging operations in the history using the Operational Transformation (OT) approach. OT is an optimistic replication technique that allows many users to concurrently update the shared data and exchange their updates in any order. To ensure consistency, OT enforces the out-of-order execution of concurrent updates using transformation functions that must have been planned in advance. It is a challenging task how to meaningfully combine OT and undo approaches while preserving consistency. Indeed, undoing operations that are received and executed out-of-order at different collaborating sites inevitably leads to divergence cases. Even though various undo solutions have been proposed over the recent years, they are either limited or erroneous.
In this paper, we propose a constraint-based approach to address the undo problem that is formulated as a Constraint Satisfaction Problem (CSP). By using CSP approach, we are able to analyze all covered transformation cases for coordinating collaborative objects with finite size of operations. This allows to devise undoable transformation patterns which considerably simplifies the design of collaborative objects. We also study the relation between commutativity and undoability which enables us to state a very important theoretical result. Indeed, we prove that commutativity is necessary and sufficient to achieve undoability for small sets of operations (of sizes 2 and 4) and only sufficient otherwise. This work represents a step forward toward a practical use of CSP techniques for designing safe OT-based collaborative applications.