Constant-Time Operation Transformation and Integration for Collaborative Editing

Operational transformation (OT) is the concurrency control mechanism for collaborative editors, due to its high responsiveness to local editing operations. However, collaborative editing is still not widely practiced. One of the reasons is that operation transformation and integration are computation intensive and time consuming. The state-of-the-art time complexity is currently O(|H|), where |H| is the length of operation histories, which can be large and grow indefinitely. Moreover, most of the published work is limited with character operations, leading to long operation histories and impractically large number of small messages over the network. This paper presents an approach that supports string operations and constant-time operation transformation and integration. The approach is based on admissibility preservation, a correctness criterion with which the correctness of the approach can be formally proven.