Conflict resolution using OT and CRDT algorithms

Imagine a scenario where you and your friend are working on a project report in google doc over zoom. You both are updating the index section adding various items. Every wondered, how google doc is handling these concurrent updates ?

One of ways to handle conflicts during concurrent updates is using locking mechanism. With this a the document/state is locked for a particular user and other users are prevented from making the changes. We can use either pessimistic or optimistic locking.

Pessimistic locking assumes conflicts will occur and locks the shared resource when any user accesses it.

In contrast, optimistic locking is more permissive and allows multiple users to access and modify a shared resource simultaneously. The conflicts are only checked during the final update to the shared resource.

Better way to handle this is using two algorithms - OT and CRDT.

OT stands for Operational Transformation and CRDT stands for Conflict-free Replicated Data Types.

Both of these provide a way to handle conflicts in real-time collaborative applications like google doc, in scenarios where more than one user end up updating the same state of the application.

Operational Transformation

This algorithm treats every change to the state (e.g doc) as an operation. When concurrent changes are made, OT takes one of the operations and transforms it in a way to keep the effect of the other operation.

OT always transforms the second operation relative to the first, not vice versa. This is why Google Docs and similar tools can handle real-time collaboration without conflicts.

OT follows some transformation rules when during transformation. Refer them in below table.

In case of tie-breaks, OT uses either timestamp, order or priority to resolve which operation should be applied first.

Drawbacks of OT in Real Apps

• Complex Logic – Hard to handle all edge cases (e.g., overlapping edits).
• Server-Dependent – Needs a central server; struggles offline.
• Slow for Large Docs – Transforming ops repeatedly hurts performance.
• Undo is Tricky – Transformed ops make history non-linear.
• Arbitrary Tie-Breaks – Timestamp/user-ID ordering can feel unfair.
• Hard to Scale – Operation logs grow indefinitely with heavy use.

Conflict-free Replicated Data Type

A CRDT (Conflict-free Replicated Data Type) is a data structure that can be replicated across multiple nodes in a distributed system, where each replica can be updated independently and concurrently without coordination between replicas, and all replicas will eventually converge to the same state.

The key properties of CRDTs are:

• Eventual consistency: All replicas will eventually have the same state
• No coordination required: Updates can happen independently on any replica
• Automatic conflict resolution: The data structure itself handles conflicts mathematically

There are two main categories:

• State-based CRDTs (CvRDTs) - replicas exchange their full state and merge using a join function that is commutative, associative, and idempotent.
• Operation-based CRDTs (CmRDTs) - replicas exchange operations, which must be commutative when applied.

The fundamental breakthrough of CRDTs is changing what we mean by "conflict". Traditional systems have conflicts because they're trying to manage shared mutable state. CRDTs eliminate conflicts by making operations mathematically commutative.

How CRDTs resolve conflict ?

1. Position-Based Ordering (Text CRDTs)

Rule: Characters inserted at same logical position are ordered by their unique identifiers

Example:

• Alice inserts "big" with IDs alice:100, alice:101, alice:102
• Bob inserts "red" with IDs bob:200, bob:201, bob:202
• Merge rule: Lower timestamp/nodeID wins position
• Result: "big red" (alice:100 < bob:200)

2. Last-Write-Wins (LWW)

Rule: Most recent timestamp wins

Example:

• Alice sets name = "John" at timestamp 100
• Bob sets name = "Jane" at timestamp 150
• Merge rule: Higher timestamp wins
• Result: name = "Jane"

3. Add-Wins (OR-Set)

Rule: Additions beat deletions unless deletion observed the specific addition

Example:

• Alice adds "apple" with tag alice:1
• Bob removes "apple" (only sees older tags)
• Merge rule: Alice's new addition survives Bob's removal
• Result: Set contains "apple"

4. Lexicographic Ordering

Rule: Deterministic tie-breaking using node IDs

Example:

• Same timestamp operations from "alice" and "bob"
• Merge rule: Alphabetical order
• Result: "alice" operations come before "bob"

5. Causal Precedence

Rule: Operations that happened-before others take precedence

Example:

• Alice edits, then Bob edits Alice's result
• Merge rule: Bob's edit causally depends on Alice's
• Result: Maintain causal order regardless of network delays

OT vs CRDT

Sample Live Editor Architecture using CRDT