収束だけでは不十分：Livelymergeが直面する並行マージの深い問題
Convergence is not enough
Livelymergeプロジェクトでは、ヒープ全体をAutomerge文書として扱うことでマージを「無料」で手に入れようとしている。しかし、リンクリストの例が示すように、収束は保証されても、プログラムの不変条件が保たれるとは限らない。並行トランザクションの書き込みを順に適用すると、リストの切断や循環が生じ得る。これは単なるデータ構造の問題ではなく、Morphicのツリー構造やキャッシュなど、複数のプロパティにまたがる不変条件に広く影響する。有望な方向性として、プログラマー定義の型に対して意図レベルでマージする「マージ対応データ型」のアイデアを探っている。
マージは意図ではなく効果を再生するものであり、プログラマーの不変条件はAutomergeが見える場所にはどこにも書き留められていない。収束だけでは不十分である。
HNでの議論
12- wim
マルチプレイヤーIDE[1]を構築しているが、ドキュメントやプランニング向けで、ドキュメントはツリー/グラフである必要がある（アウトライン、参照、トランスクルージョンなどをサポートするため）。
すべてのタイプの操作を無条件にリプレイしてマージすることはできない。例えば、ツリーの循環を引き起こす可能性があるからだ。リンクリストのように、特定の操作はオフラインクライアントにとってはローカルに有効でも、収束した順序ではグローバルに有効ではない場合がある。
私たちの同期エンジンは、操作を無条件操作とガード付き操作の2つのタイプに区別している。
無条件操作は構造的/データモデルの不変条件に違反することはない。例えば、SetCompleted(task_guid, true)のようなものだ。シンプルな最終書き込み勝ち方式。
ガード付き操作はトポロジーを変更できる。例えば、InsertMove(node_guid, parent_guid, after_guid)のようなものだ。これらは作成時の状態ではなく、現在の状態に対してチェックされる。リプレイ中は、まず楽観的なローカル操作を元に戻し、受信した正規の操作を順番にリプレイする。各操作のミューテータ関数は、適用前に現在の状態を検証し、条件に違反する場合（例えば、別のクライアントがその間に別の移動を行ったために循環が生じる場合）は、決定的に拒否される。私たちの場合、権威あるサーバーもあるので、同じガード付き操作をデータ構造以外の条件（権限など）にも使用できる。例えば、AddUser(workspace_guid, user_guid)ミューテータ関数は、最初に権限状態をチェックできる。
- alexisread
格子型に関する関連論文（BloomL）：
https://dsf.berkeley.edu/papers/UCB-lattice-tr.pdf
これに加えて、並行編集を順序付けるために、因果レジスタ（キーごとのマークルクロック）が必要になる。単に片方を落とすのではなく。
最後に、意味論的なマージを処理するには、PijulスタイルのVCSが必要になる可能性が高い。
- Animats
これはどうやらAutomerge[1]に基づいているようだ。本当に良いアイデアに思える。MMOゲームのクライアントとサーバーを同期するのに十分なアイデアだろうか？
2012年の論文、Automergeサイトの最終更新は2025年。なぜこれがどこにでもあるわけではないのか？