Brief Introduction to Replayable Event Graph

Seph Gentle (opens in a new tab), the author of Replayable Event Graph, is currently working on the its paper, and it's highly anticipated.

Whether in real-time collaboration or multi-end synchronization, a directed acyclic graph (DAG) forms over the history of these parallel edits, similar to Git's history. The REG algorithm records the history of user edits on the DAG. Unlike conventional CRDTs, REG can record just the original description of operations, not the metadata of CRDTs.

For instance, in text editing scenarios, the [RGA algorithm] needs the op ID and Lamport timestamp (opens in a new tab) of the character to the left to determine the insertion point. [Yjs]/Fugue, however, requires the op ID of both the left and right characters at insertion. In contrast, REG simplifies this by only recording the index at the time of insertion. Loro, which uses Fugue (opens in a new tab) upon REG, inherits these advantages.

An index is not a stable position descriptor, as the index of an operation can be affected by other operations. For example, if you highlight content from index=x to index=y, and concurrently someone inserts n characters at index=n where n<x, then your highlighted range should shift to cover from x+n to y+n. But REG can determine the exact position of this index by replaying history. Thus, it can reconstruct the corresponding CRDT structure by replaying history.

Reconstructing history might seem time-consuming, but REG can backtrack only some. When merging updates from remote sources, it only needs to replay operations parallel to the remote update, reconstructing the local CRDTs to calculate the diff after applying remote operations to the current document.

The REG algorithm excels with its fast local update speeds and eliminate concerns about tombstone collection in CRDTs.For instance, if an operation has been synchronized across all endpoints, no new operations will occur concurrently with it, allowing it to be safely removed from the history.