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.
Concurrency issues
Concurrent collaboration can create conflicts when multiple users edit the same section of a document. Because users modify a local copy, their view may diverge from the server state until updates are pushed from the server. This delay can lead to conflicting updates or unintended overwrites.
Example 1
Consider a scenario in which two users attempt to add characters at the same position. The ...