非同期分散システムにおける論理時刻

『Distributed Algorithms for Message-Passing Systems』第七章「Logical Time in Asynchronous Distributed Systems」にて紹介されている論理時刻の要約です。

概要

time-free な非同期分散システムで、どのように時刻を扱うかという話。
分散実行の因果関係を反映した論理時刻を非同期分散システムに持ち込む方法が紹介されている。
因果関係を反映した論理時刻とはつまり、原因となるイベントの発生時刻が結果となるイベントのの発生時刻より小さくなるような時刻体系のことである。

『Distributed Algorithms for Message-Passing Systems』では以下の3つの論理時刻が紹介されている。

• Linear Time
• Vector Time
• Matrix Time

Linear(Scalar) Time

単調増加する数値を用いた論理時刻。

Linear(Scalar) Clock の実装方法

各プロセスは初期値0の数値 $clock_i$ を持ち、イベント発生時に以下のように更新される。

• 内部イベント発生時
  • $clock_i$ をインクリメントする
• 送信イベント発生時
  • $clock_i$ をインクリメントする
  • 送信メッセージに $clock_i$ を添付する
• 受信イベント発生時
  • $clock_i = max(clock_i, 受信メッセージに添付されている時刻) + 1$

性質

• $\forall e_1, e_2: (e_1 \xrightarrow{ev} e_2) \Rightarrow date(e_1) < date(e_2)$
  • イベントが発生する度にクロックが増加するため、因果パスを反映する
    • $date(e)$ は $e$ が終端となる因果パスのうち、最も長いものの長さと一致する
  • $\therefore (date(e_1) >= date(e_2)) \Rightarrow \lnot (e_1 \xrightarrow{ev} e_2)$
  • $\therefore (date(e_1) = date(e_2)) => (e_1 || e_2)$
• $(date(e_1) < date(e_2)) => e_1 \xrightarrow{ev} e_2$ は成り立たないので注意

タイムスタンプと全順序

• タイムスタンプ 〈h, i〉 を定義
  • h はイベントの発生時刻
  • i はプロセス識別子
  • $〈h, i〉 < 〈k, j〉 = (h < k) \lor ((h = k) \land (i < j))$
• タイムスタンプを用いて、イベント同士の全順序関係を表現することができる
  • $e_1 \mapsto e_2 = 〈h, i〉 < 〈k, j〉$
    • h, k は Linear Time であるため、イベントの因果順序を反映する
    • プロセス識別子は重複しないので、全イベントに対して全順序が成り立つ
  • システムがこの全順序に従う場合、時刻からイベントの依存関係を判定することができないという Linear Time の欠点を無視することができる

Vector Time

各プロセスが生成したイベントの数を追跡する論理時刻。

Vector Clock の実装方法

各プロセスは $vc_i[1..n]$ を持つ。n は参加プロセスの数である。各要素には以下の値が格納される(初期値は0)。

• $vc_i[i]$
  • 自分自身が生成したイベントの数
• $vc_i[j]$
  • $p_i$ が把握している「$p_j$ が生成したイベントの数」
  • $p_i$ が $e$ を生成した直後の $vc_i[j]$ は、$e$ の因果過去に属するイベントのうち、$p_j$ が生成したものの数に一致する

$vc_i$ はイベント発生時に以下のように更新される。

• 内部イベント発生時
  • $vc_i[i]$ をインクリメントする
• 送信イベント発生時
  • $vc_i[i]$ をインクリメントする
  • 送信メッセージに $vc_i[1..n]$ を添付する
• 受信イベント発生時
  • $vc_i[i]$ をインクリメントする
  • $vc_i[1..n] = max(vc_i[1..n], 受信メッセージに添付されている時刻)$
    • $max(v1, v2) = [max(v1[1], v2[1]), …, max(v1[j], v2[j]), …, max(v1[n], v2[n])]$

性質

• 以下の比較が $vc1 = date(e_1)$, $vc2 = date(e_2)$ において成り立つとする
  • $vc1 <= vc2 = (\forall k \in ｛1, …, n｝: vc1[k] <= vc2[k])$
  • $vc1 < vc2 = (vc1 <= vc2) \land (vc1 \neq vc2)$
  • $vc1 || vc2 = \lnot(vc1 <= vc2) \land \lnot(vc2 <= vc1)$
• Vector Time の大小関係は、因果先行関係に完全に一致する
  • $\forall e_1, e_2: e_1 \xrightarrow{ev} e_2 \Leftrightarrow date(e_1) < date(e_2)$
  • $\forall e_1, e_2: e_1 || e_2 \Leftrightarrow date(e_1) || date(e_2)$

Matrix Time

各プロセスが把握している各プロセスが生成したイベントの数を追跡する論理時刻。

Matrix Clock の実装方法

各プロセスは $mc_i[1..n, 1..n]$ を持つ。各要素には以下の値が格納される(初期値は0)。

• $mc_i[i, 1..n]$
  • Vector Clock と同等の情報を持つ
• $mc_i[j, k]$
  • $p_i$ が把握している「$p_j$ が把握している「$p_k$ が生成したイベントの数」」

$mc_i$ はイベント発生時に以下のように更新される。

• 内部イベント発生時
  • $mc_i[i, i]$ をインクリメントする
• 送信イベント発生時
  • $mc_i[i, i]$ をインクリメントする
  • 送信メッセージに $mc_i[1..n, 1..n]$ を添付する
• 受信イベント発生時(受信メッセージに添付されている時刻を $mc$ とする)
  • $mc_i[i, i]$ をインクリメントする
  • $mc_i[i, 1..n] = max(mc_i[i, 1..n], mc[j, 1..n])$
  • $mc_i[k, l] = max(mc_i[k, l], mc[k, l])$
    • $1 <= k <= n, 1 <= l <= n$ を満たすすべての $k, l$ に対して

性質

• 「特定のプロセスが x 個のイベントを生成したことを、全プロセスが把握したこと」をローカル情報のみで確認できる
  • $min(mc_i[1..k], …, mc_i[n, k]) = x$ の場合
    • $p_k$ が x 個のイベントを生成したことを、全プロセスが知っていることになる
  • 古いイベントを破棄するのに利用可能
    • 例えば、ブロードキャストしたメッセージの再送用バッファを用意するとする
    • 古いメッセージはバッファから破棄したいが、全プロセスがそのメッセージを受信するまでは破棄できない
    • Matrix Clock を用いることで、全プロセスがメッセージを受信したことを確認できる