Distributed Algorithm 輪講 13 章 米澤研究室修士２年 小林　義徳

Why Fault-tolerant Algorithm? 単一プロセッサシステム+逐次アルゴリズム fault-tolerant にできることが限られている。 分散システム ～ partial-failure property 故障が起こっても、一部のみ影響を受ける 全体の故障より、段階的な悪化が望まれる。 故障したコンピュータの仕事を、残りの部分が代わりにやることが必要になる。

Fault tolerance Robust Algorithm Stabilizing Algorithm 部分的、半永久的故障に耐性 全体的、一時的故障に耐性

Robust Algorithm 実行の途中で 故障があっても、全体としてずっと正しい振る舞いをしつづける。 以下、プロセスのみが故障し、通信路は常に正常であるとする。 しかし、failure 数の上限がある Failure model が正確に分かるべし

この本でのFailure Model(p.429) Initially dead processes 1 step も local アルゴリズムを実行しない Process の crash 有限 step 正しく実行し、その後のステップを実行しない Byzantine behavior Local algorithm とは違う、デタラメなステップを実行 Byzantine process は、デタラメなメッセージをsend する byzantine 【形】 複雑（怪奇）な、陰険な、込み入った

The hierarchy of fault models Fault tolerance Initially dead processes Process の crash Omission Failure プロセスが、アルゴリズムの途中を抜かして実行を続けてしまう。 Byzantine behavior 易 難 例: Initially dead は、Crash の特別な場合 Crash は、Byzantine behavior の特別な場合 Failure について、 1.⊆2.⊆3.⊆4. 例: omission は、Byzantine の特別な場合 例: Byzantine-robust なアルゴリズムは、omission-robust

Decision Problems Decision に対する 3 つの要求 Termination Consistency 正しいプロセスは、必ず結果を output する。 Consistency 全てのプロセスの output 間で、一貫性がとれていること(後述) Non-triviality 他のプロセスと通信せず、固定された出力をするアルゴリズムは考えない

Decision Problems - Consistency 例 Consensus problem では、全ての正しいプロセスの出力が一致 Election problem では、一つのプロセスのみ出力 “1”、他のプロセスの出力 “0”

Stabilizing Algorithm どんな Failure がどれだけの数起こっても OK しかし、正しい振る舞いに戻るのにいくらか時間がかかる。

Robust v.s. Stabilizing Stabilizing Robust 例えば、宇宙船に大量の宇宙線がきて、 global configuration が一時的に駄目になっても、立ち直れる。 Robust 一部の限られた要素が永久に故障 一時的なサービスの停止が許されない場合に使われる。

この本に載っていないこと Refinement of synchrony assumptions Determination of solvable tasks Complexity of fault tolerance Dynamic systems and group membership Communication using shared variables Wait-free synchronization

Overview of Chapter 14 - 16 14 章: Asynchronous system での Robustness について。 15 章: Synchronous system,Robustness Synchronous system では、確実な Failure Detection ができ、より高いレベルの robustness が達成可能。 16 章: Failure Detection

Distributed Algorithm 輪講 14 章 米澤研究室修士２年 小林　義徳

予備知識 Consensus Problem Election Problem 全てのプロセスの決定が一致 プロセスの中から、リーダーを一つ選出

14 章の流れ 14.1 Impossibility of Consensus いくらか条件を緩めることにより、 解ける問題もある。 非同期、決定的 1-crash-robust consensus protocol ない。 いくらか条件を緩めることにより、 　解ける問題もある。

14.2 ,14.3 14.2 Fault を Initially dead process に制限することにより、consensus と election ができるようになる。 14.3 consensus よりプロセス間の連携が弱い問題で、crash model でも解けるものがある。 例: renaming

14.4 ,14.5 14.4　Probabilistic algorithm を用いることで、Byzantine failure の存在下でも OK なように、termination requirement を弱められる。 14.5 与えられたプロセスが正しい場合、Termination を要求することで、Byzantine-robust も可能になる

t-robust protocol における fork γ 1-valent T 0-valent T T : 多くとも t 個のプロセス t 個までは、 fault が起こっても大丈夫 There is no reachable fork.

Bivalent configuration for A プロセス p のみ異なる δ ・・・・・・・ γ γ・・・・・・δ 1 1 p が動かない場合 1-crash-robust なので、 γとγは同じ 1 0-decided 1-decided

No 1-crash-robust, deterministic consensus algorithm 何かイベントの列があったとき、 bivalent なまま もう 1ステップ実行できる いつまでも決定を下さない、fair execution が作れてしまう。 1-crash-robust, deterministic consensus algorithm は、ない。

14.2 Initially Dead Process Fault を Initially Dead に限ると、consensus , election ができる。 Resilience は、(N-1)/2 (端数は切り捨て)

Election の流れ 各プロセスが、生きているプロセスの集合を Algorithm 14.1 によって取得し、その中で最大の ID を持つものをリーダーとして選出 以下、L = (N + 1)/2 (N が奇数) N/2 + 1 (N が偶数) とする。 少なくとも L 個のプロセスが生きている場合、

Algorithm 14.1 各プロセスは、自分の存在を broadcast 他のプロセスが １. で発したメッセージを L個受け取り、自分のsuccessor に加える。 P の successor (L 個) p q1 q2

Algorithm 14.1 生きているプロセス同士、互いに自分のsuccessor を教えあう。 3.の情報をもとに、グラフ G を構築。 2L > N なので、グラフ G には、knot がただ一つ存在する(これを K とする)。 Knot : 二個以上のnode からなり、外への edge を含まない 強連結な component knot

Election,consensus K の中から例えば、ID の一番大きいものを リーダーに選ぶようにすれば、 election が完成。

Consensus under Crash Model さらに言うと、 Crash Model では、Election 自体も不可能。

14.3 Deterministically Achievable Cases この章では、その中の、Renaming アルゴリズムを解説する。

Renaming : Algorithm 14.2 問題 : 各プロセスの古い名前を新しい名 前に付け替える 問題 : 各プロセスの古い名前を新しい名 　　 前に付け替える 古い名前(namespace 無制限) 新しい名前(namespace が限られている) ただし、古い名前、新しい名前とも、全プロセスで互いに異なる。 プロセス p の入力 : 古い名前 　　　出力 : 新しい名前 メッセージの複雑さは、O(N3)

アルゴリズム概要 初期設定 アルゴリズム Vp = {xp},cp = 0 無限に V をreceive receive した V に応じて、 Vp,cp を更新 shout <set,Vp>

アルゴリズムの動作例 {x1},c1 = 0 {x2}, c2 = 0 {x3},c3 = 0

アルゴリズムの動作例 {x1},c1 = 0 {x1},c1+= 1(c1 = 1) {x2}, c2 = 0 {x1,x2}, c2 := 0 {x1} {x1} {x1} {x3}, c3 = 0 {x3,x1},c3 := 0

アルゴリズムの動作例 {x1},c1 = 1 {x1,x2}, c2 = 0 {x1,x2}, c2 += 1 (c2 = 1) 壊れた、または、非常に遅い。 未処理タスク: shout <set,{x1,x3}>

アルゴリズムの動作例 {x1,x2},c1 = 1 {x1,x2},c1 += 1(c1 = 2) {x1,x2} , c2 = 1 決定！ {x1,x2} 決定！ {x1,x2} {x3},c3 = 0 こんどは、一番下の行の、Vp <

注. 決定したプロセスも、そのまま停止せず、実行を続ける。 非常に遅いプロセスがある場合もあるので、必要 Algorithm 14.2 を見る限り、各プロセスがt をどうやって知るのかは謎。

アルゴリズムの動作例 {x1,x2},c1 = 2 {x1,x2} , c2 =2 {x3},c3 = 0 ここで、プロセス 3 が続きを実行し始めた場合も、1,2 は c1 := 0,c2 := 0 からやり直し、 また別の stable set に到達。 こんどは、一番下の行の、Vp <