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 Faults  Crashもしくは，メッセージの Omission Faults 送信，受信を失敗する可能性  ビザンチン故障 (Byzantine Fault)  任意の動作 Byzantine Faults 3.1.2 同期・非同期同期システム  条件  1命令の実行時間に上限が存在し，既知  メッセージ遅延に上限が存在し，既知  局所時計のドリフト率rが存在し，既知 P1 t P2 0  メッセージ遅延非同期システム  同期システムでないシステム時計同期 Clock Synchronization  ドリフト率r dCi (t) -1  r dt r r Ci(t) 1-r 通常定数ρは10-5程度  1 同期システムでは時計同期により  | Ci(t) – Cj(t)|  e T 同期ラウンドモデル受信→処理→送信 P1 P2 P3 ラウンドi-1 t ラウンドi ラウンドi+1 3.1.4 論理時計  Event(イベント)のOrdering(順序付け)  必要性 AよりBが後だと判定したい P1 P2 P3 B A  困難さ共通のClockがない  メッセージ遅延，プロセス実行速度が可変  因果関係 (Happened-before relation, causal relation)  1~3を満たす最小の関係(→で表記) 同じプロセスでaがbより先に起こったならa→b 2. 同じメッセージについてaが送信，bが受信なら a→b 3. a→bかつb→cならばa→c e11 → e12 1. P1 P2 e11 e21 e12 e22 e23 e21 → e22 e21 → e23 e22 → e23 e11 → e22 e21 → e12 e11 → e23 因果関係   Relation (関係) ・・・要素のtuple(組)の集合 strict partial order relation (強半順序関係) a)  R が成り立たない (irreflexivity, 非反射律)  (a, b)  R  ¬(b, a)  R (antisymmetry 反対称律)  (a, b)  R, (b, c)  R  (a, c)  R (transitivity, 推移律)  (a,  Partial order relation (半順序関係) a)  R (reflexivity, 反射律)  a≠b, (a, b)  R  ¬(b, a)  R (antisymmetry 反対称律)  (a, b)  R, (b, c)  R  (a, c)  R (transitivity, 推移律)  (a, 論理時計(by L. Lamport)  Logical Clock (論理時計)  整数LCi：各プロセスPiのevent aの論理時計の値  因果関係に矛盾しない時間  a,b, a→b ならば LCi(a) < LCj(b) P1 e11 e12 e13 e14 (1) (2) (3) (4) e15 e16 (5) (6) e17 (7) Clock values P2 (1) (2) (3) e21 e22 e23 (4) e24 (7) e25 論理時計  ルール同じプロセスでa，bが連続して起こったら LCi(b) := LCi(a) + 1 2. メッセージには送信イベントの時刻をtimestamp (時刻印) tmとして付加 3. 受信イベント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. (1) ts=2 ts=2 (1) (2) (3) (5) (6) ts=6 ts=4 (4) e21 e22 e23 e24 Clock values P2 (2) (3) (4) (7) e25 (7) 全順序関係の設定  同じ論理時計値を持つイベントの解消  Total  (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, 完全律)    order relation (全順序関係) Logical Clock + プロセスID P1 Clock values P2 e11 e12 e13 e14 (1) (1.1) (2) (3) (4) (2.1) (3.1) (4.1) (1.2) (1) (2.2) (2) e21 e22 e15 e16 (3.2) (3) e23 (5) (6) (6.1) (5.1) (4.2) (4) e24 e17 (7) (7.1) (7.2) (7) e25 ベクトル時計  論理時計では，ならば LCi(a) < LCj(b)  しかし，「LCi(a)<LCj(b)ならばa→b」は，必ずしも成り立たない  a→b  ベクトル時計  a→b  LCi(a) < LCj(b) (1,0,0)(2,0,0) P1 e P2 P3 11 (3,4,1) e12 e13 (0,1,0) (2,2,0)(2,3,1)(2,4,1) e21 e22 e23 e24 (0,0,1) (0,0,2) e31 e32 時間