协同组编辑中基于地址空间转换的一致性维护方法  

Consistency Maintenance Based on the Address Space Transformation Technique in Group Editors

作　　者：顾宁[1] 杨江明[1] 张琦炜[1] 

机构地区：[1]复旦大学计算机与信息技术系,上海200433

出　　处：《计算机学报》2007年第5期763-774,共12页Chinese Journal of Computers

基　　金：国家自然科学基金(90612008);国家"九七三"重点基础研究发展规划项目基金(2005CB321905);上海市科委基础研究重点项目基金(05JC14006)资助.

摘　　要：组编辑中的一致性维护问题在CSCW中是一个重要的技术挑战.文章介绍了一个基于地址空间转换的方法.对于并发操作,地址空间转换方法将文档的地址空间回溯到操作产生时的状态,操作可以直接在这个地址空间下得到执行.与操作转换方法相比,地址空间转换方法仅仅需要决定新操作的位置,避免了操作转换过程中操作间相对位置信息的丢失,不仅可以满足CCI模型,而且可以对Undo操作提供更好的支持.通过证明每个站点字符节点间维持一致的顺序,对应字符节点拥有相同的标记,文中给出了算法对于一致性维护的证明.同时,操作执行的平摊代价可以优化到O(logn).Consistency maintenance in group editors is a major technical challenge. This paper presents an address space transformation method. To deal with the concurrent operations, address space transformation technique retraces the document＇s address space to the state at the time of the operation＇s generation. Then the operation can be executed directly in this address space. Compared with the Operation Transformation technique, the address space transformation technique method only needs to decide the position of new operation and thus avoids the lost of relative position （left or right） among operations in the transformation process. It can not only satisfy the CCI model but also provide a better support for Undo. This paper provides the proof of the algorithm＇s correctness of consistency maintenance, in which both orders of character nodes and marks of each node at all sites are kept consistently. Furthermore, the amortized efficiency can reach O（logn）

关 键 词：计算机支持的协同工作 并发控制 一致性维护 组编辑 地址空间转换 标记回溯 

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