支持操作意图一致性的实时协同编辑算法综述  

Survey of Real-Time Collaborative Editing Algorithms Supporting Operation Intention Consistency

作　　者：何发智[1,2] 吕晓[2,3] 蔡维纬[2] 程媛[2] HE Fa-Zhi;Lü Xiao;CAI Wei-Wei;CHENG Yuan(State Key Laboratory of Software Engineering,Wuhan University,Wuhan 430072;School of Computer Science,Wuhan University,Wuhan 430072;College of Computer Engineering,Naval University of Engineering,Wuhan 430033)

机构地区：[1]武汉大学软件工程国家重点实验室,武汉430072 [2]武汉大学计算机学院,武汉430072 [3]海军工程大学计算机工程系,武汉430033

出　　处：《计算机学报》2018年第4期840-867,共28页Chinese Journal of Computers

基　　金：国家自然科学基金(61472289;61502353);国家重点研发计划(2016YFC0106305)资助

摘　　要：有别于传统分布式系统,实时协同编辑系统强调自然和谐的人人交互和人机交互,允许不同地点的协同用户同时编辑同一共享对象.为了给协同用户提供良好的响应性,实时协同编辑系统有必要采用全复制式体系结构,但又给共享对象的一致性维护问题带来巨大挑战,这一直是协同计算学科的研究热点.近年研究重点逐步从结果一致性发展到操作意图一致性.该文以操作意图一致性为主线,对支持操作意图一致性的实时协同编辑算法进行深入和全面的比较、分析和总结.首先,以Lamport事件偏序关系为起点,对协同编辑系统的因果关系、简单并发关系和偏并发关系概念进行整理.同时,给出实时协同编辑系统中全序关系的分类,操作的全序和操作对象的全序.在对全序关系和优先级进行剖析的基础上,阐述了实时协同编辑系统中的三类一致性模型:CC(Causality-preservation,Convergence)模型、CCI(Causality-preservation,Convergence,Intention-preservation)模型和CA(Causalitypreservation,Admissibility)模型.特别地,文中按照因果一致性、结果一致性和操作意图一致性的分类,给出操作意图一致性的维护路线图.然后,分别综述了各类实时协同编辑算法的研究进展和现状,包括OT(Operational Transformation)算法、AST(Address Space Transformation)算法和CRDT(Commutative Replicated Data Type)算法.进一步,文中给出了各类操作意图一致性算法的基本原理和执行框架,并基于一个代表性协同工作场景和算例对典型算法进行详细解析.接下来,文中从操作意图一致性、支持操作意图一致性的典型算法、操作转换函数和算法时间复杂度这4个关键方面对实时协同编辑算法进行归纳和对比.最后对全文小结,并指出为了进一步发展实时协同编辑系统,未来还需要在优先级策略、算法伸缩性、复杂操作语义类型、粗粒度操作对象以及选择性撤销机�Different from traditional distributed systems,real-time collaborative editing systems support natural and harmonious human to computer interactions and human to human interactions.Real-time collaborative editing systems allow multiple geographically dispersed collaborative users to view and edit the shared object over computer networks.In order to provide high responsiveness for collaborative users,real-time collaborative editing systems adopt the fully-replicated architecture,which brings the great challenge for consistency maintenance of the shared object.Consistency maintenance is one of the most essential challenges in the design and implementation of real-time collaborative editing systems,which has been a continuous hot topic in the field of collaborative computing for over 25 years for over past 25 years.In recent years,the research focus has gradually moved from result consistency to operation intention consistency.In this paper,from the perspective of operation intention consistency,we give a deep and comprehensive comparison,analysis and summary of existing real-time collaborative editing algorithms.First of all,based on Lamport’s partial ordering relation of events,we discuss and generalize the basic concepts and terminologies of the causal ordering relation,the simple concurrent relation and the partial concurrent relation.Then,we give the classification of the total ordering relation,such as the total ordering relation of operations and the total ordering relation of operation objects.Moreover,the total ordering relation of operations is further categorized as the centered total ordering relation or the distributed total ordering relation.After analyzing the total ordering relation and the priority,we investigate three types of consistency models,including CC(Causality-preservation,Convergence)model,CCI(Causality-preservation,Convergence,Intention-preservation)model and CA(Causality-preservation,Admissibility)model.Specially,we propose a road map to maintain operation intention consistency accordi

关 键 词：实时协同编辑 一致性模型 操作意图一致性 操作转换 可交换的复制数据类型 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]