Automerge Converges, But Your Linked List May Break
Convergence Is Not Enough
In the Livelymerge project, we're building a system where the entire heap is an Automerge document, hoping for free merges. But convergence isn't enough: merging concurrent edits to a linked list can truncate it or create a cycle. The problem is that Automerge replays writes, not intents. We explore a promising direction: merge-aware datatypes that record high-level operations, and note related work like Coln.
The merge replays effects, not intents, and the programmer’s invariants — every node appears exactly once, no cycles, the list ends — were never written down anywhere that Automerge could see.
- wim
We're building a multiplayer IDE [1] but for docs/planning where docs needs to be trees/graphs (to support outlining, refs, transclusions and so on)
We can't just merge any type of operation by replaying unconditionally, because that can cause tree cycles for example. Like the linked list certain operations can be valid locally for an offline client, but not globally in the converged order.
Our sync engine distinguishes between different types of operations: unconditional operations and guarded operations.
Unconditional operations can't violate structural/data-model invariants. For example SetCompleted(task_guid, true). Simple last-writer-wins.
Guarded operations can mutate topology, like InsertMove(node_guid, parent_guid, after_guid). These are checked against the current state, not the state when they were created. During replay we first revert optimistic local operations and replay the incoming canonical operations in order. The mutator function for each operation validates the current state before applying it and if it would violate a condition (for example by creating a cycle because another client made another move in the meantime) it is deterministically rejected. In our case we also have an authoritative server so we can also use the same guarded operations for conditions beyond data structure, like permissions, so the AddUser(workspace_guid, user_guid) mutator function can check permissions state first for example.
- alexisread
Relevant paper on lattice types (BloomL):
https://dsf.berkeley.edu/papers/UCB-lattice-tr.pdf
In addition to this, you’ll need a causal register (per-key merkle clock) to order concurrent edits, rather than drop one.
Lastly, you’re likely to need a Pijul style VCS to handle semantic merges.
- Animats
This is apparently based on Automerge.[1] It sounds like a really good idea. Is it a good enough idea to sync MMO game clients and servers?
Paper from 2012, last Automerge site update in 2025. Why isn't this everywhere?