A Multi-Versioning Scheme for Intention Preservation in Collaborative Editing Systems*

Although the multi-version approach to consistency maintenance has been widely discussed and implemented in database systems, version control systems, and asynchronous groupware systems, its potential in real-time groupware systems is largely unexplored. Intention preservation is an important aspect of consistency maintenance in real-time collaborative editing systems, where multiple users cooperate with each other by concurrently editing the same document. The multi-version approach is supposed to be able to preserve individual users’ concurrent conflicting intentions. In this article, we propose a new multi-versioning scheme that can preserve not only concurrent conflicting intentions but also contextual intentions while achieving convergence of the document under editing. By extending an existing multi-versioning scheme to a general one that specifies the conditions for convergence, we decouple the discussion of convergence from that of intention preservation. By constraining the general scheme, we arrive at the novel scheme that guarantees to preserve users’ intentions. The correctness of the scheme has been formally verified. The design of an algorithm for consistent version composition and identification has been discussed in detail.     

Optional and responsive fine-grain locking in Internet-based collaborative systems

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.     

协同图形图像编辑系统中对象锁与区域锁的并行

在分布式协同编辑系统中,为了防止并行操作中出现冲突,常常用到加锁的机制.分布式协同图形图像编辑系统是协同系统中一个特殊的类,因此有特殊的加锁方式.本文提出一种新的不但能够给对象加锁,而且能够给区域加锁的锁机制.在这种锁机制下,用户可以自由地选择给一个图案对象加锁或者给一个工作区域加锁.这是一种细粒度和粗粒度的结合,既有利于减少加锁时系统的负载,又有利于方便用户的操作.这个机制已经应用在我们的CoDesign系统.     

基于多版本的对象标识与垃圾收集算法

研究与设计全复制结构的实时协同编辑系统的关键问题之一是多个复制数据视图的一致性 ,其中操作意愿保证是一致性维护的根本 .分析了基于多版本的对象标识问题 ,提出一个对象标识模型 ,并针对多版本环境对冲突定义进行了修改 ;采用操作列表 OL取代历史缓冲区 HB,维护对象版本上执行过的所有操作 ,并进一步分析了操作列表的垃圾收集算法 .本文提出的算法都得到实例验证     

基于图形对象的一致性维护问题的研究

针对实时协同图形编辑系统中一致性维护关键问题,提出了一种基于图形对象的并发控制算法。该算法扩展了面向文本编辑的分布式操作转换dOPT算法,满足图形对象属性级上数据一致性维护,同时通过预定义图形对象间的关联关系和位置属性约束规则,进行操作语义维护管理,使得实时协同图形编辑系统的一致性维护更为有效和完备。     

A transaction management framework for collaborative engineering

This paper discusses the various novel functionalities of a transaction management system for collaborative engineering applications. These features include grouped and shared transactions, dynamic database partitioning, communicative locking, dependency maintenance, update notification schemes, and version management of data configurations. It also establishes protocols for data consistency maintenance on the basis of application semantics and encapsulation of nonserializable data sharing in local databases rather than by the notion of global database consistency. Finally, it presents strategies for implementing these features using a commercial object oriented database management system (OODBMS) environment (ONTOS).     

一种新的多版本增创算法

现有的对象复制技术是实时协同图形编辑系统中符合一致性模型的并发控制策略,但难以解决非几何属性以及三维绘图系统中的并发冲突情况.介绍了一个全新的一致性维护模型——基于版本复制的多版本技术,当并发操作发生冲突时,利用简化规则从目标版本派生出叶子物理版本,分别应用冲突操作到不同的叶子版本,有效地解决了非调和冲突操作的意愿保证.通过研究多版本技术的相关支持算法,在算法MOVIC的基础上,从各个冲突操作的最大共同相容操作着手,提出了基于相容冲突组的快速多版本增创算法FMVIC(Fast Multiple Versions Incremental Creation),减少了相容操作的比较次数,缩小了去冗余操作的范围.     

Extending WebDAV With Multiple-Granularity Locking

In distributed Web authoring, shared documents can be accessed concurrently by multiple authors who must be coordinated to avoid conflicts. The current Web standard for distributed authoring and versioning uses a two-phase locking to coordinate concurrent access. As the degree to which authors work concurrently may vary though among cooperative sessions, it is necessary to extend the aforementioned standard so as to support a multitude of lock granularity levels. In this paper, we first examine related protocols from the database literature, and then, we comment on their suitability for distributed authoring in the World Wide Web. Our main contribution is a multiple-granularity locking protocol, in which the locks are optional and they convey the meanings of access mode, locking scope, and locking effect. This protocol allows synchronous collaboration by guaranteeing a conflict-free environment and avoiding update loss while it also supports version control. Specifically, by identifying and timestamping object versions, the protocol preserves author intention and operation causality, which were possible so far with operational transformation only. The protocol's efficiency, finally, is demonstrated by a real test with human users and evaluated with simulation experiments, which reveal significant advantages over other protocols of this kind.     

Modular synchronization in distributed, multiversion databases:version control and concurrency control

A version control mechanism is proposed that enhances the modularity and extensibility of multiversion concurrency control algorithms. The multiversion algorithms are decoupled into two components: version control and concurrency control. This permits modular development of multiversion protocols and simplifies the task of proving the correctness of these protocols. A set of procedures for version control is described that defines the interface with the version control component. It is shown that the same interface can be used by the database actions of both two-phase locking and time-stamp concurrency control protocols to access multiversion data. An interesting feature of the framework is that the execution of read-only transactions becomes completely independent of the underlying concurrency control implementation. Unlike other multiversion algorithms, read-only transactions in this scheme do not modify any version-related information, and therefore do not interfere with the execution of read-write transactions. The extension of the multiversion algorithms to a distributed environment becomes very simple     

Collaborative telemedicine for interactive multiuser segmentation of volumetric medical images

Telemedicine has evolved rapidly in recent years to enable unprecedented access to digital medical data, such as with networked image distribution/sharing and online (distant) collaborative diagnosis, largely due to the advances in telecommunication and multimedia technologies. However, interactive collaboration systems which control editing of an object among multiple users are often limited to a simple “locking” mechanism based on a conventional client/server architecture, where only one user edits the object which is located in a specific server, while all other users become viewers. Such systems fail to provide the needs of a modern day telemedicine applications that demand simultaneous editing of the medical data distributed in diverse local sites. In this study, we introduce a novel system for telemedicine applications, with its application to an interactive segmentation of volumetric medical images. We innovate by proposing a collaborative mechanism with a scalable data sharing architecture which makes users interactively edit on a single shared image scattered in local sites, thus enabling collaborative editing for, e.g., collaborative diagnosis, teaching, and training. We demonstrate our collaborative telemedicine mechanism with a prototype image editing system developed and evaluated with a user case study. Our result suggests that the ability for collaborative editing in a telemedicine context can be of great benefit and hold promising potential for further research.     

Concurrency of operations on B-trees

Summary Concurrent operations on B-trees pose the problem of insuring that each operation can be carried out without interfering with other operations being performed simultaneously by other users. This problem can become critical if these structures are being used to support access paths, like indexes, to data base systems. In this case, serializing access to one of these indexes can create an unacceptable bottleneck for the entire system. Thus, there is a need for locking protocols that can assure integrity for each access while at the same time providing a maximum possible degree of concurrency. Another feature required from these protocols is that they be deadlock free, since the cost to resolve a deadlock may be high.Recently, there has been some questioning on whether B-tree structures can support concurrent operations. In this paper, we examine the problem of concurrent access to B-trees. We present a deadlock free solution which can be tuned to specific requirements. An analysis is presented which allows the selection of parameters so as to satisfy these requirements.The solution presented here uses simple locking protocols. Thus, we conclude that B-trees can be used advantageously in a multi-user environment.     

Protecting the consistency of workflow applications in collaborative development environments

Collaborative development environments allow a group of users to view and edit a shared item from geographically dispersed sites. Consistency maintenance in the face of concurrent accesses to shared entities is one of the core issues in the design of these systems. The paper introduces a lock based solution and three different algorithms that enable controlled, concurrent access to workflows for multiple application developers. Collaborative development of workflow applications promises better outcome in shorter time. The described method ensures that collaborators cannot break the consistency criteria of workflows by adding cycles or invalid edges to the graphs. A formal analysis of the three graph locking algorithms is also provided, focusing on the number of users who are allowed to edit a single workflow simultaneously. Based on the findings, a more powerful fourth graph locking algorithm is defined.     

基于锁定机制的电网GIS多用户协同编辑研究

针对电网GIS中多用户协同编辑的现实需要,在确保编辑数据一致性和正确性的基础上,结合任务划分和版本管理技术,提出了基于锁定机制的电网GIS多用户协同编辑.首先分析了协同编辑的体系结构和编辑流程,然后描述了协同编辑中锁定机制的实现算法、锁定流程以及客户端之间数据同步,最后结合实际项目需求构建原型系统,对基于锁定机制的电网GIS多用户协同编辑进行了验证.     

基于相对位置的分布式实时协同编辑乐观锁并发控制算法

实时分布式协同编辑系统是计算机支持的协同工作的典型应用系统,不少学者对其进行了大量的研究,其难点是协作编辑的一致性、实时性和无约束性。因此,并发控制始终是它的研究热点,目前已提出的协同编辑的并发控制算法有:传统的加锁法、tickle锁、floor控制、可逆执行(Undo/Redo)和操作转换等。传统的加锁法最突出的优点是设计和实现较为简单,能保证具体上下文的语义完整性,但是在分布式协同编辑中无法保证加锁位置的一致性。tickle锁方法适用于分节加锁的实时分布式协同编辑的并发控制,然而无法提供多个编辑者对节内的同时编辑。JCE中的协同编辑采用了floor控制方法,每个协作编者只有获得floor才能进行     

相对位置乐观锁机制及在协同编辑中的应用

为了满足实时协同编辑对快速响应、无约束协作的要求，提出了一种基于相对位置的乐观锁机制并发控制算法．该算法引入了编辑锁和读锁，并对加锁的起始位置和编辑操作位置用相对位置表示，当锁申请成功将写进锁表或者操作发送到各协作结点时，再把它们转换成绝对位置，加锁的粒度可根据编者的需要任意选择，编者在加锁请求获得确认前，可预先进行编辑操作．应用实例表明：该算法既保证了数据维护的一致性，又具有快速响应性．     

Transaction processing in mobile, heterogeneous database systems

As technological advances are made in software and hardware, the feasibility of accessing information "any time, anywhere" is becoming a reality. Furthermore, the diversity and amount of information available to a given user is increasing at a rapid rate. In a mobile computing environment, a potentially large number of users may simultaneously access the global data; therefore, there is a need to provide a means to allow concurrent management of transactions. Current multidatabase concurrency control schemes do not address the limited bandwidth and frequent disconnection associated with wireless networks. This paper proposes a new hierarchical concurrency control algorithm. The proposed concurrency control algorithm, v-lock, uses global locking tables created with semantic information contained within the hierarchy. The locking tables are used to serialize global transactions, detect and remove global deadlocks. Additionally, data replication, at the mobile unit, is used to limit the effects of the restrictions imposed by a mobile environment. The replicated data provides additional availability in case of a weak connection or disconnection. Current research has concentrated on page and file-based caching or replication schemes to address the availability and consistency issues in a mobile environment. In a mobile, multidatabase environment, local autonomy restrictions prevent the use of a page or file-based data replication scheme. This paper proposes a new data replication scheme to address the limited bandwidth and local autonomy restrictions. Queries and the associated data are cached at the mobile unit as a complete object. Consistency is maintained by using a parity-based invalidation scheme. A simple prefetching scheme is used in conjunction with caching to further improve the effectiveness of the proposed scheme. Finally, a simulator was developed to evaluate the performance of the proposed algorithms. The simulation results are presented and discussed.     

多版本技术中的对象标识及其压缩

协同编辑系统支持不同地域的协作者通过网络同时地编辑同一个文本或图形对象,其研究具有挑战性.介绍了协同图形编辑中的多版本技术,重点讨论了对象标识及其策略,给出所存在的问题.提出了一个全面的对象标识方案.该方案解决了以往方案不能处理具有依赖关系的操作和相同关系的操作的对象标识和系统维护问题.同时,随着编辑的进行和冲突的产生,对象标识会急剧膨胀,影响系统处理的效率,分析了对象标识压缩的规则,给出一个对象标识压缩方法,并对其有效性进行了分析.实例分析和实验结果表明,所提出的对象标识及其压缩方案提高了系统的效率.     

一个完全分布式的可追踪门限-多重签名方案

门限-多重签名是结合了门限签名和多重签名的特点而产生的新的签名,这种签名体制既可以使多于门限t个以上的签名者产生合法的签名,同时又具有签名者可追踪的特性。提出了一个完全分布式的可追踪门限-多重签名,使得必须有t个或t个以上的诚实组成员合作才可能产生一个门限-多重签名,并且可以公开验证签名中每个签名成员的身份。该门限-多重签名方案是基于可证明安全的单签名变体改进的,具有较高的安全性。在协议的整个过程中利用了已证明安全的签名和签密技术,保障了协议过程的安全性及可验证性。方案本身及协议的安全性和高效性使得此方案具有较高的实用性。     

Doubly-striped disk mirroring: Reliable storage for video servers

Disk striping is essential in Video-On-Demand servers to allow concurrent access for a large number of users to the same copy of a video object. On the other hand, disk striping makes the system more vulnerable to component failures. We propose a replication scheme for video content and an associated I/O scheduling algorithm that enables the system to tolerate a component failure. The scheme, called doubly-striped mirrors, compares favorably to other approaches for implementing redundancy such as RAID in terms of cost, bandwidth efficiency, buffer usage and system availability.