Convergence Is Not Enough: The Livelymerge Problem

Automerge promises convergence: after two clients exchange changes, they deterministically reach the same state. But in Livelymerge (LM), where the entire heap — every object, class, and method — is an Automerge document, that promise isn't enough. The merged state can violate invariants, truncate data structures, or create infinite loops.

The core issue: Automerge merges writes, not intents. A client computes writes based on the state it saw, but after another client's changes are merged, those writes may no longer make sense.

Exhibit A: A Linked List That Breaks

Consider a linked list 1 → 2 → 3 → 4. Two clients modify it concurrently:

  • Client A swaps 2 and 3: writes 1.next ← 3, 2.next ← 4, 3.next ← 2. Result: 1 → 3 → 2 → 4.
  • Client B swaps 3 and 4: writes 2.next ← 4, 3.next ← null, 4.next ← 3. Result: 1 → 2 → 4 → 3.

Automerge merges transactions deterministically, but the order matters. If A then B: 3.next becomes null (B's write), so traversing from 1 yields 1 → 3 and nodes 2 and 4 are stranded. If B then A: 3.next becomes 2 (A's write), creating a cycle: 1 → 3 → 2 → 4 → 3 → 2 → 4... — an infinite loop.

Automerge did nothing wrong. Both clients converge on the same broken state. The problem: B's writes were computed against the original list, but after A's changes, those writes no longer represent B's intent. The merge replays effects, not intents.

Beyond Linked Lists: The Scope of the Problem

The linked list is just a simple example. The issue affects any invariant spanning multiple properties or objects:

  • Doubly-linked lists: next and prev must mirror each other.
  • Trees: In Morphic (the graphical framework used in LM), every morph's owner must agree with its owner's submorphs. Concurrent reparenting can break this.
  • Cached counts or indexes: A cached count must agree with the collection it summarizes.
  • Uniqueness constraints: "Each element appears exactly once" is invisible to raw writes.

In LM, where the heap is the document and users can build arbitrary data structures, this is not a corner case. It's a fundamental challenge.

Automerge's Built-in Types: A Partial Solution

Automerge's built-in datatypes (arrays, maps) merge well because they record operations like insert and delete, not raw pointer writes. In Morphic, each morph's submorphs is an Automerge array, so concurrent adds interleave correctly. But this only works when you stick to the built-in types. As soon as you compose them — e.g., a doubly-linked list built from an array — invariants break.

The team has found that careful programming — leaning on built-in types and avoiding redundant representations — reduces the frequency of issues, but it's not a solution.

A Promising Direction: Merge-Aware Datatypes

The natural fix is to merge intents, not writes. Instead of recording "set 3.next to null", record "remove value 4 from the list" or "insert 3 after 1". Automerge already does this for its built-in types. The idea: let programmers define custom types that expose a higher-level vocabulary, and have Automerge merge those operations.

There's precedent: Kleppmann et al.'s move operation for replicated trees bakes "reparenting never creates a cycle" into the merge. The technique replays all operations in a deterministic order (e.g., by timestamp), checking each against the invariant and skipping violations. Since all clients replay the same order, convergence is guaranteed and invariants hold.

However, this approach has drawbacks: an operation that was valid when executed can be retroactively invalidated by a late-arriving operation with a lower timestamp, causing previously accepted work to roll back. And for user-defined types, operations must commute or have a deterministic conflict resolution — a high bar for programmers.

Related Work: Coln and ECRO

Coln, a mergeable database by Martin Kleppmann, Vincent Liu, Owen Lynch, and collaborators, takes a strict line: if a merge would violate a declared constraint (e.g., "this is a doubly-linked list"), the merge is refused. Users (or an AI) must fix the data before merging. ECRO is another system built on the same replay-with-invariants idea.

The Livelymerge team acknowledges they don't have a solution yet. They're actively exploring merge-aware datatypes and invite discussion.

What's Next

The next note will describe the object model that makes this concrete: how an Automerge document can look and feel like an ordinary JavaScript heap, including object tables, proxies, and garbage collection.

For now, the takeaway for developers: when using CRDTs in complex systems, convergence is necessary but not sufficient. You must design data structures with merge semantics in mind, or you'll end up with corrupted state.

This article is based on the Livelymerge project note "Convergence Is Not Enough" by Alex Warth, Dan Ingalls, and Peter Van Hardenberg.