3 分散システムのフォールトトレランス 分散システム Distributed Systems Networkを通して通信可能な複数のプロセス(process)から構成 プロセス≒ プロセッサ (processor) ノード (node) サイト (site)

3.1 分散システムのモデル 3.1.1 基本モデル プロセスPiは局所時計をもつ プロセスは以下のものを持たない Ci(t) = 実時刻tでの局所時計の値 プロセスは以下のものを持たない Shared memory Global Clock

3.1.3 故障モデル Fault Model クラッシュ故障 (Crash Fault) 故障したプロセスは停止 オミッション故障 (Omission Fault) Crashもしくは，メッセージの送信，受信を失敗する可能性 ビザンチン故障 (Byzantine Fault) 任意の動作 Byzantine Faults Omission Faults Crash Faults

3.1.2 同期・非同期 同期システム 条件 非同期システム 1命令の実行時間に上限が存在し，既知 メッセージ遅延に上限が存在し，既知 局所時計のドリフト率rが存在し，既知 非同期システム 同期システムでないシステム P1 t P2 メッセージ遅延

時計同期 Clock Synchronization 同期システムでは時計同期により | Ci(t) – Cj(t)| ≤ e Ci(t) r dCi (t) dt - 1 ≤ r r 1-r 通常定数ρは10-5程度 T 1

同期ラウンドモデル 受信→処理→送信 P1 P2 P3 t ラウンドi-1 ラウンドi ラウンドi+1

3.1.4 論理時計 Event(イベント)のOrdering(順序付け) 必要性 困難さ AよりBが後だと判定したい P1 共通のClockがない メッセージ遅延，プロセス実行速度が可変 AよりBが後だと判定したい P1 P2 A B P3

因果関係 (Happened-before relation, causal relation) 1~3を満たす最小の関係(→で表記) 同じプロセスでaがbより先に起こったならa→b 同じメッセージについてaが送信，bが受信ならa→b a→bかつb→cならばa→c e11 → e12 e21 → e22 e11 e12 e21 → e23 P1 e22 → e23 e11 → e22 e21 → e12 P2 e21 e22 e23 e11 → e23

因果関係 Relation (関係) ・・・ 要素のtuple(組)の集合 strict partial order relation (強半順序関係) (a, a)  R が成り立たない (irreflexivity, 非反射律) (a, b)  R  ¬(b, a)  R (antisymmetry 反対称律) (a, b)  R, (b, c)  R  (a, c)  R (transitivity, 推移律) Partial order relation (半順序関係) (a, a)  R (reflexivity, 反射律) a≠b, (a, b)  R  ¬(b, a)  R (antisymmetry 反対称律)

論理時計(by L. Lamport) Logical Clock (論理時計) 整数LCi：各プロセスPiのevent aの論理時計の値 因果関係に矛盾しない時間 a,b, a→b ならば LCi(a) < LCj(b) e11 e12 e13 e14 e15 e16 e17 P1 (1) (2) (3) (4) (5) (6) (7) Clock values (1) (2) (3) (4) (7) P2 e21 e22 e23 e24 e25

論理時計 ルール 同じプロセスでa，bが連続して起こったら LCi(b) := LCi(a) + 1 メッセージには送信イベントの時刻をtimestamp (時刻印) tmとして付加 受信イベントaは，LCi(a) := max(LCi(a), tm + 1) a,b, a→b ならば LCi(a) < LCj(b) !? e11 e12 e13 e14 e15 e16 e17 P1 (1) (2) (3) (4) (5) (6) (7) Clock values ts=6 ts=2 ts=2 ts=4 (1) (2) (3) (4) (7) P2 e21 e22 e23 e24 e25

全順序関係の設定 同じ論理時計値を持つイベントの解消 Total order relation (全順序関係) (a, a)  R (reflexivity, 反射律) (a, b)  R, (b, a)  R  a = b (antisymmetry 反対称律) (a, b)  R, (b, c)  R  (a, c)  R (transitivity, 推移律) a,b, (a, b)  Rまたは (b, a)  R (totalness, 完全律) Logical Clock + プロセスID e11 e12 e13 e14 e15 e16 e17 P1 (1) (2) (3) (4) (5) (6) (7) (1.1) (2.1) (3.1) (4.1) (5.1) (6.1) (7.1) Clock values (1.2) (2.2) (3.2) (4.2) (7.2) (1) (2) (3) (4) (7) P2 e21 e22 e23 e24 e25

ベクトル時計 論理時計では， ベクトル時計 a→b ならば LCi(a) < LCj(b) しかし，「LCi(a)<LCj(b)ならばa→b」は，必ずしも成り立たない ベクトル時計 a→b  LCi(a) < LCj(b) (1,0,0) (2,0,0) (3,4,1) P1 e11 e12 e13 (0,1,0) (2,2,0) (2,3,1) (2,4,1) P2 e21 e22 e23 e24 (0,0,1) (0,0,2) P3 e31 e32 時間