A Survey on Operational Transformation Algorithms: Challenges, Issues and Achievements 1
---
paper_title: Concurrency control in groupware systems

paper_content:

Groupware systems are computer-based systems that support two or more users engaged in a common task, and that provide an interface to a shared environment. These systems frequently require fine-granularity sharing of data and fast response times. This paper distinguishes real-time groupware systems from other multi-user systems and discusses their concurrency control requirements. An algorithm for concurrency control in real-time groupware systems is then presented. The advantages of this algorithm are its simplicity of use and its responsiveness: users can operate directly on the data without obtaining locks. The algorithm must know some semantics of the operations. However the algorithm's overall structure is independent of the semantic information, allowing the algorithm to be adapted to many situations. An example application of the algorithm to group text editing is given, along with a sketch of its proof of correctness in this particular case. We note that the behavior desired in many of these systems is non-serializable.
---
paper_title: Empirical Study on Collaborative Writing: What Do Co-authors Do, Use, and Like?

paper_content:

How do people work when they are collaborating to write a document? What kind of tools do they use and, in particular, do they resort to groupware for this task? Forty-one people filled out a questionnaire placed on the World Wide Web. In spite of the existence of specialized collaborative writing tools, most respondents reported using individual word processors and email as their main tools for writing joint documents. Respondents noted the importance of functions such as change tracking, version control, and synchronous work for collaborative writing tools. This study also confirmed the great variability that exists between collaborative writing projects, whether it be group membership, management, writing strategy, or scheduling issues.
---
paper_title: Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems

paper_content:

Real-time cooperative editing systems allow multiple users to view and edit the same text/graphic/image/multimedia document at the same time for multiple sites connected by communication networks. Consistency maintenance is one of the most significant challenges in designing and implementing real-time cooperative editing systems. In this article, a consistency model, with properties of convergence, causality preservation, and intention preservation, is proposed as a framework for consistency maintenance in real-time cooperative editing systems. Moreover, an integrated set of schemes and algorithms, which support the proposed consistency model, are devised and discussed in detail. In particular, we have contributed (1) a novel generic operation transformation control algorithm for achieving intention preservation in combination with schemes for achieving convergence and causality preservation and (2) a pair of reversible inclusion and exclusion transformation algorithms for stringwise operations for text editing. An Internet-based prototype system has been built to test the feasibility of the proposed schemes and algorithms
---
paper_title: Operational transformation in real-time group editors: issues, algorithms, and achievements

paper_content:

Rd-time group editors dow a group of users to view and edit, the same document at the same time horn geograpbicdy di.~ersed sites connected by communication networks. Consistency maintenance is one of the most si@cant &alwiges in the design and implementation of thwe types of systems. R=earch on rd-time group editors in the past decade has invented au inuolative tetique for consistency maintenance, ded operational transformation This paper presents an integrative review of the evolution of operational tra=formation techniques, with the go~ of identifying the major is-m~s, dgotiths, achievements, and remaining Mlenges. In addition, this paper contribut= a new optimized generic operational transformation control algorithm. Ke~vords Consistency maint enauce, operational transformation, convergence, CauS*ty pras~ation, intention pre~tion, group e&tors, groupware, distributed computing.
---
paper_title: Generalizing operational transformation to the standard general markup language

paper_content:

In this paper we extend operational transformation to support synchronous collaborative editing of documents written in dialects of SGML (Standard General Markup Language) such as XML and HTML, based on SGML's abstract data model, the grove. We argue that concurrent updates to a shared grove must be transformed before being applied to each replica to ensure consistency. We express grove operations as property changes on positionally-addressed nodes, define a set of transformation functions, and show how to apply an existing generic operational transformation algorithm to achieve this. This result makes synchronous group editing applicable to the modern Web.
---
paper_title: Concurrency control in groupware systems

paper_content:

Groupware systems are computer-based systems that support two or more users engaged in a common task, and that provide an interface to a shared environment. These systems frequently require fine-granularity sharing of data and fast response times. This paper distinguishes real-time groupware systems from other multi-user systems and discusses their concurrency control requirements. An algorithm for concurrency control in real-time groupware systems is then presented. The advantages of this algorithm are its simplicity of use and its responsiveness: users can operate directly on the data without obtaining locks. The algorithm must know some semantics of the operations. However the algorithm's overall structure is independent of the semantic information, allowing the algorithm to be adapted to many situations. An example application of the algorithm to group text editing is given, along with a sketch of its proof of correctness in this particular case. We note that the behavior desired in many of these systems is non-serializable.
---
paper_title: Operational transformation in real-time group editors: issues, algorithms, and achievements

paper_content:

Rd-time group editors dow a group of users to view and edit, the same document at the same time horn geograpbicdy di.~ersed sites connected by communication networks. Consistency maintenance is one of the most si@cant &alwiges in the design and implementation of thwe types of systems. R=earch on rd-time group editors in the past decade has invented au inuolative tetique for consistency maintenance, ded operational transformation This paper presents an integrative review of the evolution of operational tra=formation techniques, with the go~ of identifying the major is-m~s, dgotiths, achievements, and remaining Mlenges. In addition, this paper contribut= a new optimized generic operational transformation control algorithm. Ke~vords Consistency maint enauce, operational transformation, convergence, CauS*ty pras~ation, intention pre~tion, group e&tors, groupware, distributed computing.
---
paper_title: Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems

paper_content:

Real-time cooperative editing systems allow multiple users to view and edit the same text/graphic/image/multimedia document at the same time for multiple sites connected by communication networks. Consistency maintenance is one of the most significant challenges in designing and implementing real-time cooperative editing systems. In this article, a consistency model, with properties of convergence, causality preservation, and intention preservation, is proposed as a framework for consistency maintenance in real-time cooperative editing systems. Moreover, an integrated set of schemes and algorithms, which support the proposed consistency model, are devised and discussed in detail. In particular, we have contributed (1) a novel generic operation transformation control algorithm for achieving intention preservation in combination with schemes for achieving convergence and causality preservation and (2) a pair of reversible inclusion and exclusion transformation algorithms for stringwise operations for text editing. An Internet-based prototype system has been built to test the feasibility of the proposed schemes and algorithms
---
paper_title: Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems

paper_content:

Real-time cooperative editing systems allow multiple users to view and edit the same text/graphic/image/multimedia document at the same time for multiple sites connected by communication networks. Consistency maintenance is one of the most significant challenges in designing and implementing real-time cooperative editing systems. In this article, a consistency model, with properties of convergence, causality preservation, and intention preservation, is proposed as a framework for consistency maintenance in real-time cooperative editing systems. Moreover, an integrated set of schemes and algorithms, which support the proposed consistency model, are devised and discussed in detail. In particular, we have contributed (1) a novel generic operation transformation control algorithm for achieving intention preservation in combination with schemes for achieving convergence and causality preservation and (2) a pair of reversible inclusion and exclusion transformation algorithms for stringwise operations for text editing. An Internet-based prototype system has been built to test the feasibility of the proposed schemes and algorithms
---
paper_title: Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems

paper_content:

Real-time cooperative editing systems allow multiple users to view and edit the same text/graphic/image/multimedia document at the same time for multiple sites connected by communication networks. Consistency maintenance is one of the most significant challenges in designing and implementing real-time cooperative editing systems. In this article, a consistency model, with properties of convergence, causality preservation, and intention preservation, is proposed as a framework for consistency maintenance in real-time cooperative editing systems. Moreover, an integrated set of schemes and algorithms, which support the proposed consistency model, are devised and discussed in detail. In particular, we have contributed (1) a novel generic operation transformation control algorithm for achieving intention preservation in combination with schemes for achieving convergence and causality preservation and (2) a pair of reversible inclusion and exclusion transformation algorithms for stringwise operations for text editing. An Internet-based prototype system has been built to test the feasibility of the proposed schemes and algorithms
---
paper_title: An Admissibility-Based Operational Transformation Framework for Collaborative Editing Systems

paper_content:

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.
---
paper_title: Operational transformation in real-time group editors: issues, algorithms, and achievements

paper_content:

Rd-time group editors dow a group of users to view and edit, the same document at the same time horn geograpbicdy di.~ersed sites connected by communication networks. Consistency maintenance is one of the most si@cant &alwiges in the design and implementation of thwe types of systems. R=earch on rd-time group editors in the past decade has invented au inuolative tetique for consistency maintenance, ded operational transformation This paper presents an integrative review of the evolution of operational tra=formation techniques, with the go~ of identifying the major is-m~s, dgotiths, achievements, and remaining Mlenges. In addition, this paper contribut= a new optimized generic operational transformation control algorithm. Ke~vords Consistency maint enauce, operational transformation, convergence, CauS*ty pras~ation, intention pre~tion, group e&tors, groupware, distributed computing.
---
paper_title: A time interval based consistency control algorithm for interactive groupware applications

paper_content:

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.
---
paper_title: Operational transformation in real-time group editors: issues, algorithms, and achievements

paper_content:

Rd-time group editors dow a group of users to view and edit, the same document at the same time horn geograpbicdy di.~ersed sites connected by communication networks. Consistency maintenance is one of the most si@cant &alwiges in the design and implementation of thwe types of systems. R=earch on rd-time group editors in the past decade has invented au inuolative tetique for consistency maintenance, ded operational transformation This paper presents an integrative review of the evolution of operational tra=formation techniques, with the go~ of identifying the major is-m~s, dgotiths, achievements, and remaining Mlenges. In addition, this paper contribut= a new optimized generic operational transformation control algorithm. Ke~vords Consistency maint enauce, operational transformation, convergence, CauS*ty pras~ation, intention pre~tion, group e&tors, groupware, distributed computing.
---
paper_title: Operational transformation in real-time group editors: issues, algorithms, and achievements

paper_content:

Rd-time group editors dow a group of users to view and edit, the same document at the same time horn geograpbicdy di.~ersed sites connected by communication networks. Consistency maintenance is one of the most si@cant &alwiges in the design and implementation of thwe types of systems. R=earch on rd-time group editors in the past decade has invented au inuolative tetique for consistency maintenance, ded operational transformation This paper presents an integrative review of the evolution of operational tra=formation techniques, with the go~ of identifying the major is-m~s, dgotiths, achievements, and remaining Mlenges. In addition, this paper contribut= a new optimized generic operational transformation control algorithm. Ke~vords Consistency maint enauce, operational transformation, convergence, CauS*ty pras~ation, intention pre~tion, group e&tors, groupware, distributed computing.
---
paper_title: Generalizing operational transformation to the standard general markup language

paper_content:

In this paper we extend operational transformation to support synchronous collaborative editing of documents written in dialects of SGML (Standard General Markup Language) such as XML and HTML, based on SGML's abstract data model, the grove. We argue that concurrent updates to a shared grove must be transformed before being applied to each replica to ensure consistency. We express grove operations as property changes on positionally-addressed nodes, define a set of transformation functions, and show how to apply an existing generic operational transformation algorithm to achieve this. This result makes synchronous group editing applicable to the modern Web.
---
paper_title: An Admissibility-Based Operational Transformation Framework for Collaborative Editing Systems

paper_content:

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.
---
paper_title: A time interval based consistency control algorithm for interactive groupware applications

paper_content:

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.
---
paper_title: An Admissibility-Based Operational Transformation Framework for Collaborative Editing Systems

paper_content:

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.
---
paper_title: An Admissibility-Based Operational Transformation Framework for Collaborative Editing Systems

paper_content:

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.
---
paper_title: Commutativity-based concurrency control in groupware

paper_content:

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
---
paper_title: An Admissibility-Based Operational Transformation Framework for Collaborative Editing Systems

paper_content:

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.
---

Title: A Survey on Operational Transformation Algorithms: Challenges, Issues and Achievements

Section 1: INTRODUCTION
Description 1: Write an introduction to the fundamental issues and challenges in consistency maintenance in collaborative systems and provide background information on the context and significance of operational transformation.

Section 2: OPERATIONAL TRANSFORMATION
Description 2: Discuss the basic concept and principles of operational transformation as an optimistic consistency control method in collaborative applications.

Section 3: Inclusion and Exclusion Transformation
Description 3: Explain the concepts of inclusion transformation (IT) and exclusion transformation (ET) functions, and their roles in ensuring consistency in collaborative editing.

Section 4: Transformation Properties
Description 4: Outline the key properties (TP1 and TP2) required for the transformation functions to ensure consistent final document states.

Section 5: The dOPT Puzzle
Description 5: Describe the dOPT puzzle, its implications, and the scenarios in which the original dOPT algorithm fails.

Section 6: The TP2 Puzzle
Description 6: Discuss the TP2 puzzle, illustrate with examples, and explain why the simple fixes are insufficient.

Section 7: ALGORITHMS
Description 7: Provide an overview of various OT algorithms proposed over the years, highlighting their approaches and unique features.

Section 8: dOPT
Description 8: Discuss the dOPT algorithm, its mechanisms, and how it ensures the convergence property.

Section 9: adOPTed
Description 9: Explain the adOPTed algorithm, derived from dOPT, and describe its adaptations to a centralized server environment.

Section 10: IMOR
Description 10: Detail the IMOR algorithm and how it uses additional parameters to solve concurrent insertion issues.

Section 11: GOT
Description 11: Describe the General Operational Transformation (GOT) algorithm and how it achieves intention-preservation and convergence without relying on TP1 and TP2.

Section 12: GOTO
Description 12: Explain the GOTO algorithm, an optimized version of GOT, and how it reduces the number of transformations required.

Section 13: SOCT2
Description 13: Outline the SOCT2 algorithm, its transformation functions, and how it ensures convergence.

Section 14: SOCT3
Description 14: Detail the SOCT3 algorithm's use of a global order sequencing mechanism to avoid undo/redo operations.

Section 15: SOCT4
Description 15: Discuss the improvements in SOCT4 with regards to forward transposition and state vector elimination.

Section 16: TIBOT
Description 16: Describe the Time Interval Based Operational Transformation (TIBOT) algorithm and its efficiency in terms of complexity.

Section 17: LBT
Description 17: Explain the LBT algorithm and its method of maintaining special transformation paths to ensure consistency.

Section 18: SLOT
Description 18: Introduce the SLOT algorithm and its simplicity and efficiency compared to other OT algorithms.

Section 19: SDT
Description 19: Discuss the State Difference Based Transformation (SDT) algorithm and its ability to ensure convergence in peer-to-peer editors.

Section 20: ABT
Description 20: Detail the Admissibility-Based Transformation (ABT) algorithm, its correctness criteria, and its simpler handling of transformation functions.

Section 21: ABTS
Description 21: Explain the ABTS algorithm, an extension of ABT to support string-based operations with formal correctness proofs.

Section 22: 3.16
Description 22: Summarize the comparison of various OT algorithms and their respective strengths and weaknesses.

Section 23: FUTURE WORK
Description 23: Discuss potential future research areas and ongoing challenges in reducing time and space complexity and understanding user intentions.