协同图形编辑系统中的并发控制研究

论文摘要

分布环境下的协同图形编辑系统OCES（Object-based Cooperative graphics Editing System）是计算机支持的协同工作CSCW（Computer Supported Cooperative Work）中一个十分活跃的研究方向。为了支持自然、自由的协同编辑，OCES具有分布的用户群、实时响应、协作透明性和无约束性等特征，为此大部分系统采用全复制的体系结构。研究与开发复制式体系结构下的OCES的关键问题之一是多个复制数据视图的一致性，这也是本文研究的核心。本文首先介绍了协同编辑系统的一致性维护技术。围绕协同编辑系统的一致性模型，具体讨论了一致性模型的三个一致性特征及可行的保证技术，并考察了一些典型的一致性维护策略。然后介绍了基于对象复制的多版本策略，在分析其多版本增创算法性能缺陷的基础上给出了基于冲突组概念的新的分布式多版本递增创建算法，减少了相容操作的比较次数、避免了版本冗余问题，提高了算法的性能。随后介绍了基于版本复制的多版本策略，其解决了对象复制策略所不能克服的一些复杂问题。提出了改进的基于版本复制多版本策略，实现了操作的层次存储，最大程度上避免了同一个操作被存储在多个版本中，减少了系统的操作存储量。最后简要分析了版本间冲突操作的产生情况，提出了使用子树构造法来保证版本间冲突操作的执行意愿，并首次提出了广义最大冲突组的概念，给出了一个利用广义最大冲突组实现版本间冲突操作的分布式算法。原型系统CoWork从系统实现的角度论证了上述策略和算法的正确性。文中还简要分析了CoWork涉及的其它支持策略，以及CoWork的系统性能。

论文目录

• 插图索引
• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 分布环境下的协同编辑系统及其研究现状
• 1.3 本文主要工作及组织结构
• 第二章 协同编辑系统的一致性维护
• 2.1 传统的一致性维护技术
• 2.1.1 令牌机制
• 2.1.2 锁机制
• 2.1.3 其它机制
• 2.2 一致性模型
• 2.3 因果关系和收敛的维护
• 2.3.1 逻辑时间
• 2.3.2 因果关系和收敛
• 2.4 操作转换技术
• 2.4.1 操作转换的基本思想
• 2.4.2 典型的操作转换算法
• 2.4.2.1 GROVE
• 2.4.2.2 REDUCE
• 2.4.2.3 Jupiter
• 2.4.2.4 其它操作转换算法
• 2.5 基于对象复制的多版本技术
• 2.6 基于版本复制的多版本技术
• 2.7 一致性维护的其它研究思路
• 2.7.1 以用户为中心的一致性模型
• 2.7.2 语义一致特征
• 2.8 本章小结
• 第三章 基于对象复制的多版本技术
• 3.1 协同图形编辑系统中的操作及操作关系
• 3.2 对象复制技术
• 3.3 多版本策略
• 3.3.1 最大相容组集合
• 3.3.2 多版本动态增创算法MOVIC
• 3.3.3 实例描述
• 3.3.4 MOVIC算法性能分析
• 3.3.5 改进的新方法
• 3.4 新的多版本增创算法MVICC
• 3.4.1 相同操作问题
• 3.4.2 基于冲突组的分布式多版本递增创建算法
• 3.4.3 实例分析
• 3.4.4 MOVIC算法和MVICCC算法比较
• 3.4.5 模拟实验
• 3.5 本章小结
• 第四章 基于版本复制的多版本技术
• 4.1 与协同多版本技术相关的基本术语和概念
• 4.1.1 版本复制技术概念
• 4.1.2 冲突关系与相容关系
• 4.2 协同多版本技术的版本复制
• 4.3 改进的协同多版本技术
• 4.3.1 改进的多版本策略
• 4.3.2 实例分析及相关比较
• 4.4 改进的多版本技术中的相关问题
• 4.4.1 版本树的不一致问题
• 4.4.2 版本树优化选择
• 4.4.3 版本树的遍历
• 4.5 操作存储量的比较
• 4.5.1 模拟实验
• 4.6 多版本技术中的版本间冲突
• 4.6.1 版本间冲突操作的意愿保证
• 4.6.2 版本间冲突操作的实现
• 4.6.3 版本间冲突操作的实现算法
• 4.7 本章小结
• 第五章 支持协同图形编辑的原型系统CoWork
• 5.1 系统结构
• 5.2 会话管理
• 5.3 客户端的实现
• 5.3.1 客户端的协同感知策略
• 5.3.2 图形编辑器
• 5.3.3 系统实现
• 5.4 运行界面及分析
• 5.5 本章小结
• 结束语
• 参考文献
• 致谢
• 附录一 读研期间参与项目情况
• 附录二 读研期间发表论文情况