Distributed Systems
Eg-walker: Event Graph Walker
A collaboration algorithm for text editing that combines CRDT convergence with OT-competitive memory and merge performance.
Event Graph Convergence Proof
Formal proof that eg-walker produces identical document states regardless of topological sort order — strong eventual consistency.
Advance and Retreat Mechanism
How eg-walker navigates the causal graph by advancing and retreating individual events to simulate each operation's original context.
Internal State Machine
The per-character state machine that tracks insertion/deletion across prepare and effect versions in eg-walker.
Critical Versions and Partial Replay
How critical versions partition the event graph into independently processable sections, enabling garbage collection and efficient state reconstruction.
Compact Event Graph Encoding
Column-oriented, run-length encoded storage format that compresses collaborative editing histories by orders of magnitude.