GIT-CERCS-09-07
Qinyi Wu, Calton Pu,
Consistency in Real-time Collaborative Editing Systems Based on Partial Persistent Sequences
In real-time collaborative editing systems, users create a shared document by issuing insert, delete, and undo operations on their local replica anytime and anywhere. Data consistency issues arise due to concurrent editing conflicts. Traditional consistency models put restrictions on editing operations updating different portions of a shared document, which is unnecessary for many editing scenarios, and cause their view synchronization strategies to become less efficient. To address these problems, we propose a new data consistency model that preserves convergence and synchronizes editing operations only when they access overlapped or contiguous characters. Our view synchronization strategy is implemented by a novel data structure--partial persistent sequence. A partial persistent sequence is an ordered set of items indexed by persistent and unique position identifiers. It captures data dependencies of editing operations and encodes them in a way that they can be correctly executed on any document replica. As a result, a simple and efficient view synchronization strategy can be implemented.