Causal graph rewriting

技術要約：因果グラフ書き換え（Causal Graph Rewriting）

問題提起
セル・オートマトン（CA）や因果グラフ力学（CGD）といった従来の動的システムのモデルは、空間構造（格子やグラフ）全体を同期させるためのグローバルなクロックに依存している。これらは効果的ではあるものの、そのような同期性は、分散コンピューティングにおける並列性を阻害し、普遍的な時間が存在しない相対論的な文脈における物理現象の非同期的な性質を捉えきれないという批判を受けることが多い。既存の非同期書き換え理論は、「時空決定性（space-time determinism）」、すなわち、非同期的な更新が行われる特定の順序に関わらず、システムの最終状態が一定であることを保証する厳密な枠組みを欠いていることが多い。本論文は、局所的なルールが有向非巡回グラフ（DAG）上で非同期的に作用することを許容しながら、明確な因果構造を維持し、かつ逐次合成の下で局所性の特性を保存するモデルの必要性に取り組んでいる。

手法
著者らは、構成を**ポートラベル付き有向非巡回グラフ（DAG）として表現する計算モデルである因果グラフ書き換え（CGR）**を導入する。

• グラフ形式： 頂点はイベント（計算プロセス）を表し、$t.x$（タイムタグ $t$、位置 $x$）と命名される。エッジは依存関係（計算上の因果関係）と局所性の制約を符号化する。グラフには、部分的なビューを扱い、サブグラフの合成を可能にするための「境界」頂点と「宙吊り（dangling）」エッジが含まれる。
• 近傍スキーム（Neighbourhood Schemes）： 局所ルールは、グラフの「コーン（cone）」（過去の頂点から到達可能な連結部分グラフ）に対して作用する。著者らは、位置 $x$ の周囲の特定のコーン $G_{N_x}$ を選択する近傍スキーム $N$ を定義する。極めて重要な点として、このスキームは**外延性（extensivity）**を満たさなければならない。すなわち、グラフに対して選択される近傍は、必要な情報を含むそのグラフのいかなる部分グラフに対しても同一でなければならず、ルールがグローバルな性質に依存しないことを保証する必要がある。
• 局所ルール： 局所ルール $A_x$ は、誘導された部分グラフ $G_{N_x}$ に作用する。これは現在の頂点 $t.x$ を消費し、内部状態と依存関係を更新し、新しい頂点 $(t+1).x$ を生成する。ルールはグラフの境界（宙吊りエッジ）を保持し、非巡回性を維持しなければならない。
• 逐次力学： 計算は、有効な位置の列 $\omega = x_n \dots x_1$ を通じて進行する。各ステップは、現在のグラフにおいてその位置が「過去（ready to fire）」である場合にのみ適用される。すべての可能なグラフの集合は、**時空図（space-time diagram）**を形成する。

主な貢献

1. 局所ルールの構造的特性： 著者らは、局所ルールがどのように適切に定義されるかを定式化する。有効な局所ルールは、本質的に位置（新しい位置は作成されず、タイムタグのみが更新される）および境界（修正された領域とコンテキスト間の頂点およびエッジ）を保持することを証明する。
2. セル・オートマトンのシミュレーション： 著者らは、CGRにおける表現力を実証するために、任意の一次元セル・オートマトンがCGR内でシミュレート可能であることを形式的に証明する。これは「行進する兵士（marching soldiers）」によるエンコーディングを用いて達成され、DAGの依存関係が計算の相対的な進展を追跡することで、非同期的なスケジューリングを通じて同期的な振る舞いを効果的にシミュレートする。
3. 時間遅延（Time-Dilation）の例： 内部状態（緑／赤の「膨張（dilation）」粒子）に基づいてグラフのトポロジーを修正（エッジを反転）する新しい例が示されている。これにより、グラフの異なる領域が異なる速度で進行し、グローバルなクロックなしに一般相対性理論における時間遅延を模倣する結果となる。
4. $\ast$-局所性と$\ast$-外延性（主要な結果）： 本論文の主要な技術的貢献は、局所性が逐次合成の下で保持されることの証明である。
   • $\ast$-外延性： 更新のシーケンスの近傍は、初期グラフの関連する部分グラフのみに依存する。
   • $\ast$-局所性： グラフ $G$ に対する一連のルール $A_\omega$ の適用効果は、それを誘導された部分グラフ $G_{N_\omega}$ に適用し、その後、変更されていないコンテキストと再合成することと同一である。
     これは、単一ステップにおいてルールが局所的であれば、任意の有効なシーケンスにおいても局所的であり続けることを示す、帰納的なブートストラップ引数（補題 5.2 および 5.4）を通じて証明される。

結果

• 定理 4.1： CGRシミュレーションの時空図と、半径1/2のセル・オートマトンの進化との間の厳密な対応関係を確立し、非同期モデルが同期的な力学を再現できることを証明する。
• 定理 5.1： CGRフレームワークにおける任意の局所ルールは、自動的に $\ast$-局所的 かつ $\ast$-外延的 であることを証明する。これにより、単一ステップに対して導出された構造的特性（位置保持、境界保持）が、任意の有限のルール適用シーケンスに対して標準的に拡張されることが保証される。
• 系 5.1： シーケンスに対しても、ルールの作用は計算された近傍の内部に限定され、境界およびコンテキストには影響を与えないことを確認する。

意義と主張
本論文は、CGRが分散計算における**軽量な同期（lightweight synchronization）**のための原理的な枠組みを提供すると主張している。依存関係をグラフ構造に直接エンコードすることで、グローバルな調整なしに異なる領域が独自のペースで進行することを可能にしつつ、因果順序によって、入力が準備できる前にイベントが処理されることを防いでいる。

著者らは、CGRを、古典的、可逆的、そして量子力学的な動的システムへの軌跡（図1に示される通り）における、因果グラフ力学の非同期的な対応物として位置づけている。このモデルは、時空幾何学が動的かつ状態依存的である一般相対性理論の離散モデルへの一歩として提示されている。

本論文は、モデルの構造的堅牢性（$\ast$-局所性を通じて）を確立している一方で、完全な時空決定性（すべてのスケジューリングがイベントの状態について一致することを保証するもの）の定理は、伴走する論文 [1] の主題であることを明記している。本研究は、その決定性の証明を支えるために必要な前提条件（特にシーケンスの局所性）を提供するものである。著者らは、物理的な重力を直接モデル化することを主張しているのではなく、局所的な計算ルールがいかにして相対論的な効果を彷彿とさせる動的で状態依存的なトポロジーを生じさせ得るかを探求している。