Consistency maintenance based on the mark & retrace technique in groupware systems
Consistency maintenance based on the mark & retrace technique in groupware systems
复制标题
DOI：
10.1145/1099203.1099250
复制
发表时间：
2005-11
期刊：
影响因子：
--
通讯作者：
Ning Gu;Jiang-Ming Yang;Qiwei Zhang
中科院分区：
文献类型：
--
作者：
Ning Gu;Jiang-Ming Yang;Qiwei Zhang
复制结构被广泛用于隐藏网络延迟。然而，在完全复制的体系结构中，一致性维护是一个主要的技术挑战。本文提出了一种在复制群件系统中基于标记回溯的方法。与操作转换技术相比，它不调整操作的位置，而是将文档的地址空间追溯到操作生成时的状态。然后操作可以直接在这个地址空间中执行。Mark & Retrace方法不仅可以达到一致性维护的目的，而且可以为撤销提供更好的支持。本文证明了该算法的一致性维护的正确性，即所有站点的特征节点的顺序和每个节点的标记都保持一致。而且，摊销效率可以达到O（logn）.
Replicated architecture is widely used for concealing network delay. However, consistency maintenance in fully replicated architecture is a major technical challenge. In this paper, we report a Mark & Retrace based method in replicated groupware systems. Compared with the Operation Transformation technique, it does not adjust the operation's position but 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. Mark & Retrace method can not only achieve the same goal of consistency maintenance but also provide a better support for Undo. This paper provides the proof of the algorithm's correctness of consistency maintenance, in which both the orders of character nodes and marks of each node at all sites are kept consistent. Furthermore, the amortized efficiency can reach O(log n).