A Survey on Operational Transformation Algorithms: Challenges, Issues and Achievements 1 <s> TIBOT <s> Traditional concurrency control methods such as locking and serialization are not suitable for distributed interactive applications that demand fast local response. Operational transformation (OT) is the standard solution to concurrency control and consistency maintenance in group editors, an important class of interactive groupware applications. It generally trades consistency for local responsiveness, because human users can often tolerate temporary inconsistencies but do not like their interactions be lost or nondeterministically blocked. This paper presents a time interval based operational transformation algorithm (TIBOT) that overcomes the various limitations of previous related work. Our approach guarantees content convergence and is significantly more simple and efficient than existing approaches. This is achieved in a pure replicated architecture by using a linear clock and by posing some constraints on communication that are reasonable for the application domain. <s> BIB001 </s> A Survey on Operational Transformation Algorithms: Challenges, Issues and Achievements 1 <s> TIBOT <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
Time interval based operational transformation algorithm (TIBOT) BIB001 that overcomes the various limitations of previous related work. Our approach guarantees content convergence and is significantly more simple and efficient than existing approaches. This is achieved in a pure replicated architecture by using a linear clock and by posting some constraints on communication that are reasonable for the application domain. TIBOT achieves the time complexity of O with the storage complexity significantly reduced, as compared to adOPTed, and the algorithm itself significantly simplified, as compared to GOTO. It use a linear time interval based logical clock for the same purpose of causality preservation as the more complex vector clock approach in existing operational transformation algorithms. This increases system scalability in terms of accommodating late comers in a dynamic collaboration environment. Second, we solve the dOPT puzzle with a one-dimensional history buffer and Third, we solve the TP2 puzzle in a fully replicated architecture and without using ET (as compared to GOT or extra mechanisms. , WOOT uses a model checker to prove convergence by verifying all cases that involve up to four sites and five characters, which deservers further work with regard to convergence. TTF uses a theorem prover to verify TP1 and TP2, which are sufficient conditions for convergence by  . In both works, they explain the concept of operation intention somewhat between the interpretation of ) and our definitions of operation effects relation BIB001 Li and Li 2007; Li and Li 2005) . Nevertheless, they do not provide proofs with regard to their interpretation of intention preservation. It seems that our formalization of effects relation (Li and Li 2007) or admissibility in it BIB002 is compatible with and complementary to their approach of automated proofs. There is a potential that their approach and ours can leverage each other in future research.