耐故障アルゴリズム

故障 Initially dead (最初から動いてない) Crash (あるところから動かなくなる) Byzantine (めちゃくちゃな動きをする) Initially dead < Crash < Byzantine

耐故障: 基本アイデア 冗長性 多数決(合意) やり直し checkpointing, logging self stabilization

アルゴリズムの基準 t-XXX-robust t個のXXXなプロセスの存在下で正しく動く 有限ステップで終了

Crashのモデル化 プロセスPがcrash : Pのイベントが最初/途中から実行されない(神様によって選択されない) cf. fairness 実行可能なイベント(e.g., メッセージ受信)はいつか選択される (意地悪な)神様の選択の余地が広がったことに対応する

頭の体操 そもそも正確な“Crash Detector”は存在するか? プロセスP (正常), Q (may crash). 初期値 v = 0 有限ステップ以内に終了し， vP = vQ = 1 またはvP = 0, vQ = 0 non-trivial (常に同じ答えを返すアルゴリズムではない)

不可能の証明 (0, 0) (1, 1)

注 0-decided (vP, vQ) = (0, 0)にのみ到達可能 以後，以下の記号で表す

次のような場所が存在 適当な0-decidedと1-decidedをとる decided …

ケース1 e by Pとe’ by Qは合流する(非同期システムの性質) e by P e’ by Q OOPS! e by P

ケース2 以下の黄色と青から最初に可能なPの遷移がないとすると，白は最終状態でもある．そこでvPは???という話になる．よってそのようなPの遷移があるが，以下の図により矛盾 e by Q e’’ by P OOPS! e’ by Q

ケース3 Qのcrashにrobustより， vQ = ? vQ = 1 e by P vQ = OOPS! e’ by P

合意問題 Nプロセス 要請 変数 v (初期値不明) 有限ステップ以内に停止 停止状態で正常なプロセスはvをひとつの値に合意 non-trivial (あるひとつの値に常に合意するアルゴリズムは排除)

合意問題の重要性 「冗長な計算」の基礎 commit-abort : 全員commitまたは全員abort 多数決: 正しいプロセス間で値を合意して，正しい答えを得る 実際これが出来れば，任意のアルゴリズムがtrivialに「同じくらい耐故障」にできる 「Pが正常でない」とP以外が合意したらやりなおす commit-abort : 全員commitまたは全員abort

(悲しい)事実 非同期メッセージパッシングシステムでは，1-crash-robustな合意アルゴリズムは存在しない

bi-valent (0と1両方に到達可能)な初期状態の存在 ただひとつのプロセス(P)の状態だけが違う Pのcrashにrobustより，Pの遷移無しで最終状態に到達する．このときもちろん到達可能な状態は一致する．

以後の議論は先のP, Qの場合とほとんど同じ

次のような場所が存在 適当な0-decidedと1-decidedをとる decided …

ケース1 e by Pとe’ by Qは合流する(非同期システムの性質) e by P e’ by Q OOPS! e by P

ケース2 白からP以外の遷移がないとする．すると白は最終状態でもありそこでP以外は合意している．0に合意しているとすると，青でもP以外は0に合意している．青から1-decidedなconfigurationに至るためにはP以外すべてのプロセスの遷移を一度は実行せねばならず，これはcrash robustに反する e by P e’’ by Q OOPS! e’ by P

確率的な合意アルゴリズム 確率1で停止(t -> ∞ => とまる確率 -> 1) 停止時には確実に合意している non-trivial

簡単のため1-crashで考える 一般にはt (< N/2)-crash robustが可能 基本アイデア: 多数決 repeat { 全員に向かって投票; N – 1人の返事を集計; 過半数(> N/2)で当確 (以降の投票に「当確マーク); そうでなければ，次は半数以上の方に投票(同数なら1)．}

注意 N個目の返事を待ってはいけない(crash時にdeadlock)．N – 1個で判断しなくてはいけない crashがない間の“early decision” (当選確実)が本質的に難しい部分

ある回の投票が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を受け取る

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> 1人: <r, 1, 1> x61 => <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> 1人: <r+1, 0, 1> x61 => <r+2, 0, 61>