因果順序とhappened-before関係の図解

時空間図とは何を描くものか

分散システム（/devops/microservices/）で複数プロセスが動くとき、「どのイベントがどのイベントより前か」は壁時計では決められない。そこで因果関係そのものを図にしたのが 時空間図（space-time diagram） である。Lamport が 1978 年の論文で導入した描き方で、論理時計（/devops/logical-clocks/）の議論はほぼすべてこの図の上で行われる。

描き方は単純だ。各プロセスを1本の 横線 で表し、左から右へ時間が進む。線上に打つ 点 がそのプロセス内のイベント（ローカルイベント）。プロセス間で送るメッセージは、送信点から受信点へ向かう 斜めの矢印 で描く。矢印が必ず右上がり/右下がりに「右へ」進むのは、送信より受信が後だからだ。

時間 →
P1: --a----b---------e----->
          \         /
           \       /
P2: --------c-----d-------->

この図で a, b, e は P1 のイベント、c, d は P2 のイベント。b → c の矢印は「b で送ったメッセージを c で受信」、d → e は「d で送って e で受信」を表す。図はこれだけで因果のすべてを含んでいる。

図から happened-before を読む

happened-before 関係（記号 →）は「a は b に影響を与ええた」という因果の可能性を表す。図の上では、次の幾何的な操作にそのまま対応する。

happened-before の3条件は、この「到達可能性」を分解したものにすぎない。

1. 同一プロセス内：同じ横線上で a が b より左なら a → b（線を右へたどる）。
2. メッセージ：送信点 a から受信点 b へは矢印で到達できるので a → b。
3. 推移律：到達経路をつなげられるなら a → c。横線と矢印を乗り継いだ経路がこれにあたる。

先の図で確かめる。a → b は同一線上。b → c は矢印。c → d は P2 の線上。d → e は矢印。これらを乗り継げば a → e も成り立つ（a から右へ b、矢印で c、右へ d、矢印で e）。図の上で1本の経路として描けることが、推移律の正体である。

並行イベント：図のどこにも経路がないペア

ここが時空間図の最大の効用だ。a → b でも b → a でもないペア、つまり どちらからも相手に到達できない 2点が存在する。これを 並行（concurrent、記号 a ∥ b） と呼ぶ。次の図を見る。

時間 →
P1: --a-------x---------->
          \
           \
P2: --------b----y------->

a → b（矢印で到達）は成り立つ。では x と y はどうか。x は P1 上で a の右、y は P2 上で b の右にある。x から y へは、x が送信点でない限り横線でも矢印でも到達できない。y から x へも同様だ。よって x ∥ y ＝ 並行である。

裸の波括弧を避けて集合で書くと、あるイベント e に対し「e に到達できる点の集合」{e より前の因果} と「e から到達できる点の集合」{e より後の因果} 以外の、図上のすべての点が e と並行になる。因果の「光円錐」の外側、と言い換えてもよい。

ベクタークロックの増分を図に貼る

時空間図の各点に ベクタークロック を書き込むと、到達可能性という幾何が、配列の大小という数値に翻訳される。N プロセスの系で各点に長さ N の配列を割り当てる。更新規則は次の通り。

# プロセス i の現在値を V_i（初期は全要素 0）とする
# 1) ローカルイベント: 自分の要素だけ +1
V_i[i] = V_i[i] + 1

# 2) 送信: 上で +1 した後の V_i を配列ごとメッセージに添付して送る
# 3) 受信: 要素ごとに max を取り、最後に自分の要素を +1
for k in 0..N-1:
    V_i[k] = max(V_i[k], msg.V[k])
V_i[i] = V_i[i] + 1

先の {P1, P2} の図（2要素配列、左が P1・右が P2）に実際に貼ってみる。

時間 →
P1: --a(1,0)----b(2,0)---------e(3,2)-->
                   \           /
                    \         /
P2: ----------------c(2,1)--d(2,2)------>

たどり方を1点ずつ確認する。a は P1 の最初のローカルイベントで (1,0)。b も P1 のローカルイベント（ここで送信）で (2,0)。c は b からのメッセージ受信なので、自分の値 (0,0) と受信値 (2,0) を要素ごと max して (2,0)、最後に自分（P2＝右）を +1 して (2,1)。d は P2 のローカルイベント（送信）で右を +1、(2,2)。e は d の受信で、自分 (2,0) と受信 (2,2) の max が (2,2)、自分（P1＝左）を +1 して (3,2)。

矢印をまたぐたびに相手側の要素が「伝播」して増えるのが、図の上で見て取れる。これが「因果の鎖に沿って情報が伝わる」ことの数値的な現れである。

比較規則：図の到達可能性と完全に一致する

2つの配列 VA と VB を次のように比較する。波括弧の集合表記はインラインコードで {すべての k} のように書く。

VA ≤ VB  ⇔  すべての k で VA[k] ≤ VB[k]
VA < VB  ⇔  VA ≤ VB かつ ある k で VA[k] < VB[k]

この数値判定が、図でたどった到達可能性と過不足なく一致する。

並行の数値シグネチャを上の図で確かめる。b = (2,0) と c = (2,1) なら b < c で因果あり（矢印どおり）。一方、もし P2 に b より前の独立イベント c0 = (0,1) があれば、a = (1,0) と c0 = (0,1) は1要素目が a で大きく2要素目が c0 で大きいので、どちら向きにも < が立たない。これが「図に到達経路がない」ことの数式版である。

図を使う実務上の意味

時空間図は黒板の道具に見えて、実務の判断基準そのものになる。整合性モデル（/devops/consistency-models/）の因果整合性（causal consistency）は「happened-before を保って見せる」契約であり、その happened-before はこの図で定義される。Dynamo 系 KVS が競合バージョンを兄弟（sibling）として残すのも、ベクタークロックが並行（図に経路なし）を検出したときだけだ。

合意アルゴリズム（/devops/consensus-family-tree/）が全順序を作るのは、いわば「並行ペアに人為的な順序を後付けする」操作にあたる。半順序である図の上に、矛盾しない1本の全順序線を引けることを保証するのが合意の仕事、と捉えると位置づけが明確になる。

まとめ

• 時空間図は各プロセスを横線、ローカルイベントを点、メッセージを斜めの矢印で描く。因果順序を「右向きの線と矢印をたどれるか」という到達可能性 に翻訳する。
• a から b へ経路があれば a → b、どちらからも到達できなければ a ∥ b（並行）。並行ペアの存在が、happened-before が半順序であることの視覚的証拠である。
• 各点にベクタークロックを貼ると、ローカルイベントは自分の要素を +1、受信は要素ごと max して +1 という規則で図と数値が1対1に対応する。矢印をまたぐと相手側要素が伝播する。
• 比較規則 VA < VB は図の到達可能性と完全一致し、どちらにも < が立たない状態が並行＝図の経路不在を表す。この対応が因果分析の確かな足場になる。