A semi-transparent selective undo algorithm for multi-user collaborative editors

Multi-user collaborative editors are useful computer-aided tools to support human-to-human collaboration. For multi-user collaborative editors, selective undo is an essential utility enabling users to undo any editing operations at any time. Collaborative editors usually adopt operational transformation (OT) to address concurrency and consistency issues. However, it is still a great challenge to design an efficient and correct OT algorithm capable of handling both normal do operations and user-initiated undo operations because these two kinds of operations can interfere with each other in various forms. In this paper, we propose a semi-transparent selective undo algorithm that handles both do and undo in a unified framework, which separates the processing part of do operations from the processing part of undo operations. Formal proofs are provided to prove the proposed algorithm under the well-established criteria. Theoretical analysis and experimental evaluation are conducted to show that the proposed algorithm outperforms the prior OT-based selective undo algorithms.     

Context-Based Operational Transformation in Distributed Collaborative Editing Systems

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.     

A novel CRDT-based synchronization method for real-time collaborative CAD systems

CRDT (Conflict-free Replicated Data Type) has been proposed as an alternative synchronization mechanism for collaborative text editing systems in recent years. However, CRDT-based synchronization methods for collaborative systems with sophisticated objects, such as collaborative CAD (Co-CAD) systems, are rarely investigated in previous literatures. How well CRDT-based synchronization methods for Co-CAD systems could perform remains unknown. This paper presents a novel CRDT-based synchronization method to maintain eventual consistency for the feature-based CAD model. Firstly, three operation relations are defined as the dependency-conflict relation, the mutual exclusive relation and the compatible relation in context of the feature-based CAD systems. Secondly, a feature-based conflict detection mechanism is proposed to detect the three relations. Thirdly, a feature-based conflict resolution approach under the CRDT framework is presented to solve the conflicts. Fourthly, the time complexity and the space complexity are analyzed in theory. Finally, case studies of collaborative modeling procedures verify the correctness and feasibility of the proposed method.     

实时协同位图编辑系统中不一致性问题研究

实时协同编辑系统有着广泛的应用前景,然而其冲突性操作导致众多结果不一致,解决一致性问题已成为设计与实现实时协同系统的关键性问题。该文基于对分布式系统采用的各种并发控制和一致性维持模型的比较,分析协同编辑中的三种不一致性问题、一致性模型,并研究相应的解决技术,提出了一种新的基于复制结构的协同位图编辑系统一致性维持模型。     

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

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

基于色彩地址空间转换与多版本策略的复杂位图协同模型与一致性维护算法

调色编辑在现有位图协同模型下存在数据发送量大、编辑灵活性差、操作重叠易冲突、生成版本多、站点存储压力大等问题,针对这些问题提出了一种面向复杂位图的调色协同编辑模型。协同操作仅发送坐标与色彩变化量的协同操作,具有数据量小、多维编辑粒度、位置可重叠等特性;增加了时空关系的四维位图协同架构,只保存已编辑的像素点数据可减少数据存储量;采用空间转换的副本状态控制算法,通过回溯重构历史版本,可以确保协同操作总是在正确的副本状态上执行;根据当前状态与策略配置,动态生成分支版本的算法,可以解决此前模型分支版本过多的问题。最后,基于CCI（causality-preservation,convergence,intention-preservation）模型进行正确性推论,开发协同编辑器原型Co-Pixel,随机生成的操作集设计实验,对照Adobe Lightroom 模拟实际编辑行为。结果显示提出的模型可有效减少操作产生冲突,降低一致性维护过程中的算法开销,灵活调整用户执行意图维护工作的结果版本。     

基于多核的并行操作转换算法

操作转换算法是实时协同编辑系统首选的并发控制算法,它不仅能提供不受限的交互,而且维护分布式操作的意图一致性。然而随着操作数目的增多,操作的响应时间也会延长。结合多核多线程技术的发展,提出了第一个并行的操作转换算法,其能减少远程操作集成到本地站点的时间开销。对传统的串行算法进行了改造,使得具有计算依赖的过程能够并行化。实验结果表明,提出的算法相较于传统算法具有较大的优势,在处理较大操作历史的情况下依然能够保证操作合理的响应时间。     

一种基于用户兴趣局部相似性的推荐算法

协作过滤算法作为至今最成功的个性化推荐技术之一,被广泛应用于电子商务、个性化节目推荐等系统中。但传统的基于协作过滤的推荐系统一直受到系统的稀疏性、推荐精确度低等问题的困扰。提出了一种基于用户兴趣局部相似性的改进的协作推荐算法（CFUPS）,针对协作过滤算法中用户近邻的计算和项目评分的预测两关键步骤,基于用户间潜在的局部相似的兴趣,并结合项目资源属性和项目评分矩阵来预测项目评分,进而给用户推荐感兴趣的个性化资源,理论上在提高推荐精度、克服稀疏性问题上均有改善。同时实验表明,在极具稀疏性的数据集上,该算法的推荐精度较以往的协作过滤算法有明显提高。     

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

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

容错系统中文件状态的保存与恢复算法

在机群计算环境中实现容错是人们日益关心的热点。许多著名的机群计算环境都使用检查点实现了容错的功能。但目前的检查点算法在使程序卷回执行的同时，不能相应地恢复文件系统的状态，因而对应用程序访问文件系统有较多的限制。本文在原子操作和并发控制的基础上，提出了能够恢复文件系统状态的ＳＣＲ算法，进一步发展了文件系统可恢复性的概念，ＳＣＲ算法与检查点机制结合使用，便可支持分布式应用程序在容错运行时对文件系统的任     

基于对象的Any Undo策略

Undo是基于对象的协同图形编辑系统的重要功能,可用于误操作的恢复。Undo的实现极具挑战性,因为分布协同环境下操作具有并发性,Undo的实现与一致性维护密切相关。提出的基于对象的Any Undo策略从操作语意的角度探讨了Undo操作的一致性维护,并给出了具体的实现机制。给出的支持机制都得到了实例证明,其可行性也在原型系统CoDraftPaint中得到初步验证。     

An approximation algorithm for box abstraction of transition systems on real state spaces

Predicate abstraction is a powerful technique for extracting finite-state models from infinite-state systems such as computer software, and is applied to verification of safety properties. Predicate abstraction is also applied to verification of dynamical systems on real state spaces such as hybrid dynamical systems. In this paper, we propose a fast algorithm for computing entire abstract state spaces of transition systems on real state spaces. The method is based on the box abstraction of state spaces, and requires a relatively smaller number of reachability checks and Boolean operations. We also propose a fast method for computing the set of boxes that intersect a given convex polyhedron. This computation is a part of the proposed state-space generation algorithm. Effectiveness of the algorithm is evaluated by the computation time and by the difference of the approximated state space from the exact state space.     

实时协同设计系统中同步过程的研究

作为一类支持人机交互的分布式系统,实时协同设计系统允许多个用户通过网络同步的对同一文档进行编辑.实时性、分布式、用户操作无限制是该系统的3个重要要求,但由于用户的同步操作和网络传输延迟的存在,协同过程中容易产生各种不同步的现象.对由于站点迟到或者非正常退出协同设计系统而引起的同步性问题进行了研究,提出了同步过程,包括主控站点发送同步队列、状态矢量轮询、缺少操作补齐等步骤,解决了站点迟到或非正常退出系统而引起的同步性问题.     

Smart devices and spaces for pervasive computing

Applications and services for pervasive computing have been dramatically grown and have contributed extensively to our daily experiences in recent years. Smart systems, devices, and spaces are proactive for ubiquitous and pervasive computing. Smart information technology (IT) is also an outcome of the state of the art and novel mobile and ubiquitous computing technologies that include highly capable handheld device, pervasive and personal device, etc. This special issue will be a trigger for further related research and technology improvements in pervasive and ubiquitous computing using smart devices and services. This special issue called for original papers describing the latest developments, trends, and solutions of smart devices and spaces for pervasive computing including real-time operating systems (OS), tiny OS and middleware supports, mobile system performance, trustworthy Internet and communications, agents and mobile and pervasive services, among others. In particular, this special issue focuses on a remote control and media-sharing system, flash storage-based smart system, heterogeneous mobile OS, and prediction and auto-execution system for pervasive computing.     

协同图形编辑系统中并发操作冲突检测的研究

实时协同设计是CSCW应用的重要领域。实时协同设计过程实际上就是并发冲突产生和消解的过程。本文描述协同图形编辑系统中多对象之间的冲突相关定义,提出一种判别并发操作冲突的关联对象冲突检测策略,设计实现相应的冲突检测算法,最后对算法的可行性进行分析。     

Development of Situation-Aware Applications in Services and Cloud Computing Environments

Computing paradigms have evolved towards integrating small and personal computing devices with large-scale and resource-sharing computing infrastructures, such as services and cloud computing (SCC) platforms during the past two decades to provide users anytime, anywhere computing capability with more flexibility, richer computing resources, more cost-effectiveness, lower risks of system failures, and less management and maintenance effort. Situation-aware (SA) applications in SCC environments have the capability to adapt SCC systems to situation changes to facilitate better human-computer interactions and continuous system availability, and satisfactory quality-of-service (QoS) for the applications. Mission-critical applications in many domains usually require situation awareness, and have started to incorporate it in SCC platforms due to the need of rapidly reconfiguring and integrating systems owned and operated by various organizations for sharing information and coordinating operations. In this paper, the concepts and characteristics of SCC and situation awareness (SAW), and the challenges and current state of the art in developing SA applications in SCC environments are discussed. Our research in this area, including the development of Adaptable Situation-aware Secure Service-based (AS3) systems and Adaptive Service-Based Systems (ASBS) with QoS Monitoring and Adaptation (M/A), is presented. Future research in this area is discussed.     

CRDT协议的TLA+描述与验证

无冲突复制数据类型（conflict-free replicated data types，简称CRDT）是一种封装了冲突消解策略的分布式复制数据类型，它能保证分布式系统中副本节点间的强最终一致性，即执行了相同更新操作的副本节点具有相同的状态.CRDT协议设计精巧，不易保证其正确性.旨在采用模型检验技术验证一系列CRDT协议的正确性.具体而言，构建了一个可复用的CRDT协议描述与验证框架，包括网络通信层、协议接口层、具体协议层与规约层.网络通信层描述副本节点之间的通信模型，实现了多种类型的通信网络.协议接口层为已知的CRDT协议（分为基于操作的协议与基于状态的协议）提供了统一的接口.在具体协议层，用户可以根据协议的需求选用合适的底层通信网络.规约层则描述了所有CRDT协议都需要满足的强最终一致性与最终可见性（所有的更新操作最终都会被所有的副本节点接收并处理）.使用TLA+形式化规约语言实现了该框架，然后以Add-Wins Set复制数据类型为例，展示了如何使用框架描述具体协议，并使用TLC模型检验工具验证协议的正确性.     

An efficient and secure approach for a cloud collaborative editing

The demand for cloud-based collaborative editing service is rising along with the tremendously increased popularity in cloud computing. In the cloud-based collaborative editing environment, the data are stored in the cloud and able to be accessed from everywhere through every compatible device with the Internet. The information is shared with every accredited user in a group. In other words, multiple authorized users of the group are able to work on the same document and edit the document collaboratively and synchronously online. Meanwhile, during the whole collaborative editing process, the encryption technique is eventually applied to protect and secure the data. The encryption for the collaborative editing, however, could require much time to operate. To elevate the efficiency of the encryption, this study first analyzes the text editing in the collaborative service and presents a framework of the Red–Black tree, named as rbTree-Doc. The rbTree-Doc can reduce the amount of data to be encrypted. Although the trade-off for creating the Red–Black tree introduces extra cost, the experimental results of using rbTree-Doc in text editing operations, such as insertion and removal, show improved efficiency compared with other whole-document encryption strategy. Using rbTree-Doc, the efficiency is improved by 31.04% compared to that 3DES encryption is applied and by 23.94% compared to that AES encryption is applied.     

面向图形对象的协同编辑系统的并发操作冲突检测

协同者的并发操作的冲突是引发不一致的主要原因，因而并发操作的冲突判别则是系统开发的一个重要的方面．本文分析了基于图形对象的协同编辑系统的并发操作冲突的机理，给出了操作命令的一般表示方法，提出一个通用的基于该描述的冲突判别推理方法，并基于不同领域知识将该方法用于二维绘图系统和三维产品特征建模系统中的并发操作冲突的分析，实验结果表明该方法是可以适合不同协同系统的通用方法．     

Pervasive computing at scale: Transforming the state of the art

The remarkable recent progress in computing power, sensors and embedded devices, smart phones, wireless communications and networking technologies, combined with emerging data mining techniques, cloud computing and social networking paradigms has enabled us to create pervasive computing systems and services with diverse applications and global accessibility. In this paper, we assess the current state of the art of pervasive computing at scale (PeCS) and look ahead to future directions the field can pursue together with challenges it will need to overcome.