Download presentation
Presentation is loading. Please wait.
1
耐故障アルゴリズム
2
故障 Initially dead (最初から動いてない) Crash (あるところから動かなくなる)
Byzantine (めちゃくちゃな動きをする) Initially dead < Crash < Byzantine
3
耐故障: 基本アイデア 冗長性 多数決(合意) やり直し checkpointing, logging self stabilization
4
アルゴリズムの基準 t-XXX-robust t個のXXXなプロセスの存在下で正しく動く 有限ステップで終了
5
Crashのモデル化 プロセスPがcrash : Pのイベントが最初/途中から実行されない(神様によって選択されない)
cf. fairness 実行可能なイベント(e.g., メッセージ受信)はいつか選択される (意地悪な)神様の選択の余地が広がったことに対応する
6
頭の体操 そもそも正確な“Crash Detector”は存在するか? プロセスP (正常), Q (may crash).
初期値 v = 0 有限ステップ以内に終了し， vP = vQ = 1 またはvP = 0, vQ = 0 non-trivial (常に同じ答えを返すアルゴリズムではない)
7
不可能の証明 (0, 0) (1, 1)
8
注 0-decided (vP, vQ) = (0, 0)にのみ到達可能
以後，以下の記号で表す
9
次のような場所が存在 適当な0-decidedと1-decidedをとる decided …
10
ケース1 e by Pとe’ by Qは合流する(非同期システムの性質) e by P e’ by Q OOPS! e by P
11
ケース2 以下の黄色と青から最初に可能なPの遷移がないとすると，白は最終状態でもある．そこでvPは???という話になる．よってそのようなPの遷移があるが，以下の図により矛盾 e by Q e’’ by P OOPS! e’ by Q
12
ケース3 Qのcrashにrobustより， vQ = ? vQ = 1 e by P vQ = OOPS! e’ by P
13
合意問題 Nプロセス 要請 変数 v (初期値不明) 有限ステップ以内に停止 停止状態で正常なプロセスはvをひとつの値に合意
non-trivial (あるひとつの値に常に合意するアルゴリズムは排除)
14
合意問題の重要性 「冗長な計算」の基礎 commit-abort : 全員commitまたは全員abort
多数決: 正しいプロセス間で値を合意して，正しい答えを得る 実際これが出来れば，任意のアルゴリズムがtrivialに「同じくらい耐故障」にできる 「Pが正常でない」とP以外が合意したらやりなおす commit-abort : 全員commitまたは全員abort
15
(悲しい)事実 非同期メッセージパッシングシステムでは，1-crash-robustな合意アルゴリズムは存在しない
16
bi-valent (0と1両方に到達可能)な初期状態の存在
ただひとつのプロセス(P)の状態だけが違う Pのcrashにrobustより，Pの遷移無しで最終状態に到達する．このときもちろん到達可能な状態は一致する．
17
以後の議論は先のP, Qの場合とほとんど同じ
18
次のような場所が存在 適当な0-decidedと1-decidedをとる decided …
19
ケース1 e by Pとe’ by Qは合流する(非同期システムの性質) e by P e’ by Q OOPS! e by P
20
ケース2 白からP以外の遷移がないとする．すると白は最終状態でもありそこでP以外は合意している．0に合意しているとすると，青でもP以外は0に合意している．青から1-decidedなconfigurationに至るためにはP以外すべてのプロセスの遷移を一度は実行せねばならず，これはcrash robustに反する e by P e’’ by Q OOPS! e’ by P
21
確率的な合意アルゴリズム 確率1で停止(t -> ∞ => とまる確率 -> 1) 停止時には確実に合意している
non-trivial
22
簡単のため1-crashで考える 一般にはt (< N/2)-crash robustが可能 基本アイデア: 多数決
repeat { 全員に向かって投票; N – 1人の返事を集計; 過半数(> N/2)で当確 (以降の投票に「当確マーク); そうでなければ，次は半数以上の方に投票(同数なら1)．}
23
注意 N個目の返事を待ってはいけない(crash時にdeadlock)．N – 1個で判断しなくてはいけない
crashがない間の“early decision” (当選確実)が本質的に難しい部分
24
ある回の投票がa個の0とb個の1だったとする(a + b = N)．このとき各プロセスは
{ a, a – 1 }個の0をうけとる 言い換え，今x個の0とy個の1 (x + y = N – 1)を受け取ったとする 真実は，a = { x, x + 1 } 他のプロセスは{ x – 1, x, x + 1 }個の0を受け取る
25
Tel p455のアルゴリズムで決まらない場合(40 crash, N=101)
round rのshout: <r, 0, 61> x 1 + <r, 1, 1> x 100 round rのreceive: 100人: <r, 0, 61> x1 + <r, 1, 1> x60 => <r + 1, 0, 1> 人: <r, 1, 1> x => <r + 1, 1, 61> round r + 1のshout: <r+1, 0, 1> x100 + <r+1, 1, 61> x1 round r + 1のreceive: 100人: <r+1, 1, 61> x1 + <r+1, 0, 1> x60 => <r+2, 1, 1> 人: <r+1, 0, 1> x => <r+2, 0, 61>
Similar presentations
