Distributed Algorithm 輪講 13 – 14 章

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 する
The hierarchy of fault models
1. Initially dead processes
2. Process の crash
3. Omission Failure

Fault tolerance
易
プロセスが、アルゴリズムの途中を抜かして実
行を続けてしまう。
4. Byzantine behavior
難
Failure について、 1.⊆2.⊆3.⊆4.
例: omission は、Byzantine の特別な場合
例: Byzantine-robust なアルゴリズムは、omission-robust
Decision Problems
Decision に対する 3 つの要求

Termination
 正しいプロセスは、必ず結果を output する。

Consistency
 全てのプロセスの output 間で、一貫性がとれて
いること(後述)

Non-triviality
 他のプロセスと通信せず、固定された出力をする
アルゴリズムは考えない
Decision Problems - Consistency
例


Consensus problem では、全ての正しいプロ
セスの出力が一致
Election problem では、一つのプロセスのみ
出力 “1”、他のプロセスの出力 “0”
Stabilizing Algorithm
どんな Failure がどれだけの数起こっても
OK
しかし、正しい振る舞いに戻るのにいくらか
時間がかかる。
Robust v.s. Stabilizing
Stabilizing

例えば、宇宙船に大量の宇宙線がきて、
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
γ
T
1-valent
T 0-valent
T : 多くとも t 個のプロセス
t 個までは、 fault が起こっても大丈夫
There is no reachable fork.
Bivalent configuration for A
プロセス p のみ異なる
δ ・・・・・・・ γ γ・・・・・・δ
0
0
1
1
p が動かない場合
1-crash-robust なので、
γとγは同じ
0
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
1. 各プロセスは、自分の存在を broadcast
2. 他のプロセスが１. で発したメッセージを
L個受け取り、自分のsuccessor に加える。
P の successor
(L 個)
p
q1
q2
Algorithm 14.1
3. 生きているプロセス同士、互いに自分のsuccessor
を教えあう。
4. 3.の情報をもとに、グラフ G を構築。
2L > N なので、グラフ G には、knot がただ一つ
存在する(これを K とする)。
Knot :
二個以上のnode からなり、
外への edge を含まない
強連結な component
knot
Election,consensus
K の中から例えば、ID の一番大きいもの
をリーダーに選ぶようにすれば、 election
が完成。
全体の決定をリーダーに任せるようにすれ
ば、consensus もできる。
Consensus under Crash Model
Crash Model では、全体の決定をリーダー
に任せるようにしても、リーダーが落ちる可
能性があるので、ダメ。
さらに言うと、 Crash Model では、Election
自体も不可能。
14.3 Deterministically
Achievable Cases
よりプロセス間の連携が弱い問題では、
Deterministic に解けるものもある。
この章では、その中の、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
{x3},c3 = 0
{x2}, c2 = 0
アルゴリズムの動作例
{x1},c1 = 0
{x2}, c2 = 0
{x1},c1+= 1(c1 = 1) {x1,x2}, c2 := 0
{x1}
{x1}
{x1}
{x3}, c3 = 0
{x3,x1},c3 := 0
アルゴリズムの動作例
{x1},c1 = 1
{x1,x2},c1 := 1
{x1,x2}
{x1,x2}, c2 = 0
{x1,x2}, c2 += 1 (c2 = 1)
{x1,x2}
{x1,x2}
{x3,x1},c3 = 0
壊れた、または、非常に遅い。
未処理タスク: shout <set,{x1,x3}>
アルゴリズムの動作例
{x1,x2},c1 = 1
{x1,x2} , c2 = 1
{x1,x2},c1 += 1(c1 = 2) {x1,x2} , c2 += 1 (c2 = 2)
{x1,x2}
決定！
{x1,x2}
決定！
{x1,x2}
{x3},c3 = 0
注.
決定したプロセスも、そのまま停止せず、
実行を続ける。

非常に遅いプロセスがある場合もあるので、
必要
Algorithm 14.2 を見る限り、各プロセスが
t をどうやって知るのかは謎。
アルゴリズムの動作例
{x1,x2},c1 = 2
{x1,x2} , c2 =2
{x3},c3 = 0
ここで、プロセス 3 が続きを実行し始めた場合も、
1,2 は c1 := 0,c2 := 0 からやり直し、
また別の stable set に到達。

Download Report