A Survey on Operational Transformation Algorithms: Challenges, Issues and Achievements 1 <s> INTRODUCTION <s> 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. <s> BIB001 </s> A Survey on Operational Transformation Algorithms: Challenges, Issues and Achievements 1 <s> INTRODUCTION <s> 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. <s> BIB002 </s> A Survey on Operational Transformation Algorithms: Challenges, Issues and Achievements 1 <s> INTRODUCTION <s> 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 <s> BIB003 </s> A Survey on Operational Transformation Algorithms: Challenges, Issues and Achievements 1 <s> INTRODUCTION <s> 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. <s> BIB004 </s> A Survey on Operational Transformation Algorithms: Challenges, Issues and Achievements 1 <s> INTRODUCTION <s> 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. <s> BIB005
Consistency maintenance is a fundamental issue in many areas of computing systems, including database systems [Bernstein et al. 1987 ], distributed systems [Birman et al. 1991] , and groupware systems [Baecker 1992; ]. Real-time collaborative graphics editing systems allow a group of users to view and edit the same graphics document at the same time from geographically dispersed sites connected by communication networks. Consistency maintenance in the face of concurrent accesses to shared objects is one of the core issues in the design of these types of systems. Real time group editors (e.g., Grove and Reduce) are a category of distributed systems that allow a group of users to edit the same document collaboratively at the same time over a computer network, e.g., the Internet. They are frequently used as an effective research vehicle and model of a wide range of distributed interactive groupware applications that feature coordinated manipulation of shared data objects. Consistency maintenance is a critical and challenging issue in many interactive groupware applications that can be modeled as group editors. Due to the fact that human users are an integrated part of the system, there are specific requirements BIB001 [2]: High local responsiveness: A group editor should be as responsive as its single-user counterparts. Unconstrained interaction: The users should be able to edit any part of the shared document at any time in a way comparable to using single-user editors. Real-time communication: The users must be notified of each other's operations in a timely manner for mutual awareness and effective coordination. Consistency: Eventually the users must be able to see a converged version of the shared document that is consistent with their actual intentions. Group editors usually replicate the shared document at each site. Each user's operations are executed on the local replica immediately without being blocked or delayed. Operations are then propagated to remote sites and concurrency control protocols are sought to repair inconsistencies. Traditional concurrency control methods, such as locking and serialization, are found unsuitable for interactive groupware applications. Moreover, concurrency control methods in traditional distributed systems in general only consider content consistency, i.e., that all replicas eventually converge, while overlooking intention consistency, i.e., that the converged content is what the users want. Over the past decade operational transformation (OT) BIB004 BIB001 BIB002 has become an established method for consistency maintenance in group editors. Compared to alternative concurrency control methods such as locking and serialization, OT has been found uniquely promising in achieving convergence, causality and intention preservation without sacrificing responsiveness and concurrent work in Sun et al. BIB003 . The main property of OT, allowing users to edit any part of the shared data at any time, in particular matches the vision of Bentley and Dourish  of developing collaborative systems as a customizable collaboration medium. In light of their arguments, group editors with this property do not impose any constraint on how people use the technology. Users are allowed to use group editors for either asynchronous or synchronous editing. With the right" single-user features (e.g., formatting) and multi-user features, group editors appear capable of accommodating a variety of editing purposes, work styles, and processes BIB005 .