On the Undoability Problem in Distributed Collaborative Applications

Asma Cherif 1 Abdessamad Imine 1
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Collaborative applications are relevant programs allowing many users to simultaneously cooperate in order to perform a given task on a shared object. These applications are based on replicating shared objects in order to ensure data availability. The Operational Transformation (OT) approach is used for supporting optimistic replication in these applications. It allows the users to concurrently update the shared data and exchange their updates in any order since the convergence of all replicas, i.e. the fact that all users view the same data, is ensured in all cases. 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 particulary, selective undo allows user to undo any operation and is based on rearranging operations in the history. Combining OT and undo approaches is a challenging problem. Even though various undo solutions have been proposed over the recent years, verifying their correctness still be a challenging problem due to the absence of formal guidelines for undo. In this report, we address the undo problem from a theoretical point of view. As the main contribution, we propose a necessary and sufficient condition for undoing replicated objects based on OT with respect to three inverse properties. To overcome the difficulty of necessity proof, we use Constraint Satisfaction Problems (CSP) theory in order to cover all possible transformation cases. As the main result, we prove that it is impossible to achieve a correct undo for objects with non- commutative operations. To relax this impossibility result, we sketch a preliminary solution that consists in adding explicitly a new form of idle operations.
Type de document :
[Research Report] 2011, pp.30
Liste complète des métadonnées

Contributeur : Abdessamad Imine <>
Soumis le : mardi 29 novembre 2011 - 11:44:09
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10


  • HAL Id : hal-00646127, version 1


Asma Cherif, Abdessamad Imine. On the Undoability Problem in Distributed Collaborative Applications. [Research Report] 2011, pp.30. 〈hal-00646127〉



Consultations de la notice