Convergence is not enough

Introduction In the Livelymerge project, Dan Ingalls, Peter Van Hardenberg, and I (Alex Warth) are building a Lively Kernel-like system whose heap — every object, class, and method — is an Automerge document. The pitch, from the first note in this series, was that this would give us merges “for free”: multiple users share the same object memory, work on it concurrently (even offline), and Automerge reconciles everything. I also wrote that merging the state of a live system is a nontrivial problem, and that there’s no way to guarantee that objects’ invariants won’t be violated. This note looks that problem straight in the eye, with a concrete example. We don’t have a solution yet — this is an acknowledgment, not a victory lap — but I’ll sketch one possible solution that we find promising, and we’d love to hear your ideas, too. Exhibit A: a linked list Automerge’s promise is convergence: after two clients exchange their changes, they are guaranteed to arrive at the same state. But that state is not guaranteed to be one your program can live with. To be fair, for lots of applications — documents, todo lists, sketches — Automerge’s merge does just what you’d want. But in LM we’re doing something weirder: asking it to merge the heap of a running program, pointers and all. That’s well outside Automerge’s comfort zone, and this note is about what happens out there. Consider a humble linked list containing 1 → 2 → 3 → 4, built the way any programmer would build it in LM: each node has a next property that points to another node. Now suppose two clients modify it concurrently: Client A swaps 2 and 3, by writing 1.next ← 3, 2.next ← 4, and 3.next ← 2. Their list now reads 1, 3, 2, 4. Client B swaps 3 and 4, by writing 2.next ← 4, 3.next ← null, and 4.next ← 3. Their list reads 1, 2, 4, 3. Now let’s see what happens when these changes sync. Here’s how Automerge merges them: each client’s change is a transaction, and the merge behaves as if one transaction’s writes were applied and then the other’s — Automerge deterministically picks one of the two orders, and both clients get the same one. (So arbitrary interleavings of the individual writes are not possible, which limits the number of states we can end up in.) A write that the later transaction didn’t touch survives from the earlier one; where both transactions wrote, the later one wins. Let’s see what the two possible orders actually produce. 1.next comes from A either way (B never wrote it), 4.next comes from B either way, but 3.next — which both transactions wrote — goes to whichever came second: A then B (3.next = null): traversing from 1 yields “1, 3” — the list has been truncated, and nodes 2 and 4 are stranded off to the side. B then A (3.next = 2): traversing from 1 yields “1, 3, 2, 4, 3, 2, 4, …” — the list now contains a cycle, and any code that walks it will never terminate. Let me emphasize: Automerge did nothing wrong here. Both clients converge on the same result, deterministically, exactly as promised. The trouble is that replaying B’s writes after A’s is not the same as performing B’s intent after A’s. Client B computed those three writes by looking at the original list, 1 → 2 → 3 → 4 — a state that, post-merge, no longer exists. If B’s “swap 3 and 4” had actually run after A’s change, it would have produced different writes and a perfectly good list. 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. Convergence is not enough. This is not just about linked lists You can dodge this particular example by not building linked lists out of next pointers. Automerge has built-in datatypes with well-behaved merge semantics — its arrays (which our object model exposes directly) merge concurrent insertions and deletions the way you’d hope, and maps of various flavors are easy to represent. We lean on this hard in practice in Morphic, t