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

Stress causes and exacerbates many physiological and mental health problems. Routine and unobtrusive monitoring of stress would enable a variety of treatments, from break-taking to calming exercises. It may also be a valuable tool for assessing effects (frustration, difficulty) of using interfaces or applications. Custom sensing hardware is a poor option, because of the need to buy/wear/use it continuously, even before stress-related problems are evident. Here we explore stress measurement from common computer mouse operations. We use a simple model of arm-hand dynamics that captures muscle stiffness during mouse movement. We show that the within-subject mouse-derived stress measure is quite strong, even compared to concurrent physiological sensor measurements. While our study used fixed mouse tasks, the stress signal was still strong even when averaged across widely varying task geometries. We argue that mouse sensing "in the wild" may be feasible, by analyzing frequently-performed operations of particular geometries.

Conflict is common in collaboration, and may have both negative and positive effects on collaborative work. Past research has focused on controlling negative aspects of conflict by preventing, eliminating or isolating conflicts, but done little on exploring positive aspects of conflict. In this paper, we contribute a novel creative conflict resolution (CCR) approach to address these issues in real-time collaborative editing systems. In addition to maintaining consistency, the CCR approach is able to create new results from conflicts, generate alternative solutions based on collective effects of conflict operations, and support users to choose suitable conflict solutions and conflict resolution policies according to their needs. The CCR approach provides not only a new way of resolving conflicts in real-time collaborative editing systems, but also a framework for supporting a range of existing conflict resolution strategies. Techniques and user interface issues related to the CCR approach and a prototype implementation are discussed in this paper.

Understanding and facilitating real-life social interaction is a high-impact goal for Ubicomp research. Microphone arrays offer the unique capability to provide continuous, calm capture of verbal interaction in large physical spaces, such as homes and (especially open-plan) offices. Most microphone array work has focused on arrays of custom sensors in small spaces, and a few recent works have tested small arrays of commodity sensors in single rooms. This paper describes the first working scalable and cost-effective array that offers high-precision localization of conversational speech, and hence enables ongoing studies of verbal interactions in large semi-structured spaces. This work represents significant improvements over prior work in three dimensions -- cost, scale and accuracy. It also achieves high throughput for real-time updates of tens of active sources using off-the-shelf components. We describe the system design, key localization algorithms, and a systematic performance evaluation. We then show how source location data can be usefully aggregated to reveal interesting patterns in group conversations, such as dominance and engagement.

Operational Transformation (OT) is a consistency maintenance technique for collaborative editing systems-a special class of distributed applications for supporting human-computer-human interaction and collaboration over communication networks. The theory of causality has been the foundation of all prior OT systems, but it is inadequate to meet essential OT requirements in functionality and correctness. In this paper, we analyze the limitation of the causality theory, propose a novel theory of operation context as the new foundation for OT systems, and present a new OT algorithm-Context-based OT (COT)-which provides uniform and efficient solutions to both consistency maintenance and undo problems. The COT algorithm has been implemented and used for supporting a range of novel collaborative applications. The context theory and context vectors are potentially applicable to other distributed computing applications.

Operational Transformation (OT) is a technique for consistency maintenance and group undo, and is being applied to an increasing number of collaborative applications. The theoretical foundation for OT is crucial in determining its capability to solve existing and new problems, as well as the quality of those solutions. The theory of causality has been the foundation of all prior OT systems, but it is inadequate to capture essential correctness requirements. Past research had invented various patches to work around this problem, resulting in increasingly intricate and complicated OT algorithms. After having designed, implemented, and experimented with a series of OT algorithms, we reflected on what had been learned and set out to develop a new theoretical framework for better understanding and resolving OT problems, reducing its complexity, and supporting its continual evolution. In this paper, we report the main results of this effort: the theory of operation context and the COT (Context-based OT) algorithm. The COT algorithm is capable of supporting both do and undo of any operations at anytime, without requiring transformation functions to preserve Reversibility Property, Convergence Property 2, Inverse Properties 2 and 3. The COT algorithm is not only simpler and more efficient than prior OT control algorithms, but also simplifies the design of transformation functions. We have implemented the COT algorithm in a generic collaboration engine and used it for supporting a range of novel collaborative applications.

Single-user interactive computer applications are pervasive in our daily lives and work. Leveraging single-user applications for supporting multi-user collaboration has the potential to significantly increase the availability and improve the usability of collaborative applications. In this article, we report an innovative Transparent Adaptation (TA) approach and associated supporting techniques that can be used to convert existing and new single-user applications into collaborative ones, without changing the source code of the original application. The cornerstone of the TA approach is the operational transformation (OT) technique and the method of adapting the single-user application programming interface to the data and operation models of OT. This approach and supporting techniques were developed and tested in the process of transparently converting two commercial off-the-shelf single-user applications (Microsoft Word and PowerPoint) into real-time collaborative applications, called CoWord and CoPowerPoint, respectively. CoWord and CoPowerPoint not only retain the functionalities and “look-and-feel” of their single-user counterparts, but also provide advanced multi-user collaboration capabilities for supporting multiple interaction paradigms, ranging from concurrent and free interaction to sequential and synchronized interaction, and for supporting detailed workspace awareness, including multi-user telepointers and radar views. The TA approach and generic collaboration engine software component developed from this work are potentially applicable and reusable in adapting a wide range of single-user applications.

Effective interaction among participants is crucial to the success of a presentation. The workspace of a presentation, which is the presentation slides, is a natural and effective medium of interactions among presentation participants. However, due to the insufficient support from existing collaborative presentation systems, workspace-mediated interaction is inconvenient in presentations, especially in collaborative presentations. In this paper, we explore typical workspace-mediated interaction forms and analyze their characteristics. Based on this analysis, we present a series of approaches to supporting workspace-mediated interaction in the context of the CoPowerPoint system.

Object grouping is an effective means for managing the complexity in graphics editing. However, research on collaborative object grouping has not been adequate. In this paper, we contribute a novel collaborative object grouping technique, called CoGroup. CoGroup can achieve maximal combined effects among compatible operations and preserve all users' work in the face of conflict without the overhead of undoing and redoing conflict operations as in existing serialization approaches. CoGroup has been implemented in collaborative word processing (CoWord) and slide authoring (CoPowerPoint) systems and is generally applicable to a range of off-the-shelf commercial graphics applications, particularly CAD/CASE tools.

Telepointers are a real-time groupware interface feature to indicate where other users are pointing. None of existing telepointer techniques, however, is capable of tracking the reference object and preserving the relative position in the face of dynamic content and view changes in real-time collaborative document editing systems. In this paper, we report a novel object-associated telepointer (OAT) technique with the following features in the face of dynamic content and view changes: (1) relocating telepointers to track the reference object; (2) preserving the position relative to the reference object; and (3) providing feedback of the telepointer relocation to the local user with a virtual local cursor. The key technique for supporting OAT is to extend the operational transformation technique with a generic Refer operation to support adjusting the reference object position. The OAT technique has been implemented in the CoWord system based on the transparent adaptation approach so that it can provide the OAT support to a range of realtime collaborative applications.

Operational Transformation (OT) is a technique originally invented for supporting consistency maintenance in collaborative text editors. Word processors have much richer data types and more comprehensive operations than plain text editors. Among others, the capability of updating attributes of any types of object is an essential feature of all word processors. In this paper, we report an extension of OT for supporting a generic Update operation, in addition to Insert and Delete operations, for collaborative word processing. We focus on technical issues and solutions involved in transforming Updates for both consistency maintenance and group undo. A novel technique, called Multi-Version Single-Display (MVSD), has been devised to resolve conflict between concurrent Updates, and integrated into the framework of OT. This work has been motivated by and conducted in the CoWord project, which aims to convert MS Word into a real-time collaborative word processor without changing its source code. This OT extension is relevant not only to word processors but also to a range of interactive applications that can be modelled as editors.

Single-user interactive computer applications are pervasive in our daily lives and work. Leveraging single-user applications for multi-user collaboration has the potential to significantly increase the availability and improve the usability of collaborative applications. In this paper, we report an innovative transparent adaptation approach for this purpose. The basic idea is to adapt the single-user application programming interface to the data and operational models of the underlying collaboration supporting technique, namely Operational Transformation. Distinctive features of this approach include: (1) Application transparency: it does not require access to the source code of the single-user application; (2) Unconstrained collaboration: it supports concurrent and free interaction and collaboration among multiple users; and (3) Reusable collaborative software components: collaborative software components developed with this approach can be reused in adapting a wide range of single-user applications. This approach has been applied to transparently convert MS Word into a real-time collaborative word processor, called CoWord, which supports multiple users to view and edit any objects in the same Word document at the same time over the Internet. The generality of this approach has been tested by re-applying it to convert MS PowerPoint into CoPowerPoint.

The widespread distribution and availability of small-scale sensors, actuators, and embedded processors is transforming the physical world into a computing platform. One such example is a sensor network consisting of a large number of sensor nodes that combine physical sensing capabilities such as temperature, light, or seismic sensors with networking and computation capabilities [1]. Applications range from environmental control, warehouse inventory, health care to military environments. Existing sensor networks assume that the sensors are preprogrammed and send data to a central frontend where the data is aggregated and stored for offfsline querying and analysis. This approach has two major draw-backs. First, the user cannot change the behavior of the system on the fly. Second, communication in today's networks is orders of magnitude more expensive than local computation, thus in-network processing can vastly reduce resource usage and thus extend the lifetime of a sensor network.This demo demonstrates a database approach to unite the seemingly conflicting requirements of scalability and flexibility in monitoring the physical world. We demonstrate the COUGAR System, a new distributed data management infrastructure that scales with the growth of sensor interconnectivity and computational power on the sensors over the next decades. Our system resides directly on the sensor nodes and creates the abstraction of a single processing node without centralizing data or computation.