OT (Operational Transformation) was invented for supporting real-time co-editors in the late 1980s and has evolved to become core techniques widely used in today's working co-editors and adopted in industrial products. CRDT (Commutative Replicated Data Type) for co-editors was first proposed around 2006, under the name of WOOT (WithOut Operational Transformation). Follow-up CRDT variations are commonly labeled as "post-OT" techniques capable of making concurrent operations natively commutative in co-editors. On top of that, CRDT solutions have made broad claims of superiority over OT solutions, and often portrayed OT as an incorrect and inefficient technique. Over one decade later, however, CRDT is rarely found in working co-editors; OT remains the choice for building the vast majority of today's co-editors. Contradictions between the reality and CRDT's purported advantages have been the source of much confusion and debate in co-editing researcher and developer communities. To seek truth from facts, we set out to conduct a comprehensive and critical review on representative OT and CRDT solutions and working co-editors based on them. From this work, we have made important discoveries about OT and CRDT, and revealed facts and evidences that refute CRDT claims over OT on all accounts. These discoveries help explain the underlying reasons for the choice between OT and CRDT in the real world. We report these results in a series of three articles. In this article (the second in the series), we reveal the differences between OT and CRDT in their basic approaches to realizing the same general transformation and how such differences had resulted in different technical challenges and consequential correctness and complexity issues. Moreover, we reveal hidden complexity and algorithmic flaws with representative CRDT solutions, and discuss common myths and facts related to correctness and complexity of OT and CRDT. We hope the discoveries from this work help clear up common myths and confusions surrounding OT and CRDT, and accelerate progress in co-editing technology for real world applications.

OT (Operational Transformation) was invented for supporting real-time co-editors in the late 1980s and has evolved to become a collection of core techniques widely used in today's working co-editors and adopted in major industrial products. CRDT (Commutative Replicated Data Type) for co-editors was first proposed around 2006, under the name of WOOT (WithOut Operational Transformation). Follow-up CRDT variations are commonly labeled as "post-OT" techniques capable of making concurrent operations natively commutativity in co-editors. On top of that, CRDT solutions have made broad claims of superiority over OT solutions, and routinely portrayed OT as an incorrect, complex and inefficient technique. Over one decade later, however, CRDT is rarely found in working co-editors, and OT remains the choice for building the vast majority of today's co-editors. Contradictions between the reality and CRDT's purported advantages have been the source of much confusion and debate in co-editing research and developer communities. Have the vast majority of co-editors been unfortunate in choosing the faulty and inferior OT, or those CRDT claims are false? What are the real differences between OT and CRDT for co-editors? What are the key factors and underlying reasons behind the choices between OT and CRDT in the real world? A thorough examination of these questions is relevant not only to researchers who are exploring the frontiers of co-editing technologies and systems, but also to practitioners who are seeking viable techniques to build real world applications. To seek truth from facts, we set out to conduct a comprehensive and critical review on representative OT and CRDT solutions and working co-editors based on them. From this work, we have made important discoveries about OT and CRDT, and revealed facts and evidences that refute CRDT claims over OT on all accounts. We report our discoveries in a series of articles and the current article is the first one in this series. In this paper, we present a general transformation framework for consistency maintenance in co-editors, which was distilled from dissecting and examining representative OT and CRDT solutions (and other alternative solutions) during this work, and report our discoveries under the guidance of this framework. In particular, we reveal that CRDT is like OT in following a general transformation approach, but achieves the same transformation indirectly, in contrast to OT direct transformation approach; and CRDT is not natively commutative for concurrent co-editing operations, but has to achieve the same OT commutativity indirectly as well, with consequential correctness and complexity issues. Uncovering the hidden transformation nature and demystifying the commutativity property of CRDT provides much-needed clarity about what CRDT really is and is not to co-editing, and serves as the foundation to explore the real differences between OT and CRDT in correctness, complexity, implementation, and real world applications, which are reported in follow-up articles. We hope discoveries from this work help clear up common misconceptions and confusions surrounding OT and CRDT, and accelerate progress in co-editing technology for real world applications.?

File sharing and collaboration is a common functionality in cloud storage systems, which allow multiple users to concurrently manipulate files in shared folders or workspaces. However, in the face of concurrency, existing cloud storage systems may deliver unexpected results to end-users. The goal of our research is to reveal the results delivered (but never explicitly specified) by the existing cloud storage systems in concurrent environments and make these results publically accessible, which could benefit both cloud storage end-users and service providers. To reach this research goal, we developed an automated benchmark tool, which allows people to freely test the four major cloud storage systems, including Dropbox, Box, Mircosoft OneDrive, and Google Drive, with well-designed concurrency test cases, and access the testing results, at anytime from anywhere. In this paper, we detail the design and implementation of the tool and present technical solutions to the issues in implementing the tool and report part of benchmarking results.

Most past research efforts in co-editing focused on homogeneous co-editing, which allows multiple users to use the same editor to edit shared documents in the same session, and nearly all real-world co-editors, such as Google Docs, are homogeneous co-editors. In this work, we explore issues and solutions in building heterogeneous co-editing systems, which allow multiple users to use different editors to edit shared documents in the same session. To drive our exploration, we built a prototype heterogeneous co-editing system, named CoVim+CoEmacs, which allows multiple users to use full functionalities and UI features of two comprehensive and rivalry text editors, Vim and Emacs, in the same co-editing session. In this paper, we focus on technical issues in designing and implementing heterogeneous co-editors in general and CoVim+CoEmacs in particular. We have motivated this work by potential usage benefits of heterogeneous co-editing systems and used working scenarios under the CoVim+CoEmacs prototype to illustrate some novel usages and inner workings of such systems, but left systematic user studies on heterogeneous co-editing to future work. We hope the insights and experiences drawn from this work can not only contribute to advancing state-of-the-art collaborative system design and implementation, but also provide inspiration to future heterogeneous collaborative application system designers.

OT (Operational Transformation) is a consistency maintenance technique for real-time collaborative editors and a continuous topic of research in CSCW for over two-decades. One main challenge in OT research is to detect and resolve puzzles -- characteristic collaboration scenarios or transformation cases in which an OT system may fail to produce consistent results. A long-standing open issue is whether we can find and solve all possible puzzles in OT systems supporting string-wise operations under well-defined consistency requirements. In this paper, we present our research that solves this open problem and a set of concrete string-wise transformation functions capable of solving all known puzzles and preserving well-defined consistency requirements. Our results contribute to the advancement of state-of-the-art of OT fundamental knowledge and technological innovation.

Collaboration among programmers with different expertise and skill sets is becoming highly essential as many software systems are getting larger and more complex. The CoVim project aims to incorporate advanced real-time collaboration capabilities into Vim, one of the most popular source code editors, using the Transparent Adaptation (TA) approach. This work has extended TA from GUI-based applications (e.g. MS Word, MS PowerPoint, and Autodesk Maya) to complex keyboard-oriented applications like Vim. This work also contributed a novel state-centric operation derivation approach for TA, which is generic and more efficient in supporting a range of real-time editing features, compared to prior TA's interception-centric operation derivation approach which is user-interaction dependent and application specific.

Cloud storage is widely used to share and collaborate on files over the Internet; consistency maintenance of replicated files in the face of concurrency is a major challenge. In this paper, we present a novel CSOT (Cloud Storage Operational Transformation) solution to support real-time file synchronization in front-end cloud storage and achieve consistent and desirable concurrent operation combined-effects that cannot be fully achieved by any existing cloud storage systems. We have formally verified algorithmic correctness of CSOT, built a proof-of-concept implementation, and experimentally compared results produced by CSOT and three industrial cloud storage systems, Microsoft OneDrive, Google Drive, and Dropbox, under the same collection of concurrent operation testing cases. CSOT is the first to extend OT consistency maintenance capability to shared workspaces in cloud storage and contributes to advancement of cloud-based collaboration technologies.

This paper presents an Operational Transformation (OT) technique, named CSOT (Cloud Storage OT), that supports real-time file synchronization in cloud storage and achieve well-defined consistent combined-effects of concurrent file manipulation operations. We have developed and used a comprehensive suite of concurrency testing cases to derive and compare the results produced by CSOT and three industrial cloud storage systems and made interesting discoveries.

Operational Transformation (OT) is a collaboration-enabling technology and increasingly adopted in a wide range of real-world applications. One long-lasting issue in OT research is detecting and resolving puzzles -- subtle and characteristic collaborative editing scenarios in which an OT system may fail. After many years of extensive search and research, a variety of intricate puzzles have been de-tected and resolved. However, it remains open whether all puzzles, under certain well-defined conditions, have been discovered. To address this issue, we set out to devise a system of verification frameworks and a software tool, that are independent of specific OT algorithms and able to ex-haustively cover all possible transformation cases in which puzzles (if any) will manifest themselves. With the support of these tools, we verified OT correctness and concluded: all puzzles, under basic data and operation models and established transformation properties, have been discov-ered and resolved. Our discoveries help resolve a number of long-standing mysteries surrounding OT correctness and contribute to the advancement of OT fundamental knowledge and technology.

One core issue in real-time collaborative 3D design systems is dependency-conflict caused by concurrent access to object replicas in Dependency Graph (DG) states -- the common underlying structure of 3D design systems. Prior work has provided an Operational Transformation (OT) solution to dependency-conflict resolution, assuming dependency-conflict can be detected. But dependency-conflict detection is a complex and challenging issue because dependency relations among targets of concurrent operations -- a necessary condition for dependency-conflict -- is dynamic in nature and the detection must refer to prior DG states that are often unavailable during dependency-conflict detection. Conflict detection was never a difficult issue in prior OT work based on well-defined linear data models because conflict relations are readily derivable from operation position parameters without having to refer to prior document states. This work is the first to recognize and solve the dependency-conflict detection problem, which complements prior work in dependency-conflict resolution to provide a complete solution to dependency-conflict problem in real-time collaborative DG-based systems. Both theoretical verification and real implementation have been applied to validate the proposed dependency-conflict detection solution.

Telepointers are a real-time collaborative feature to indicate pointing at shared objects. Existing telepointing techniques are, however, restricted to pointing at the foremost object underneath a mouse cursor in relaxed-space but strict-time WYSIWIS environments. In real-time collaborative 3D design systems with animation creation capabilities, multiple 3D objects can be simultaneously visible underneath mouse cursors for users to freely and concurrently work on and point at (unconstrained collaboration), and multiple users can view 3D workspaces and point from different viewing perspectives (relaxed-space WYSIWIS) and animation time frames (relaxed-time WYSIWIS). This paper contributes a novel XPointer technique with the capability of pointing through objects correctly and consistently from different viewing perspectives and time frames, even in the presence of concurrent editing work. This work is the first to identify and address these advanced 3D telepointing needs and capabilities, and to extend the concept of relaxed WYSIWIS to include the time aspect. The XPointer has been implemented in the CoMaya real-time collaborative 3D design system (demonstration video: http://cooffice.ntu.edu.sg/comaya/videoXPointer.php).

Conflict resolution is one major challenge in real-time distributed collaborative 3D design systems, which allow concurrent collaborative work on shared 3D documents. Operational Transformation (OT) is a core conflict resolution technique in a range of real-world collaborative systems. No existing OT technique is, however, capable of resolving conflicts among objects with dependency relations, i.e. an update of one object may propagate to other connected/dependent objects, which is commonly used in 3D or complex graphic design systems. This paper contributes a novel OT solution with such a capability for collaborative 3D design systems. This work is the first to extend OT capability to dependency conflict resolution, and OT application scope from 1D/2D to 3D applications, thus advancing the state-of-the-art of OT in both theory and practical application. The proposed solution has been theoretically verified for its correctness in detecting dependency conflicts and achieving consistent results, and implemented in the CoMaya collaborative design system.

Various workspace awareness widgets and supporting techniques have been developed for collaborative 2D systems, but little has been done in supporting these widgets in collaborative 3D systems. In this paper, we contribute a novel awareness widget - televiewpointer, which provides integrated and flexible televiewing and telepointing capabilities in real-time collaborative 3D design systems that allow relaxed WYSIWIS and concurrent work. Distinctive features of the televiewpointer include: (1) extension of telepointers from 2D to 3D representation with a distant telepointing capability; (2) integration with view frustums to represent users' view scope and workspace contextual information for telepointing; (3) incorporation of mirror views to provide complementary views to the shared 3D workspace and a distributed radar view; and (4) combination with 2D telepointers to provide a flexible telepointing service in multiple working/viewing spaces without requiring users to synchronize their working perspectives. Supporting televiewpointers in real-time collaborative 3D designs systems is challenging because the free and concurrent work and televiewpoint raises a potential problem of inconsistent and incorrect workspace awareness information. This paper discusses the design rationales behind the proposed televiewpointer features, presents technical solutions in supporting these features and maintaining their consistencies, and formulates usability hypotheses in relation to these features for future evaluation. All features and techniques reported in this paper have been implemented in the CoMaya collaborative 3D design system. The demonstration video of the televiewpointer is available at http://cooffice.ntu.edu.sg/comaya/videoTVP.php.

Complex 3D digital media creation demands anytime and anywhere collaboration support. The CoMaya project aims to incorporate such advanced collaboration capabilities into Autodesk Maya. This paper reports some research findings and lessons we learned from extending the transparent adaptation approach from 2D office applications to 3D digital media design tools.