Supporting selective undo of string-wise operations for collaborative editing systems

With the advancement of distributed computing systems, an increasing number of collaborative systems are developed to support real-life collaborative work. As a typical representative of collaborative systems, collaborative editing systems have been one of the major researches within CSCW(Computer Supported Cooperative Work) areas. In collaborative editing systems, selective undo is a key feature that permits users to undo any operation at anywhere and anytime. Recently, with the extensive popularity of big data and cloud computing, collaborative editing systems increasingly tend to massive-scale collaborations, which have to face new technical challenges. How to support selective undo of string-wise operations has become one of significant challenges in future generation collaborative editing systems. Although CRDT (Commutative Replicated Data Type) is a new generation of collaborative editing algorithms, most CRDT algorithms do not support selective undo of string-wise operations. Currently, existing works take time logarithmic or even linear in the number of operation nodes to undo an operation, which would be suboptimal in which a large amount of operations may accumulate. In addition, how to formally prove the correctness of the algorithm is necessary. This paper proposes an efficient CRDT algorithm that supports integrated do and selective undo of string-wise operations. Formal proofs are provided to prove the correctness of the proposed approach and the intentions preserving of do/undo operations. Theoretical analysis and experimental evaluation show that our algorithm outperforms the existing CRDT algorithms to support selective undo.