Text Document

Consistency Maintenance Based on the Mark & Retrace Technique in Groupware Systems

Fulltext URI

Document type

Additional Information



Journal Title

Journal ISSN

Volume Title


Association for Computing Machinery


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).


Gu, Ning; Yang, Jiangming; Zhang, Qiwei (2005): Consistency Maintenance Based on the Mark & Retrace Technique in Groupware Systems. Proceedings of the 2005 ACM International Conference on Supporting Group Work. DOI: 10.1145/1099203.1099250. New York, NY, USA: Association for Computing Machinery. pp. 264–273. Sanibel Island, Florida, USA