Concurrency in Collaborative Editing

Concurrent editing requires more than applying operations in arrival order. An insertion or deletion refers to the state the author saw, which may differ from the receiver’s state. Compare two ways to preserve that context: transform positional operations, or use a replicated data structure with stable identities and defined merge rules.

Introduction

We have designed the core collaborative editing service, but we still need to address how to handle concurrent document changes. Before solving for concurrency, we must define the data model of a collaborative text editor.

What is a document editor?

For this simplified model, a document is an ordered sequence of characters. Each character has a value, such as a letter, digit, newline (↵), or space. An index identifies its position in the current sequence. A production editor must additionally define its text units and represent formatting, embedded objects, and stable comment anchors.

The editor performs operations like insert(), delete(), and edit() on characters based on these indexes. The diagram below depicts how an editor executes these operations.