Concurrency in Collaborative Editing
Explore concurrency issues in collaborative editing services like Google Docs, where simultaneous changes can lead to conflicts. Assess conflict resolution techniques, comparing operational transformation (OT) and conflict-free replicated data type (CRDT). Learn how these methods ensure strong consistency and document convergence by maintaining commutativity and idempotency.
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?
A document is a composition of characters in a specific order. Each character has a value and a positional index. The character can be a letter, a number, an enter (↵), or a space. An index represents the character’s position within the ordered list of characters.
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.