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.

Real-time collaborative programming allows programmers to concurrently edit shared source code over communication networks. To support semantic conflict prevention, prior work has proposed a bask dependency-based automatic locking (DAL) approach to automatically grant locks on source code regions with dependency relationships, under the assumptions that there exists no locking-scope overlapping among concurrent editing operations, and the source code structure remains static during the collaboration process. To address major restrictions of the basic DAL scheme, this paper presents a shard-locking approach and techniques to fully support unconstrained real-time collaborative programming with semantic conflict prevention. The approach allows multiple programmers to concurrently edit source code regions with overlapping locking scopes in the presence of concurrent editing operations and dynamic source code structures. The techniques and solutions have been implemented in a research prototype for evaluations.

Nowadays, collaborative editing systems, such Google Docs, Microsoft Office Web Apps, and Codox Wave Apps (for supporting read-time editing in existing Web browser-based editors, including Gmail, Wikipedia, Evernote, and WordPress), are commonly used by hundreds of millions of people around the world. Research on collaborative editing, however, started in the 1980s as a niche area in the field of Computer-Supported Cooperative Work, and was initially driven mainly by academic curiosity. This niche area has evolved for decades and resulted in wide adoption in major IT industry products in recent years. In this paper, the author reflects on the evolution of collaborative editing research and application, including representative academic research projects, industrial products, and open source software projects. He will also share his views on the current trends, opportunities and challenges in future collaborative editing research and real-world applications.

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.

In this paper, we report our discovery of general transformation conditions and patterns underlying a range of Operational Transformation (OT) systems for achieving convergence. Based on these conditions and patterns, we have established convergence correctness of seven existing OT systems, and designed two new OT systems with a unique combination of novel features for supporting advanced collaborative applications. These results contribute to the advancement of OT knowledge, technology, and OT-based collaboration editing systems.

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.

In this paper, we present a comprehensive and in-depth study on convergence preservation and avoidance in Operational Transformation (OT) systems. In this study, we discovered basic conditions, transformation patterns, and mechanisms for avoiding Convergence Property 2 (CP2), and established CP2-avoidance correctness of seven major OT systems. Furthermore, we proposed improvements to existing systems and designed a new OT system capable of avoiding CP2 with a unique combination of novel features. These results contribute significantly to the advancement of OT and collaboration-enabling 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).

Social search empowers seekers to help each other find the information they need by sharing their domain knowledge and search efforts. Current social search activities are primarily voluntary, acted on the goodwill to help others or the purpose for self-promotion and the contributed content is mostly retrievable free of charge to the public. However, the voluntary nature of social search compromises its long-term sustainability as participants are not offered intrinsic incentives to contribute and share information, and free information presents intricate ramifications on the its quality. In this paper, we present the idea of knowledge bartering, where one can barter a knowledge item they have for another item they wish to have. To make the idea viable, we propose the online silk road solution to automate a knowledge bartering process that can maximise the social welfare within a community.

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.

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.

Operational Transformation (OT) is commonly used for conflict resolution in real-time collaborative applications, but none of existing OT techniques is able to solve a special type of conflict - orthogonal conflict, which may occur when concurrent operations are inserting/deleting an arbitrary number of objects in different dimensions of a two-dimensional (2D) workspace, such as spreadsheet documents. This paper is the first to identify and solve the orthogonal conflict problem by extending OT with a new capability of resolving 2D conflicts. Extending OT from one- to two-dimensional conflict resolution is fundamental to the theory and application of OT, and technically challenging as well because 2D orthogonal conflict is different from but intimately related to the one-dimensional positional shifting conflict and necessitates new and integral solutions for multi-dimensional conflicts. In this paper, we present formal definitions of orthogonal conflict, pseudo-code description, design rationale analysis, and correctness verification and complexity analysis of the 2DOT solution.

Real-time collaborative programming environments support a team of programmers to edit the same shared source code document concurrently over communication networks. This paper presents the design and implementation of a novel real-time collaborative programming system named CoEclipse, which transparently converts the single-user Eclipse IDE into a multi-user real-time collaborative programming tool, incorporates and integrates syntactic and semantic consistency maintenance techniques derived from our prior work, and provides advanced awareness features for supporting semantic conflict prevention. The novelties of CoEclipse include its full compatibility with existing single-user programming environments in terms of user interfaces and working processes, seamless integration of syntactic and semantic consistency maintenance features, and providing complementary approaches of awareness and locking in collectively supporting semantic conflict prevention. Furthermore, the CoEclipse approach in supporting advanced real-time collaboration is generic, which can be applied to other application domains for achieving similar design objectives and rationales.

Real-time collaborative programming and non-real-time collaborative programming are two classes of methods and techniques for supporting programmers to jointly conduct complex programming work in software development. They are complementary to each other, and both are useful and effective under different programming circumstances. However, most existing programming tools and environments have been designed for supporting only one of them, and little has been done to provide integrated support for both. In this paper, we contribute a novel Any-Time Collaborative Programming Environment (ATCoPE) to seamlessly integrate conventional non-real-time collaborative programming tools and environments with emerging real-time collaborative programming techniques and support collaborating programmers to work in and flexibly switch among different collaboration modes according to their needs. We present the general design objectives for ATCoPE, the system architecture, functional design and specifications, rationales beyond design decisions, and major technical issues and solutions in detail, as well as a proof-of-concept implementation of the ATCoEclipse prototype system.

Trust management is a paramount issue in social networks. Existing models based on global reputation are simplistic as they do not support personalised measures for individual users. Models based on local trust propagation tend to be too subjective to be reliable as they do not consider a social network in its entirety. More importantly, neither model has taken the risk factor into the consideration of trust management. In this paper, we contribute a novel trust model that allows personalised measures to be naturally established on objective grounds through tracing credit flows within a social network, where the trust between a pair of users can be derived from the credit flowing from one into the other and the relative risk disparity between them. This model uses power flows in an electrical grid as a metaphor for the credit flows in a social network and is based on the hypothesis that the credit flows in a social network are similar in nature to the power flows in an electrical grid. Experiments with a real-world dataset have proved the hypothesis and the results have shown that the credit flow based trust model can derive not only personalised but also more accurate trust measures than existing models do.

Recent years have witnessed the emergence and rapid development of collaborative Web-based applications exemplified by Web-based office productivity applications. One major challenge in building these applications is maintaining data consistency while meeting the requirements of fast local response, total work preservation, unconstrained interaction, and customizable collaboration mode. These requirements are important in determining users’ experiences in interaction and collaboration, and in meeting users’ diverse needs under complex and dynamic collaboration and networking environments; but none of existing solutions is able to meet all of them. In this article, we present a data consistency maintenance solution capable of meeting these requirements for collaborative Web-based applications. Major technical contributions include an efficient sequence-based operation transformation control algorithm based on the concept of contextualization, an operation broadcast protocol for supporting a variety of collaboration modes, an operation replaying algorithm for ensuring fast local response and efficient remote operation replay, and a set of communication protocols for managing the integrity of collaborative Web-based sessions. The proposed solution has been implemented in a prototype collaborative Web-based editor WRACE and the correctness of the solution is formally verified in the article.

Operational transformation (OT) is a collaborative computing technology for supporting advanced collaborative applications. OT was originally invented for consistency maintenance and concurrency control in collaborative editing of plain text documents in 80s. Two decades of research has extended OT functionalities and applications to include group undo, conflict resolution, operation notification and compression, group-awareness, HTML/XML document editing, collaborative office productivity tools, and collaborative computer-aided digital media design tools. Because of its lock-free, unconstrained interaction control, and consistency-preserving properties, OT is particularly suitable for supporting real-time collaboration over the Internet. OT has recently been adopted as the core collaboration technique in Google Wave, which is taking OT to a new range of web-based applications and services, including e-mail, instant messaging, blogging, wiki, and social networking. The speaker has been working on OT research and application since 1994. In this talk, the speaker will share his experiences and lessons in researching OT issues, designing OT algorithms, and building OT-based collaborative applications, from 1-dimensional text editors (e.g. CoVim), 2-dimensional word processors (e.g. CoWord), to 3-dimensional computer-aided digital media design tools (e.g. CoMaya).

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.

Formulating proper keywords and evaluating search results are common difficulties in exploratory information seeking. Reusing and refining others' successful searches are pragmatic directions to tackle these difficulties. In this paper, we present a novel epistemology-based social search solution, where search epistemologies are effectively shared, reused, and refined by others with the same or similar search interests through novel user interfaces. We have developed a prototype system Baijia and experimental results show that an epistemology-based social search system outperforms a conventional search engine in supporting exploratory information seeking.

Computer-Aided Design (CAD) applications provide industrial design communities with various computer-based tools to perform design activities. Innovation is an important requirement in most design tasks. This paper presents a novel approach to inspiring innovative design integration in a horizontal collaboration process. The approach allows individual designers' works to be integrated and multiple design choices to be explored. The technique is currently applied to design work involving Boolean operations-widely available in most CAD operations, where a major technical challenge is to integrate a group of concurrent Boolean operations for design exploration. The approach is particularly helpful to inspire innovation in the integration phases of industrial design tasks such as accessory design, art design, and digital media design.

It has been years since Computer-Aided Design (CAD) technology was used to assist engineers, architects and other design professionals in their design activities. Collaboration has been increasingly needed in the CAD community and various CSCW technologies have thus been adopted to support the development of collaborative design systems. Existing collaborative CAD applications suffer from several problems such as not allowing concurrent work and poor local response. In this paper, we report our approaches to converting single-user CAD applications into collaborative ones, based on the Transparent Adaptation (TA) technique. The approach is able to significantly improve productivity of collaborative designers as well as provide a human-centered collaborative design environment. To prove the feasibility of our approach, we have successfully converted the single-user AutoCAD application into a collaborative one, named as CoAutoCAD. Key issues on the design of CoAutoCAD are reported in this paper.

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.

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.

Globalization leads to an efficient new business paradigm generally known as Collaborative Virtual Enterprise (CVE) which demands flexible service orchestration and robust workflow execution. As two major service orchestration strategies, OWL-S and BPEL have their own strength and deficiencies. To meet the challenge in CVE, in this paper, we propose a Workflow Execution System (WES) that takes advantage of the complementary strengths of these two technologies. On the one hand, having semantic support, OWL-S is used in dynamic service discovery and composition at high level. On the other hand, at the concrete level, industry-based BPEL is exploited in service execution. The description of each Semantic Web service is enhanced with rule-based modeling of the essential business logic behind the service interface. In order to realize interoperability in OWL-S and BPEL without loss of semantic information, we further proposed an OWLS2BPEL Mapper to facilitate the workflow robustness and support rule evaluation to increase responsiveness to customers. A concrete scenario in PC manufacturing Collaborative Virtual Enterprise is analyzed to demonstrate the effectiveness of our workflow execution system.

Constraints maintenance plays an important role in keeping the integrity and validity of models in UML software modeling. Constraints maintenance capabilities are reasonably adequate in UML modeling applications, but few work has been done to address the distributed constraints maintenance issue in collaborative UML modeling environments. In this paper, we propose a novel solution to the issue, which can retain the effects of all concurrent modeling operations even though they may cause constraints violations. We further contribute a distributed constraints maintenance framework, in which the solution is encapsulated as a generic engine to be mounted in a variety of single-user UML modeling applications for supporting distributed collaborative UML modeling and distributed constraints maintenance.

With an increasing complexity of business processes, self-healing capability is becoming an important issue in order to support robust service flow execution. In this paper, a dynamic self-healing mechanism is proposed, which can dynamically identify suitable alternatives and replace faulty services such that a service flow can be performed successfully despite of unexpected exceptions. This mechanism explicitly utilizes semantic Web services for service matching and selection of a composite service in business service flow, and Semantic Web services are equipped with rich business rules in a domain-dependent manner. We explore the self-healing mechanism for supporting self-healable service flow execution which is modeled in BPEL4WS. A demo system of self-healing capable service flow execution is built to validate its effectiveness by a concrete scenario, PC manufacturing application.

Constraints allow users to declare relationships among objects and let the constraint systems maintain and satisfy these relationships. Formulas have been adopted to express constraints in a wide variety of single-user applications, because of their simplicity, efficiency and manageability. The needs and benefits of supporting formula-defined constraints in collaborative environments have long been recognized. However, maintaining both constraints and consistency in the presence of concurrency in collaborative systems is a challenge. In these systems, users may concurrently define formulas, which could result in that different formulas are defined to express the same object attribute at different sites. In this article, we discuss the issues and techniques in maintaining formula-defined constraints in collaborative systems. In particular, we also proposed a method that is able to maintain both constraints and system consistency in concurrent environments based on the existing consistency maintenance approaches. This method extends the application of these approaches from collaborative systems without constraint to systems that support formulas. The proposed method has been applied to implement a collaborative Visio system, called CoVisio, which leverages single-user Microsoft Visio for multi-user collaboration. Specific issues related to CoVisio are also discussed in detail.

Recent advancements in collaboration technology have shown that it is possible to convert existing single-user applications into real-time collaborative applications without modifying the source codes of the single-user applications. Such conversion relies on the API (Application Programming Interface) provided by the single-user applications. Poorly designed APIs make such conversion difficult, inefficient, or even impossible. Until now, it is not well understood what features APIs should provide to facilitate conversion of single-user applications into collaborative applications. This paper presents recommendations of the features single-user application APIs should provide to facilitate conversion. The results are based on what we have learnt from converting Microsoft Visio, into real-time collaborative Visio (CoVisio), and our previous experience in building CoWord and CoPowerPoint.

Constraints are very useful in real-time collaborative editing systems. They are able to automatically enforce semantic rules and properties. A specific type of constraint is dataflow constraint. Any property that can be expressed as an equation can be represented as a dataflow constraint. However, ensuring multi-way dataflow constraint satisfaction and consistency maintenance in a replicated collaborative environment is a challenge. This paper presents a novel method for computing multi-way dataflow constraint propagation for real-time collaborative editing systems. This method produces convergent result that is consistent with syntax level effect, irrespective of the operation execution order. This method is generic and is applied to enforce object placement and label name consistency in a realtime collaborative CASE system

Modeling is commonly used in the process of software development. UML (Unified Modeling Language) is a standard software modeling language and has been widely adopted for software analysis and design. As software systems are getting larger and more complex nowadays, software modeling using UML often requires collective and collaborative efforts from multiple software designers. In contrast, most of today's software modeling applications are still single-user-oriented and do not offer much help to coordinate interaction and collaboration among team members. In this paper, we will present the technical challenges and solutions in providing advanced collaboration capabilities and transparently integrating them into mainstream software modeling applications to effectively facilitate collaboration among geographically dispersed software designers. The work has been tested and demonstrated by the design of CoRSA (Collaborative Rational Software Architect) - an experimental collaborative software modeling prototype based on RSA, one of the most widely used commercial software modeling applications in the market

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.

Collaborative document repository manager (CDRM) is one of the three key components in a collaborative editing system. It provides a repository for storing shared documents and a portal for managing shared documents, initiating collaborative editing sessions, and viewing session information. While most collaborative systems have been using ad hoc and tightly-coupled CDRMs, our work is to provide a generic WebDAV-based CDRM to take advantage of WebDAV's ubiquitous accessibility, directly writable medium, and access transparency. This WebDAV-based CDRM has been deployed into the CoOffice (collaborative office) and the CoStarOffice (collaborative staroffice) systems for evaluation, demonstration, and usability study

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.

Multi-way dataflow constraints are very useful in the development of collaborative applications, such as collaborative CAD and CASE systems, but satisfying multi-way dataflow constraints in the presence of concurrency in collaborative systems is difficult. In this article, we discuss the issues and techniques in maintaining multi-way dataflow constraints in concurrent environments. In particular, we also proposed a novel strategy that is able to reconstruct computation flows to satisfy multi-way dataflow constraints according to concurrent user operations in collaborative systems. Our strategy ensures both constraint satisfaction and system consistency, which is independent of the execution orders of concurrent operations.

With the rapid popularity of computer networks, collaborative document writing becomes increasingly desirable in recent years. In practice, collaborative writing is more likely to be done in an asynchronous manner, where collaborators usually work in parallel with different time schedules and are not present at the same time. Merging is the key technique to support concurrent writing and textual merging remains the primary and the only successful merging function to date. However, most of existing systems support constrained textual merging for the simplicity of the underling merging algorithms. In this paper, we propose a flexible operation-based syntactic textual merging algorithm that is capable of reconciling changes made in parallel by different users according to the syntax of the files to be merged or user-specified merging policies. Moreover, this syntax-based reconciliation algorithm is able to preserve the intentions of individual changes.

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.

Software configuration management (SCM) systems are very important for coordinating group efforts in developing large and complex software systems. The ability to support concurrent software development is the key to deliver high quality software with low time-to-market, where merging is the core enabling technique. Textual merging is the primary and the only successful merging function available in today's SCM systems. However none of them supports complete textual merging, which is not only very useful itself but also the foundation for syntactic and semantic textual merging. We propose a novel operation-based textual merging algorithm, which has the capability of supporting complete textual merging while still preserving the intentions of individual editing operations.

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.

An unfavorable phenomenon is observed: current electronic markets are fragmented and have formed a set of autonomously distributed product information islands. This leads to heterogeneity of product information between separated sources and makes difficult on product document interoperation. To resolve the issue and facilitate business document interoperation, this paper proposes a heterogeneous concept mapping approach. By this approach, heterogeneous product documents are transformed from one context to another context without losing any semantic information. This transformation process is supported by a heterogeneous concept transformation algorithm that includes five transformation steps: source-local context transformation, local-common context transformation, common-common context transformation, common-local context transformation and local-source context transformation.

Product data exchange is the precondition of business interoperation between Web-based firms. However, millions of small and medium sized enterprises (SMEs) encode their Web product data in ad hoc formats for electronic product catalogues. This prevents product data exchange between business partners for business interoperation. To solve this problem, this paper has proposed a novel concept-centric catalogue engineering approach for representing, transforming and comparing semantic contexts in ad hoc product data exchange. In this approach, concepts and contexts of product data are specified along data exchange chain and are mapped onto several novel XML product map (XPM) documents by utilizing XML hierarchical structure and its syntax. The designed XPM has overcome the semantic limitations of XML markup and has achieved the semantic interoperation for ad hoc product data exchange.

The most common task being performed on the World Wide Web, namely exploring its contents remains an individual rather than a cooperative, shared or partnered activity. We propose that the existing model of collaborative browsing, namely master/slave, is too restrictive. Instead, we introduce group unified histories to provide unconstrained cooperative browsing. Our approach is founded on a persistent shared history object which is replicated for each user and totally configurable. In order for cooperation to succeed users are updated of changes taking place and shown the history of documents within the context of the group. Replication means that consistency needs to be maintained. We show that unconstrained cooperative browsing is a subset of collaborative editing, and using the consistency model of real-time collaborative editors achieves consistency and provides awareness in group unified histories.

Version control systems are widely used to support distributed concurrent software development, where document merging is a key function. Most existing systems adopt state-based merging, which relies on the derivation of deltas among documents. The derivation of deltas involves transferring documents over the network and executing time-consuming text differentiation algorithms, which may result in a poor system response. Operation-based merging saves executed operations in logs as deltas, thus eliminating the need for deriving deltas. However, for the operation-based merging to be adopted in version control systems, a major technical challenge is how to keep the size of logs small so that it requires less time to transfer the log over the network and to re-execute operations in the log. In this paper we contribute a novel compression algorithm, which is able to minimize the size of a log as well as the number of operations within it. It has been proven both correct and complete in the sense that the compressed log has the same effect as the original one and operations that can be merged have already been merged.

Griffith Sciences, School of Information and Communication Technology

Notification is an essential feature in collaborative systems, which determines a system's capability and flexibility in supporting different kinds of collaborative work. In the past years, various notification strategies have been designed for different systems. However, the design of notification components has been ad hoc, and the techniques used for supporting notification have been application-dependent. In this paper, we contribute a flexible notification framework that can be used to describe and compare a range of notification strategies used in existing collaborative systems, and to guide the design of notification components for new collaborative systems. The framework has been applied to the design of a notification component for a group editor, which uses a single notification mechanism to support various notification policies for meeting both real-time and non-real-time collaboration needs. In addition, a new operational transformation control algorithm has been devised in combination with the notification component, which is significantly simpler and more efficient than existing algorithms.

As an important mechanism for error recovery and exploration of alternatives in interactive and collaborative applications, an undo facility should have the capability of undoing any operation at any time. However, supporting undo in collaborative applications is technically challenging and none of the existing group undo solutions is able to offer such a capability. In this article, we contribute an undo solution with such a capability for group text editors. The basic idea is to interpret an undo command as a concurrent inverse operation by means of operational transformation. To cope with the high complexity of group undo, a generic undo framework has been adopted to separate undo policy from the undo mechanism and to separate transformation control algorithms from transformation functions. The proposed undo solution consists of a generic transformation control algorithm that is capable of generating, transforming, and representing valid inverse operations in any context, and a set of transformation functions that are capable of preserving undo-related transformation conditions and properties. Formal proofs are provided to show the correctness of the undo transformation control algorithm in achieving the required undo effect, undo property, and consistency properties. Solutions to the known undo puzzles are provided to show soundness of the transformation functions. A Web-based group text editor REDUCE (REal-time Distributed Unconstrained Cooperative Editing) has been implemented to demonstrate the feasibility and usability of the proposed undo and other technical solutions. The proposed undo solution is generally applicable to collaborative applications that support concurrent insertion and deletion on shared documents consisting of one or multiple dimensions of linearly ordered data objects with positional references.

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. In this article, we propose an object-level multiversioning approach to consistency maintenance in real-time collaborative graphic editors. This approach is novel in achieving intention preservation and convergence, in preserving the work concurrently produced by multiple users in the face of conflict, and in minimizing the number of object versions for conflict resolution. Major technical contributions of this work include a formal specification of a unique combined effect for an arbitrary group of conflict and compatible operations, a distributed algorithm for incremental creation of multiple object versions, a consistent object identification scheme for multiple object versions, and a convergent layering scheme for overlapping objects. All algorithms and schemes presented in this article have been implemented in an Internet-based GRACE (graphics collaborative editing) system.

Locking is a standard technique used in distributed computing and database systems to ensure data integrity by prohibiting concurrent conflicting updates on shared data objects. Internet-based collaborative systems are a special class of distributed applications which support human-to-human interaction and collaboration over the Internet. In this paper, a novel optional and responsive fine-grain locking scheme is proposed for consistency maintenance in Internet-based collaborative editors. In the proposed scheme, locking is made optional in the sense that a user may update any part of the document without necessarily requesting a lock. In the face of high communication latency in the Internet environment, responsive locking is achieved by granting the permit to the user for updating the data region immediately after issuing a locking request. Moreover, multiple fine-grain locks can be placed on different regions inside a document to allow concurrent and mutually exclusive editing on the same document. Protocols and algorithms for locking conflict resolution and consistency maintenance are devised to address special technical issues involved in optional and responsive fine-grain locking. The proposed locking scheme and supporting techniques were implemented in an Internet-based collaborative editor to demonstrate its feasibility and usability.

The paper proposes a novel view based consistency model for distributed shared memory. A view is a set of ordinary, data objects that a processor has the right to access in a data-race-free program. The view based consistency model only requires that the data objects of a view are updated before a processor accesses them. Compared with other memory consistency models, the view based consistency model can achieve data selection without user annotation and can reduce much false-sharing effect. This model has been implemented based on TreadMarks. Performance results have shown that for all our applications, the view based consistency model outperforms the lazy release consistency model.

Undo is a useful and widely supported feature which can be used to recover from erroneous operations, learn new system features, and explore alternative solutions. The ability to undo any operation at any time is especially important for collaborative editing systems because it can be used to support local or global undo and also multiple undo models. The Any Undo solution presented in this paper is able to undo any operation in collaborative graphics editing systems. The major challenge in designing the Any Undo solution is to produce the correct undo/redo effect when operations may be undone/redone in any order. The solution is divided into two parts. The first part focuses on how to produce the undo/redo effect on individual objects. Due to the use of multi-versioning concurrency control protocol, the second part of the solution focuses on producing the correct version and the correct number of versions. This Any Undo solution has been implemented in a collaborative graphics editing system called GRACE.

Real-time collaborative editing systems are distributed groupware systems that allow multiple users to edit the same document at the same time from multiple sites. A specific type of collaborative editing system is the object-based collaborative graphics editing system. Traditionally, locking has been used as the major concurrency control techniques in this type of system. This paper examines locking in a supporting role to the concurrency control technique of multi-versioning. Two types of locks are examined: object and region. Two optional and responsive locking schemes, instant locking and instant exclusive locking, are presented. Their advantages and disadvantages are discussed.

Intention preservation is an important aspect of consistency maintenance in distributed group editors. In this paper, we first introduce a classification framework for various kinds of intentions, then propose LOVOT (post-LOcking, multi-Versioning and Operational Transformation), an integrated scheme for intention preservation. With this scheme, individual users' compatible intentions are preserved by operational transformation, individuals' conflicting intentions are preserved by multi-versioning, and the preservation of a syntactically and semantically consistent group intention is facilitated by post-locking. An algorithm for preserving individual users' intentions is discussed in detail. The integrated scheme is fully distributed, highly responsive, non-blocking and capable of avoiding any locking overhead.

The ability to undo operations is an indispensable feature of real-time group editors, but supporting group undo is a difficult problem. None of the existing solutions for group undo is able to support undoing any operation at any time with guaranteed success. In this paper, we contribute a novel group undo solution with such a capability. The basic idea is to interpret an undo command as a concurrent inverse operation by means of operational transformation, so that an operation is always undoable regardless of its undo context. By separating undo policy from undo mechanism, multiple undo modes, such as single-step undo, chronological undo, and selective undo, can be supported in the same collaborative editing session. In addition, solutions to known undo puzzles are also provided. A web-based group text editor using the proposed undo solution has been implemented and is accessible at: http://reduce.qpsf.edu.au.

Groupware systems are a special class of distributed computing systems which support human-computer-human interaction. Real-time collaborative graphics editors 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. Resolving conflict access to shared objects is one of the core issues in the design of this type of system. This paper proposes a novel distributed multi-version approach to conflict resolution. This approach aims to preserve the work concurrently produced by multiple users in the face of conflicts, and to minimize the number of object versions for accommodating combined effects of conflicting and compatible operations. Major technical contributions of this work include a formal specification of a unique combined effect for any group of conflicting and compatible operations, a distributed algorithm for incremental creation of multiple object versions, and a consistent object identification scheme for multi-version and multireplica graphics editing systems. All algorithms and schemes preserved in this paper have been used in the GRACE (Graphics Collaborative Editing) system implemented in Java.

Object based collaborative graphics editing systems allow multiple users to edit the same graphics document at the same time from multiple sites. The paper examines the use of locking to prevent the generation of conflicting operations in this type of system. Two types of locks are examined: object and region. A locking scheme which preserves the intentions of all operations is proposed. Furthermore, the problems of lock ownership caused by concurrent operations are resolved.

The paper reports on an investigation into one of the most urgent problems facing distance language education: the problem of lack of exposure to speaking practice in the target language. The Open Learning Chinese Program taught at Griffith University is used as a case study. Following a discussion on issues relating to distance education for languages such as the indispensability of technology to learning languages in a distance mode, and the importance of communicative competence, the paper moves on to an examination of the capabilities of Internet based real time technology. Two major indications can be generated from this research: real time technology can help solve the problem of insufficient exposure to speaking practice, and a historical convergence of distance and traditional campus based education toward a networked education can be expected.

Communication latency presents a major challenge to achieving high responsiveness for Internet based cooperative editing systems. The authors propose conflict control locking (post-locking) schemes for conflict resolution in real time object based cooperative graphics editors. With these schemes, no locking request is needed before applying an editing operation to an object, instead, a lock will automatically be generated by the system if a conflict occurs. Lock ownership assigning rules are devised for the schemes. With a specific post-locking approach, algorithms and implementation techniques such as lock synchronisation detection, voting, and group intention realisation, are discussed in detail.

Real-time collaborative editing systems are groupware systems that allow multiple users to edit the same document at the same time from multiple sites. A specific type of collaborative editing system is the object-based collaborative graphics editing system. One of the major challenge in building such systems is to solve the concurrency control problems. This paper addresses the concurrency control problem of how to preserve the intentions of concurrently generated operations whose effects are conflicting. An object replication strategy is proposed to preserve the intentions of all operations. The effects of conflicting operations are applied to different replicas of the same object, while non-conflicting operations are applied to the same object. An object identification scheme is proposed to uniquely and consistently identify non-replicated and replicated objects. Lastly, an object replication algorithm is proposed to produce consistent replication effects at all sites.

Article Optimal locking integrated with operational transformation in distributed real-time group editors Share on Authors: Chengzheng Sun School of Computing and Information Technology, Griffith University, Brisbane, Qld 4111, Australia School of Computing and Information Technology, Griffith University, Brisbane, Qld 4111, AustraliaView Profile , Rok Sosič School of Computing and Information Technology, Griffith University, Brisbane, Qld 4111, Australia School of Computing and Information Technology, Griffith University, Brisbane, Qld 4111, AustraliaView Profile Authors Info & Claims PODC '99: Proceedings of the eighteenth annual ACM symposium on Principles of distributed computingMay 1999 Pages 43–52https://doi.org/10.1145/301308.301322Online:01 May 1999Publication History 16citation497DownloadsMetricsTotal Citations16Total Downloads497Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In order to support the interaction betweeen coexisting traditional short transactions and long cooperative transactions, we propose a novel timestamp ordering approach. With this timestamp ordering method, short transactions can be processed in the traditional way, as if there were no cooperative transactions. Therefore they will not be blocked by cooperative transactions. Cooperative transactions will not be aborted when there is a conflict with short transactions. Rather, they will incorporate the recent updates into their own processing. The serializabilities, among short transactions, and between a cooperative transaction (group) and other short transactions, are all preserved.

In order to support both traditional short transaction and long cooperative transactions, we propose a novel timestamp ordering approach. With this timestamp ordering method, short transactions can be processed in the traditional way, as if there are no cooperative transactions, therefore not be blocked by long transactions; cooperative transactions will not be aborted when there is a conflict with short transactions, rather it will incorporate the recent updates into its own processing; and the serializabilities, among short transactions, and between a cooperative transaction (group) and other short transactions, are all preserved.

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.

Analysing and visualising the run time behaviour of a distributed program requires collecting performance data during its execution. This is usually done through program instrumentation that inserts trace recording instructions into the program. The intrusiveness of inserted extra code to the original program may make the existing errors vanish, or can cause new errors to appear. It will not only change the real time execution speed, but also change the probability of making particular non deterministic choices. W. Cai and S.J. Turner (1994) proposed a logical clock approach (LCA) to control the inter process communication. It uses a logical clock in each process to reflect the real time execution of the process when running without monitoring. Not relying on any special hardware, this approach achieves minimum intrusiveness and makes the monitoring effect on the original program completely independent from the amount of time spent on monitoring activities. A main problem with LCA is that in an event of non deterministic communication and when several processes wait on each other's logical clock to advance, a deadlock may occur. LCA uses a carrier null message algorithm to break the deadlock situation. But sending an extra null message will distort the event timing information. Therefore, LCA is only suitable for debugging rather than for performance tuning. We present a major improvement to LCA, which preserves the timing information without introducing any deadlock. Our improved approach can support both debugging and performance tuning. We call our clocks virtual clocks to avoid confusion.

This paper proposes a transparent selective sequential consistency approach to distributed shared memory (DSM) systems. First, three basic techniques-time selection, processor selection, and data selection-are analyzed for improving the performance of strictly sequential consistency DSM systems, and a transparent approach to achieving these selections is proposed. Then, this paper focuses on the protocols and techniques devised to achieve transparent data selection, including a novel selective lazy/eager updates propagation protocol for propagating updates on shared data objects, and the critical region updated pages set scheme to automatically detect the associations between shared data objects and synchronization objects. The proposed approach is able to offer the same potential performance advantages as the entry consistency model or the scope consistency model, but it imposes no extra burden to programmers and never fails to execute programs correctly. The devised protocols and techniques have been implemented and experimented with in the context of the TreadMarks DSM system. Performance results have shown that for many applications, our transparent data selection approach outperforms the lazy release consistency model using a lazy or eager updates propagation protocol.

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

In real-time cooperative editing systems, independent operations on any part of the shared document may be generated from multiple cooperating sites. It is very important and technically challenging to ensure that the effect of executing an operation at remote sites, in the presence of concurrent execution of independent operations, achieves the same effect as executing this operation at the local site at the time of its generation, thus preserving its intention and maintaining system consistency. In this paper, we investigate the technical issues involved in preserving intentions of concurrent operations, explain the reasons why traditional serializationbased concurrency control strategies and existing operational transformation strategies failed to solve these problems, and propose a generic operation transformation scheme for intention preservation and consistency maintenance in real-time cooperative editing systems. The proposed scheme has been implemented in an Internetbased proto...

The total and causal ordering of group operations in distributed systems is at the core of solutions to many problems in distributed computing. Existing approaches ore based on either a centralized coordinator to assign a sequence number for each operation or on a distributed two-phase protocol to determine the total ordering number. This paper proposes an efficient distributed single-phase protocol which determines the total ordering of group operations at the moment when operations are generated, without the need for a dedicated phase of determining the total ordering.

No abstract available.