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

• 作者: 何发智 吕晓 程媛 蔡维纬
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 实时协同编辑 一致性模型 操作意图一致性 操作转换 可交换的复制数据类型
• 年，卷（期）: 2018,（4）
• 所属期刊栏目: 算法与智能
• 页码范围: 840-867
• 页数: 28页
• 分类号: TP311
• 字数: 27171字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2018.00840

摘要

有别于传统分布式系统,实时协同编辑系统强调自然和谐的人人交互和人机交互,允许不同地点的协同用户同时编辑同一共享对象.为了给协同用户提供良好的响应性,实时协同编辑系统有必要采用全复制式体系结构,但又给共享对象的一致性维护问题带来巨大挑战,这一直是协同计算学科的研究热点.近年研究重点逐步从结果一致性发展到操作意图一致性.该文以操作意图一致性为主线,对支持操作意图一致性的实时协同编辑算法进行深入和全面的比较、分析和总结.首先,以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个关键方面对实时协同编辑算法进行归纳和对比.最后对全文小结,并指出为了进一步发展实时协同编辑系统,未来还需要在优先级策略、算法伸缩性、复杂操作语义类型、粗粒度操作对象以及选择性撤销机制等方面深入开展一些研究工作.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	程媛	武汉大学计算机学院	11	47	4.0	6.0
2	何发智	武汉大学软件工程国家重点实验室	51	539	10.0	22.0
6	蔡维纬	武汉大学计算机学院	3	10	2.0	3.0
7	吕晓	武汉大学计算机学院	3	10	2.0	3.0