A Survey on Operational Transformation Algorithms: Challenges, Issues and Achievements 1 <s> ABTS <s> Commutativity of operations is often exploited in concurrent systems to attain high levels of concurrency. A commutativity-based concurrency control method, called operational transformation (OT), has been actively researched in groupware over the past 15 years. However, much progress can still be made on more practicable approaches to developing and proving OT algorithms. Several constraints have been proposed previously but they are generally difficult to follow and verify in practice. This paper proposes an alternative approach to address this problem. A new consistency model is defined which greatly simplifies the design and proof of OT algorithms <s> BIB001 </s> A Survey on Operational Transformation Algorithms: Challenges, Issues and Achievements 1 <s> ABTS <s> Operational transformation (OT) as a consistency control method has been well accepted in group editors. With OT, the users can edit any part of a shared document at any time and local responsiveness is not sensitive to communication latencies. However, established theoretical frameworks for developing OT algorithms either require transformation functions to work in all possible cases, which complicates the design of transformation functions, or include an under-formalized condition of intention preservation, which results in algorithms that cannot be formally proved and must be fixed over time to address newly discovered counterexamples. To address those limitations, this paper proposes an alternative framework, called admissibility-based transformation (ABT), that is theoretically based on formalized, provable correctness criteria and practically no longer requires transformation functions to work under all conditions. Compared to previous approaches, ABT simplifies the design and proofs of OT algorithms. <s> BIB002
The presented string wise ABTS algorithm is a significant extension to its character wise version ABT BIB001 BIB002 .It supports string based primitive operations. The presented algorithm is the first of its kind with string wise operations and correctness formally proved. Specifically, when transforming two string wise operations, the algorithm is greatly complicated by the handling of position relations between the operation regions because operations may be split cascadingly during transformation. In it operations are stored in their execution order in the history H, the time complexity to integrate a remote operation is roughly O(IHI 2 ) , The space complexity of the presented ABTS algorithm is trivially O(IHI). In ABTS a history buffer H is maintained at each site which logs operations that have been applied to the data replica at that site. For correctness reasons BIB001 BIB002 , H is maintained as a concatenation of of two subsequences, Hi and Hd' which record the executed insert and delete operations in their order of execution, respectively. That is, H = Hi. Hd. In addition, each site maintains RQ, a list of operations received from remote sites in their order of arrival. Each site j runs the following three concurrent threads: Thread £ each time receives a local operation 0, applies it to the data replica, calls algorithm updateHL to update H and compute 0', a transformed version of 0, and propagates the resulting 0' to remote sites. Thread N receives remote operations from the network and appends them to RQ in their order of arrival. Thread R scans RQ for a remote operation 0 at a time that is causally-ready, i.e., all operations that happen before o have been executed at site j. Then algorithm update HR is called to update H and transform 0 into a version 0' that can be correctly executed in current state of site j. After that, 0' is executed on the data replica at site j.