Event Graph Walker (Eg-Walker)

Event Graph Walker (Eg-Walker) is a revolutionary CRDT algorithm that fundamentally changes how collaborative editing systems handle concurrent operations. Instead of storing complex CRDT metadata, Eg-Walker enables the use of simple indices by efficiently replaying relevant history when needed.

Important Note: Loro is not a strict implementation of Event Graph Walker. Rather, Loro is heavily inspired by Eg-Walker’s design philosophy and incorporates its key insights to achieve similar properties - particularly the ability to use simple indices instead of complex CRDT metadata, and the efficient replay mechanism for handling concurrent operations.

The Problem: Complex CRDT Metadata

Traditional CRDTs require extensive metadata to maintain consistency across distributed systems:

• RGA algorithm: Requires operation ID and Lamport timestamp of the left neighbor
• Yjs/Fugue: Needs operation IDs of both left and right neighbors
• Storage overhead: Each operation carries significant metadata for position tracking
• Tombstone accumulation: Deleted content must be retained indefinitely

This metadata complexity leads to:

• Increased storage requirements
• Slower performance as documents grow
• Complex garbage collection challenges
• Higher network bandwidth usage

The Innovation: Simple Indices with Smart Replay

Eg-Walker introduces a paradigm shift: record simple indices, replay when needed.

Core Concept

Instead of storing complex position descriptors, Eg-Walker:

1. Records operations with simple indices at the time of execution
2. Maintains a directed acyclic graph (DAG) of the edit history
3. Replays relevant portions of history when merging concurrent changes
4. Reconstructs the exact CRDT state only when needed

How It Works

The Event Graph

In collaborative editing, parallel edits naturally form a directed acyclic graph (DAG), similar to Git’s history:

    A --- B --- C     (User 1)
   /             \
Root              Merge
   \             /
    D --- E --- F     (User 2)

Each node represents an operation, and edges represent causal dependencies.

The Algorithm

1. Local Operations: Direct and Fast

When a user makes a local edit:

• Record the operation with its current index position
• No complex metadata calculation needed
• Immediate application to the document

Example:

// Traditional CRDT (e.g., RGA)
insert({
  char: 'a',
  leftId: 'op-123',
  timestamp: 1234567890,
  siteId: 'user-1'
})
 
// With Eg-Walker
insert({
  char: 'a',
  index: 5  // Simple index!
})

2. Merging Remote Operations: Smart Replay

When receiving remote operations:

1. Find the Lowest Common Ancestor (LCA) between local and remote versions
2. Replay operations from the LCA to both versions
3. Construct temporary CRDT state to calculate effects
4. Apply the merged result

The key insight: You only replay the divergent portion of history, not the entire document.

3. Index Transformation

Consider this scenario:

• You highlight text from index 10 to 20
• Concurrently, someone inserts 5 characters at index 3
• Your highlight should shift to indices 15 to 25

Eg-Walker handles this by:

1. Identifying concurrent operations through the event graph
2. Replaying operations in causal order
3. Transforming indices based on the replay sequence

Performance Benefits

1. Reduced Storage

2. Faster Local Updates

• No metadata computation: Direct index-based operations
• No tombstone traversal: Clean document state
• Predictable performance: O(1) or O(logN) for most local operations

3. Efficient Synchronization

• Minimal replay: Only divergent history portions
• Bounded computation: Proportional to concurrent edits, not document size
• Smart caching: Reuse computed states when possible

Implementation in Loro

While Loro is not a pure Eg-Walker implementation, it draws heavily from Eg-Walker’s innovations to achieve similar benefits. Loro implements Fugue (a modern CRDT algorithm) with Eg-Walker-inspired optimizations:

• Fugue’s correctness guarantees for text editing
• Eg-Walker-inspired efficiency in storage and computation
• Simple index-based operations at the API level
• Smart replay mechanisms for merging concurrent changes

This hybrid approach provides:

// Simple API with powerful internals
const doc = new Loro();
const text = doc.getText("content");
 
// Just use indices - Eg-Walker handles the complexity
text.insert(5, "Hello");
text.delete(2, 3);
 
// Efficient merging happens automatically
doc.import(remoteUpdate);

Garbage Collection Revolution

One of Eg-Walker’s most significant advantages is safe garbage collection:

Traditional CRDTs

• Must keep all tombstones forever
• Document size grows unbounded
• Complex protocols for coordinated cleanup

With Eg-Walker

• Operations synchronized across all endpoints can be safely removed
• No new operations will be concurrent with fully-synchronized ones
• Document size remains proportional to active content

Research Foundation

Eg-Walker is based on rigorous academic research:

Collaborative Text Editing with Eg-walker: Better, Faster, Smaller
By: Joseph Gentle, Martin Kleppmann

The algorithm has been proven to:

• Maintain strong eventual consistency
• Preserve all CRDT correctness properties
• Significantly reduce computational and storage overhead