An optimized RGA supporting selective undo for collaborative text editing systems

摘要

Collaboration plays a key role in distributed applications. As a fundamental vehicle for collaboration, collaborative text editing systems have been an important field within CSCW. More recently, with the increasing popularity of cloud computing, collaborative text editing systems move towards large-scale collaborations based on the cloud computing/cloud platform. The computing performance is the key factor of success for large-scale collaborations. CRDT algorithms have been proved to outperform traditional algorithms in publications. However, how to support selective undo has been a challenging issue for existing CRDT algorithms. This paper proposes an efficient CRDT algorithm called ORGAU that provides integrated do and selective undo efficiently. The correctness and operation intentions preserving of the proposed algorithm under an integrated do/undo framework are formally proved. Compared with the typical CRDT algorithms, the proposed algorithm has better computing performance both in theoretical analysis and experimental evaluation while keeping the same space complexity. (C) 2019 Elsevier Inc. All rights reserved.