← 分散システム 一覧

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：論理時計（Lamportタイムスタンプ）　|　関連：レプリケーション方式（同期／非同期・リーダー／リーダーレス）・PACELC・結果整合性

要点（BLUF）

• ベクトル時計は、各プロセスが全プロセス分のカウンタ配列 V を持つ論理時計。Lamportのスカラを「全員ぶんのベクトル」に拡張したもの。
• これにより a → b ⇔ V(a) < V(b)（双方向）が成り立ち、因果と並行を正確に区別できる。Lamportの「逆が言えない」限界を解消する。
• 代償はサイズ O(N)（プロセス数に比例）。動的なメンバーや巨大クラスタでは重く、版数ベクトル・ドット付き版ベクトルなどの工夫が要る。

問題設定 ── 並行を「並行」と言いたい

論理時計（Lamportタイムスタンプ） は C(a)<C(b) でも並行かもしれず、衝突検出に使えません。たとえばリーダーレス複製（レプリケーション方式（同期／非同期・リーダー／リーダーレス））では「2つの更新が因果順か、並行（＝衝突）か」を判定したい。これにはベクトル時計が要ります。

アルゴリズム ── 全成分を持つ

プロセス i は配列 V[0..N-1] を持ち、

ローカル/送信イベント: V[i] += 1
受信(相手の Vm):        各 k で V[k] = max(V[k], Vm[k]); その後 V[i] += 1

比較規則（要：ベクトルは半順序）：

V < W なら V は W に先行、どちらの ≤ も成り立たなければ並行。

具体例 ── 並行を正しく検出（実機）

ラボ 02-03_vector_clock.py の実行結果（P1→P2 は通信あり、P3 は独立に進む）：

== ベクトル時計 ==
e1 (P1送信)     = [1, 0, 0]
e2 (P2が受信)   = [1, 1, 0]
e3 (P3ローカル) = [0, 0, 1]

e1 と e2 の関係: V < W (V が先行) -> 期待: 因果(先行)
e1 と e3 の関係: V || W (並行) -> 期待: 並行
e2 と e3 の関係: V || W (並行) -> 期待: 並行

e1=[1,0,0] < e2=[1,1,0] なので e1→e2（因果）。一方 e3=[0,0,1] は e1・e2 とどちらの ≤ も満たさないので並行。Lamportなら e2 と e3 にスカラ順序が付いてしまい区別できませんが、ベクトル時計は || を正しく見抜きます。

仕組みの直観 ── なぜ双方向が成り立つか

V(b)[i] は「プロセス i のイベントを b が何個まで知っているか」を表します。a→b なら、a の起きたプロセス j の成分について V(b)[j] ≥ V(a)[j] が必ず成り立ち、かつどこか1成分は真に大きい。逆に全成分が a 以上なら、a の情報が漏れなく b に伝わっている＝因果がある。「誰の何番目まで知っているか」を全員ぶん持つから、因果が完全に再構成できるのです。

他手法との比較

なぜ分散だと難しいか（直観）

「同時に起きた2つの更新」を事後に判定する手段が、分散には無い（共通時計が無い）。ベクトル時計は、各更新が「どの履歴を見て生まれたか」を持ち歩かせることで、衝突かどうかを構造的に判定できるようにします。Dynamo系（レプリケーション方式（同期／非同期・リーダー／リーダーレス））の衝突検出の理論的基盤です。

⚠️ よくある誤解・落とし穴

• 「ベクトル時計があれば衝突を自動解決できる」→ 検出はできるが解決（どちらを採るか）は別問題。LWW・マージ・CRDT などの方針が要る（PACELC・結果整合性）。
• 「成分は実時刻」→ 違う。各成分はそのプロセスの論理イベント数。
• 「N（プロセス数）が増えても平気」→ サイズが O(N) で増え、メンバー変動で扱いが難しい。版数ベクトル等で軽量化する。
• 「V[i] += 1 を受信時に忘れてよい」→ 自分のイベントを数え損ね、因果判定が壊れる。

対応ラボ

distributed-systems-study/labs/02-03_vector_clock.py（因果ペアと並行ペアを V<W / V∥W で判定し、Lamportとの差を確認済み）。

関連

• 出発点の限界は 論理時計（Lamportタイムスタンプ）
• 衝突検出が効くのは レプリケーション方式（同期／非同期・リーダー／リーダーレス）
• 一貫した大域状態は グローバルスナップショット（Chandy-Lamport）

← 第2章 時間と順序 目次