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

发布时间：2018-10-14 13:36

【摘要】：有别于传统分布式系统,实时协同编辑系统强调自然和谐的人人交互和人机交互,允许不同地点的协同用户同时编辑同一共享对象.为了给协同用户提供良好的响应性,实时协同编辑系统有必要采用全复制式体系结构,但又给共享对象的一致性维护问题带来巨大挑战,这一直是协同计算学科的研究热点.近年研究重点逐步从结果一致性发展到操作意图一致性.该文以操作意图一致性为主线,对支持操作意图一致性的实时协同编辑算法进行深入和全面的比较、分析和总结.首先,以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个关键方面对实时协同编辑算法进行归纳和对比.最后对全文小结,并指出为了进一步发展实时协同编辑系统,未来还需要在优先级策略、算法伸缩性、复杂操作语义类型、粗粒度操作对象以及选择性撤销机制等方面深入开展一些研究工作.
[Abstract]:Unlike traditional distributed systems, real-time collaborative editing systems emphasize the natural harmony of human interaction and human-computer interaction, allowing co-users in different locations to edit the same shared object at the same time. In order to provide good response to cooperative users, it is necessary for real-time collaborative editing system to adopt full-replication architecture, but it also brings a great challenge to the consistency maintenance of shared objects, which has been a hot research topic in the field of collaborative computing. In recent years, the focus of research has gradually developed from consistency of results to consistency of operational intent. Based on the consistency of operation intention, this paper makes a deep and comprehensive comparison, analysis and summary of the real-time cooperative editing algorithm which supports the consistency of operation intention. Firstly, the concepts of causality, simple concurrency and partial concurrency relation of cooperative editing system are sorted out with Lamport event partial order relation as the starting point. At the same time, the classification of the total order relation, the total order of the operation and the total order of the operation object in the real-time cooperative editing system are given. Based on the analysis of the total order relation and priority, the, CCI (Causality-preservation,Convergence,Intention-preservation) model and the CA (Causalitypreservation,Admissibility) model of three kinds of consistency models (: CC (Causality-preservation,Convergence) and CA (Causalitypreservation,Admissibility) in real-time collaborative editing system are described. In particular, according to the classification of causality consistency, result consistency and operational intention consistency, the maintenance road map of operational intent consistency is given. Then, the research progress and current situation of all kinds of real-time cooperative editing algorithms, including OT (Operational Transformation) algorithm, AST (Address Space Transformation) algorithm and CRDT (Commutative Replicated Data Type) algorithm, are reviewed respectively. Furthermore, the basic principle and implementation framework of all kinds of algorithms for consistency of operation intention are given, and the typical algorithms are analyzed in detail based on a typical collaborative work scenario and an example. Then, this paper sums up and compares the real-time cooperative editing algorithm from four key aspects: consistency of operation intention, typical algorithm supporting consistency of operation intention, operation conversion function and algorithm time complexity. Finally, it is pointed out that in order to further develop the real-time cooperative editing system, we also need priority strategy, algorithm scalability, and complex operation semantic types in the future. Some researches on coarse-grained operation object and selective revocation mechanism have been carried out.
【作者单位】：武汉大学软件工程国家重点实验室武汉大学计算机学院海军工程大学计算机工程系
【基金】：国家自然科学基金(61472289,61502353) 国家重点研发计划(2016YFC0106305)资助
【分类号】：TP301.6

【相似文献】