論理時計（Lamportタイムスタンプ）

← 分散システム一覧

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：物理時計とクロック同期（NTP）　|　関連：ベクトル時計・線形化可能性と逐次一貫性

要点（BLUF）

Lamport論理時計は、実時刻を諦め、**イベントの因果関係（happens-before, →）**だけを単調増加カウンタで表す。
ルールは3つだけ：①ローカルイベントで +1、②送信時に +1 してその値をメッセージに添付、③受信時に max(自分, 受信値)+1。
性質は a → b ならば C(a) < C(b)（因果は時刻の大小で保存）。ただし逆は不成立：C(a)<C(b) でも並行のことがある。並行を見抜くにはベクトル時計が要る。

問題設定 ── happens-before という順序

物理時計が使えない（物理時計とクロック同期（NTP））以上、「実際に何時か」ではなく「何が何に影響しえたか」で順序を定義します。Lamport の happens-before（→） の定義：

同じプロセス内で a が b より前なら a → b
a が「送信」、b がその「受信」なら a → b
推移律：a → b かつ b → c なら a → c

どちらでもない2イベントは 並行（concurrent, a ∥ b）。並行とは「互いに影響しえなかった」という意味です。

アルゴリズム ── 3つのルール

各プロセスは整数カウンタ L を1つ持ちます。

ローカルイベント:   L = L + 1
メッセージ送信:     L = L + 1; メッセージに ts = L を添付
メッセージ受信(ts): L = max(L, ts) + 1

sequenceDiagram
    participant P1
    participant P2
    participant P3
    Note over P1: a (L=1)
    P1->>P2: m1 (ts=2)
    Note over P2: b (L=1)
    Note over P2: recv m1 -> L=max(1,2)+1=3
    P2->>P3: m2 (ts=4)
    Note over P3: c (L=1)
    Note over P3: recv m2 -> L=max(1,4)+1=5

具体例 ── 因果連鎖でカウンタが伝播する（実機）

ラボ 02-02_lamport_clock.py を実行した結果：

== 各プロセスのイベント列 (Lamport時刻, ラベル) ==
P1 [(1, 'a'), (2, 'send:m1->P2')]
P2 [(1, 'b'), (3, 'recv:m1<-P1'), (4, 'send:m2->P3')]
P3 [(1, 'c'), (5, 'recv:m2<-P2')]

== happens-before の確認 ==
a(送信前) のLamport時刻 = 1
P3最終受信 r のLamport時刻 = 5
a -> ... -> r が因果連鎖。C(a)=1 < C(r)=5 を満たす: True

P1のイベント a（時刻1）から、送信→受信→送信→受信と因果が連鎖し、P3の最終受信は時刻5。因果のある2点では必ず時刻が増えています。一方、P2 の b（時刻1）と P3 の c（時刻1）は同じ値だが並行——Lamport時刻だけ見ると同値で、前後すら付きません。

正しさの観点 ── 何が言えて、何が言えないか

安全性（clock condition）：a → b ならば C(a) < C(b)。因果のある順序は決して逆転しない。
全順序化：同値のときプロセスIDで決定的にタイブレークすれば、全イベントに矛盾しない全順序を付けられる（相互排他やトータルオーダー配信に使える）。
言えないこと：C(a) < C(b) から a → b は導けない。Lamportは並行を因果と区別できない（一方向の含意のみ）。

a \to b \;\Rightarrow\; C(a) < C(b) \quad(\text{逆は成り立たない})

なぜこの設計か（直観）

max(自分, 受信)+1 がキモ。受信側は「相手がそこまで進んでいた」事実を取り込み、自分を必ずそれ以上に進める。だから因果の下流は必ず大きな値になる。実時刻を見ず、メッセージの流れ＝因果だけを数で追いかけているわけです。

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

「Lamport時刻が小さい＝先に起きた」→ 並行なら無意味。小さくても影響関係は無いかもしれない。
「同じLamport時刻＝同時刻」→ 単に並行（順序が付かない）なだけ。実時刻の同時性ではない。
「全順序が付くなら因果も完全に分かる」→ 全順序は便宜的なタイブレーク込み。因果そのものを知りたいならベクトル時計。
「受信で +1 を忘れてもいい」→ 忘れると因果が逆転しうる（安全性が壊れる）。

対応ラボ

distributed-systems-study/labs/02-02_lamport_clock.py（3プロセスの因果連鎖で C(a)<C(r) を確認済み）。