Consistency in Real-time Collaborative Editing Systems Based on Partial Persistent Sequences

In real-time collaborative editing systems, users create a \nshared document by issuing insert, delete, and undo operations \non their local replica anytime and anywhere. Data \nconsistency issues arise due to concurrent editing conflicts. \nTraditional consistency models put restrictions on editing \noperations updating different portions of a shared document, \nwhich is unnecessary for many editing scenarios, and \ncause their view synchronization strategies to become less \nefficient. To address these problems, we propose a new data \nconsistency model that preserves convergence and synchronizes \nediting operations only when they access overlapped \nor contiguous characters. Our view synchronization strategy \nis implemented by a novel data structure–partial persistent \nsequence. A partial persistent sequence is an ordered set of \nitems indexed by persistent and unique position identifiers. \nIt captures data dependencies of editing operations and encodes \nthem in a way that they can be correctly executed on \nany document replica. As a result, a simple and efficient \nview synchronization strategy can be implemented.