Алекс Уорт вместе с Дэном Ингаллсом и Питером ван Харденбергом строит в проекте Livelymerge (LM) систему в стиле Lively Kernel, где вся куча — объекты, классы и методы — это документ Automerge. Несколько пользователей работают с общей памятью объектов, даже офлайн, а Automerge всё согласует. Но слияние состояния живой системы — нетривиальная задача.
Automerge гарантирует конвергенцию: после обмена изменениями клиенты приходят к одному состоянию. Но оно может оказаться непригодным для программы. Пример — связанный список 1 → 2 → 3 → 4. Клиент A меняет местами узлы 2 и 3, записывая 1.next ← 3, 2.next ← 4, 3.next ← 2. Клиент B меняет местами 3 и 4: 2.next ← 4, 3.next ← null, 4.next ← 3. Automerge детерминированно выбирает один из порядков транзакций, и оба клиента получают одинаковый результат. Если сначала A, потом B, 3.next = null — список обрывается на «1, 3», узлы 2 и 4 остаются в стороне. Если сначала B, потом A, 3.next = 2 — получается цикл 1, 3, 2, 4, 3, 2..., и обход никогда не завершится.
Automerge работает правильно: конвергенция есть. Проблема в том, что повторное применение записей B после A — не то же самое, что выполнение намерения B после A. B считал свои записи по исходному списку, которого после слияния уже нет.
Это не только про списки. Встроенные типы Automerge — массивы, карты — сливаются хорошо. В Morphic (графический фреймворк из Self, позже Squeak и Lively Kernel) список submorphs — это массив Automerge, конкурентные добавления нормально перемешиваются. Но при композиции типов инварианты невидимы: двусвязный список (next и prev должны совпадать), дерево (owner морфа должен согласовываться с submorphs владельца), кэшированный счётчик.
Готового решения у авторов пока нет. Им нравится идея merge-aware datatypes: сливать намерения, а не записи. Automerge уже так делает для встроенных типов — хранит операции вставки и удаления, а не записи указателей. Если бы типы можно было объявлять и задавать их операции, слияние работало бы на этом уровне. Прецедент — операция move для реплицируемых деревьев Клеппмана с соавторами: правило «смена родителя не создаёт цикл» встроено прямо в слияние. Техника — воспроизводить операции всех клиентов в одном порядке (например, по метке времени), проверяя инвариант и пропуская нарушающие. На этом же стоит ECRO. Минус: валидная операция может быть отменена задним числом, когда поздно приходит операция с меньшей меткой времени.
Той же темой занимается Coln — mergeable-база данных Мартина Клеппмана, Винсента Лю и Оуэна Линча. Если слияние нарушает ограничение, Coln отказывает в нём, и пользователь (или AI) возвращает данные в согласованное состояние.