ビザンチン故障と分散制御 九州大学 システム情報科学研究院 山内由紀子

Presentation on theme: "ビザンチン故障と分散制御 九州大学 システム情報科学研究院 山内由紀子"— Presentation transcript:

1 ビザンチン故障と分散制御 九州大学 システム情報科学研究院 山内由紀子
ビザンチン故障と分散制御 九州大学　システム情報科学研究院 山内由紀子 最適化ワークショップ 2013,02,19

2 講演概要 分散システムとアルゴリズム ビザンチン合意アルゴリズム 移動ビザンチン合意アルゴリズム 今後の展開

3 分散システム 通信リンクで相互接続され， 協調動作する多数の計算機（プロセス） から成るシステム 分散させて上手く計算する
通信リンクで相互接続され， 協調動作する多数の計算機（プロセス） から成るシステム インターネット，ATM網，みどりの窓口 分子計算，膜計算，などなど 分散させて上手く計算する 並列処理 分散してしまっていても上手く計算する 分散・協調処理

4 合意問題 n人いる参加者で，1ビットについて合意したい 応用：分散データベース等の一貫性維持 各参加者は提案値∈{0, 1}を持つ
誰かの持つ値に全員で合意する 応用：分散データベース等の一貫性維持 処理速度向上，故障耐性のための冗長化，分散配置 サーバ間の一貫性維持

5 合意問題 Q： 各参加者の計算手順を考えてください n人いる参加者で，1ビットについて合意したい 応用：分散データベース等の一貫性維持
各参加者は提案値∈{0, 1}を持つ 誰かの持つ値に全員で合意する 応用：分散データベース等の一貫性維持 処理速度向上，故障耐性のための冗長化，分散配置 サーバ間の一貫性維持 分散アルゴリズム Q： 各参加者の計算手順を考えてください どんな通信（情報の送信/受信）をするか どんな情報を記録し，受信した情報と合わせて 何を計算するか

6 分散システムの難しさ (1/3) 局所性 各計算機がローカルに持つデータだけをもとに計算
通信リンクがある計算機間でのみ 計算結果を交換（送信，受信）できる

7 分散システムの難しさ (2/3) 非同期性 各計算機の計算速度，通信の遅延はばらばら スケジューラ（アドバーサリ）に対する最悪時評価

8 分散システムの難しさ (3/3) 自律適応的運用 故障耐性，自己組織化，自己最適化，等 大規模，遠隔地に広がるシステムは管理困難
計算機が多ければ，故障も発生 故障耐性，自己組織化，自己最適化，等

9 合意問題 n人いる参加者で，1ビットについて合意したい 計算手順案 各参加者は提案値∈{0, 1}を持つ 誰かの持つ値に全員で合意する
全員で (提案者, 提案値) を交換 n人ぶん集まったら，多数決/最大値/etc. 故障

10 ビザンチン合意問題 ビザンチン故障 定義 [ビザンチン合意問題] アルゴリズムに従わず，任意の動作 （停止，偽メッセージの送信，等）
アルゴリズムに従わず，任意の動作 （停止，偽メッセージの送信，等） ビザンチン故障に対する前提知識なし 定義 [ビザンチン合意問題] プロセス集合 P={P1, P2, …, Pn} の各プロセス Pi が 提案値 vi∈{0, 1} を持つ． また，合意値をただ1度だけ書き込める変数 wi を持つ． 以下の条件を満たす合意値を決定するアルゴリズムを設計せよ． （合意性）　すべての正常なプロセスは同じ値を合意値とする （停止性）　すべての正常なプロセスはいずれ合意値を決定する （妥当性）　合意値はいずれかの正常プロセスの提案値である

11 ビザンチン合意問題：ゴール 不可能性：故障プロセス数 f の上限 アルゴリズムの設計 効率性：計算時間，通信量 1 ビザンチン 1

12 3プロセス間でのビザンチン合意 アルゴリズムが存在すれば？
ビザンチン合意の難しさ 提案値の交換による 3プロセス間でのビザンチン合意 アルゴリズムが存在すれば？ C：故障 B A 1 1 1 1 A 1 C B A：故障 1 C B：故障 合意値：0 合意値：1 合意不可能

13 ビザンチン合意問題の不可能性 停止故障⊂ビザンチン故障 同期システム 定理1 (Fisher et al, 1985)
任意の通信遅延を許す非同期システムでは 1プロセスの停止故障に対しても合意問題は解けない 停止故障⊂ビザンチン故障 同期システム 各プロセスがラウンドごとに送信，受信，計算を繰り返す環境 通信遅延を無視 定理2 (Pease et al, 1980) n<3f のとき，同期システムにおいてもビザンチン合意問題は解けない

14 ビザンチン合意アルゴリズム M. Pease, R. Shostak, and L. Lamport, Reaching Agreement in the Presence of faults, J. of the Association for Computing Machinery, 27 (2), pp.228—234, 1980.

15 n>3f ならばやさしい？ 例）提案値を集めて多数決 故障プロセスが別々の値を送れば多数決が覆る事も 故障 提案値0 1 提案値1
P1 P2 P3 P4 P5 P6 P7 故障 1 提案値0 提案値1

16 目標：異なる (f+1) 人以下に中継された値を収集すれば， 正常プロセスでは提案値を復元できることを保証
アルゴリズムのアイデア 全プロセスの提案値について合意 正常プロセスに同じ （提案者，提案値）集合を持たせる 各プロセスの提案値を 様々な経路で収集 P1（自分）の提案値はbだ P1の提案値はbだ，とP2が言っている P1の提案値はbだ，とP3が言っている … P1の提案値はbだ，とP2が言っている， とP3が言っている P1 P2 P3 P4 P5 P6 P7 目標：異なる (f+1) 人以下に中継された値を収集すれば， 正常プロセスでは提案値を復元できることを保証

17 中継経路集合 Tf+1 今回使用する中継経路 アルファベット S={1, 2, …, n}
各プロセスは高々1回だけ出現 長さは(f+1)以下 アルファベット S={1, 2, …, n} P1 P2 P3 P4 P5 P6 P7 S上の同一文字が高々1回しか出現しない 長さ f+1 以下の文字列の集合 Tf+1 =

18 中継経路集合 Tf+1 (Contd.) 接頭辞の最長共通部分で木構造 Tf+1 各プロセス Pi において，x∈Tf+1 について
レベル h の頂点の子の数は n-h 各プロセス Pi において，x∈Tf+1 について ui(x) ：xの経路で伝達された値 ui(l) = vi (Pi の提案値) maji(x)：xの子の過半数値 レベル1 レベル2 レベル3 レベル0 l (空系列) 1 2 12 13 3 7 14 123 124 125 17 127

19 システムモデル再掲 同期システム：ラウンドごとに，送信，受信，計算 n プロセス中，f プロセスがビザンチン故障 ただし，n>3f
P1 P1 P2 P3 P2 P3 第1ラウンド 第2ラウンド 第3ラウンド 時刻

20 アルゴリズム ByzCons (1/2) 最初の(f+1)ラウンドは Tf+1 の値を回収 (中継経路，提案値)を交換
例) 「P1の提案値はbだ，とP2が言っている」を P3 が受信 ((1 2), b) を受信　 u3(12)=b とし，((1 2 3), b) を送信 l (空系列) 1 2 12 13 3 7 14 123 124 125 17 127 故障プロセスの判別ができなくても！

21 アルゴリズム ByzCons (2/2) Tf+1 の各頂点に中継値が入れば
葉から順番に以下の操作： x 子の過半数を超える中継値を maji(x) に入れる ( 葉では ui(x) = maji(x) ) ただし，そのような値がなければ0 最後に maji(l) に入った値を合意値 wi とする l (空系列) 1 2 12 13 3 7 14 123 124 125 17 127 故障プロセスの判別ができなくても！

22 アルゴリズムの正当性：合意性 正常プロセスの Tf+1で maj(l) が一致すれば合意
レベル1の各頂点 x について， 任意の正常プロセス i, j で maji(x)=majj(x) を示す 定義：頂点 x∈Tf+1 が値共有 すべての正常プロセス Pi, Pj で maji(x) = majj(x) 正常プロセス i 正常プロセス j l (空系列) 1 2 3 n l (空系列) 1 2 3 n

23 アルゴリズムの正当性：合意性 合意性の根拠： 正常プロセスで終了する x∈Tf+1 は値共有
正常プロセスの Tf+1で maj(l) が一致すれば合意 レベル1の各頂点 x について， 任意の正常プロセス i, j で maji(x)=majj(x) を示す 定義：頂点 x∈Tf+1 が値共有 すべての正常プロセス Pi, Pj で maji(x) = majj(x) 合意性の根拠： 正常プロセスで終了する x∈Tf+1 は値共有 故障プロセスのみから成る y∈Tf+1 は値共有 正常プロセス i 正常プロセス i l (空系列) 1 2 3 n l (空系列) 1 2 3 n

24 合意性の根拠(1) Base case アルゴリズムより，任意の正常プロセス Pi で maji(x) = uj(x’)
補題1：正常プロセスで終了する x∈Tf+1 について，ある値bが存在し，任意の正常プロセスPi において，ui(x) = maji(x) = b Base case レベルf+1 の x = x’j において j が正常プロセスであれば，j は uj(x’) を送信 アルゴリズムより，任意の正常プロセス Pi で maji(x) = uj(x’)

25 合意性の根拠(1) Induction: レベル h+1 以上で補題が成立と仮定
補題1：正常プロセスで終了する x∈Tf+1 について，ある値bが存在し，任意の正常プロセスPi において，ui(x) = maji(x) = b Induction: レベル h+1 以上で補題が成立と仮定 レベル h の正常プロセス Pi で ui(x) = b のとき 正常プロセス Pj 正常プロセス Pk 正常プロセス Pi x= x’j x' x= x’j x' x= x’j レベル h x' xk b b b ui(xk) = b = maji(xk)

26 合意性の根拠(1) x の子の数 > n-h > n-(f+1) > n-f > 2f
補題1：正常プロセスで終了する x∈Tf+1 について，ある値bが存在し，任意の正常プロセスPi において，ui(x) = maji(x) = b x の子の数 > n-h > n-(f+1) > n-f > 2f よって，x の子の過半数以上で maji(xk) = b したがって，任意の正常プロセス Pi で maji(x) = ui(x) = b 正常プロセス Pj 正常プロセス Pk 正常プロセス Pi x= x’j x' x= x’j x' x= x’j レベル h x' xk b b b ui(xk) = b = maji(xk)

27 合意性の根拠(2) 故障プロセスは f 個しかないので，yの長さは高々 f Base case: |y|=f のとき
補題2： 故障プロセスのみから成る y∈Tf+1 は値共有 故障プロセスは f 個しかないので，yの長さは高々 f Base case: |y|=f のとき y の任意の子 yj ∈ Tf+1 について， j は必ず正常プロセス よって， yj は値共有 アルゴリズムより， 任意の正常プロセス Pi, Pj で maji(y) = majj(y) l (空系列)

28 合意性の根拠(2) Induction: 長さ h 以上の故障プロセスのみから成 る中継路で補題が成り立つと仮定
補題2： 故障プロセスのみから成る y∈Tf+1 は値共有 Induction: 長さ h 以上の故障プロセスのみから成 る中継路で補題が成り立つと仮定 長さ h-1 の故障プロセスのみから成る中継路y y の子はすべて補題1，補題2を満たす よって，アルゴリズムより y も 任意の正常プロセス Pi, Pj で maji(y) = majj(y)

29 妥当性の根拠 レベル1の各xについて maji(l) は値共有かつ妥当性を満たす
補題1：正常プロセスで終了する x∈Tf+1 について，ある値bが存在し，任意の正常プロセスPi において，ui(x) = maji(x) = b 補題2： 故障プロセスのみから成る y∈Tf+1 は値共有 正常プロセス i l (空系列) 1 2 3 n レベル1の各xについて xが正常プロセスならば ui(x) = maji(x) = (xの提案値) xが故障プロセスでも値共有 maji(l) は値共有かつ妥当性を満たす

30 アルゴリズムByz-Consの正当性 合意性：補題1，補題2 停止性：f+1 ラウンドで必ず終了 妥当性：合意性の議論より 定理3
アルゴリズムByz-Consは n>3f の時，同期システムでビザンチン合意問題を解く 合意性：補題1，補題2 停止性：f+1 ラウンドで必ず終了 妥当性：合意性の議論より

31 時間複雑度，通信複雑度 アルゴリズムが停止するまでに要する ビザンチン合意問題の下限 時間： f+1 ラウンド
通信：O(nf+1 log n) ビット ビザンチン合意問題の下限 プロセス数 ラウンド数 ビット数 下限 3f+1 f+1 W(f2)

32 移動ビザンチン合意アルゴリズム J. A. Garay, Reaching (and Maintaining) Agreement in the Presence of Mobile Faults, In Proc. of Workshop on Distributed Algorithms, pp.253–264,1994.

33 移動ビザンチン故障 ビザンチン故障プロセス集合が時々刻々と変化 たとえば メモリの内容の書き換え 送信メッセージの操作
アルゴリズムのコードの書き換え たとえば コンピュータウィルス， ボットプログラムの活動

34 移動ビザンチン故障 ビザンチン故障プロセス集合が時々刻々と変化 たとえば メモリの内容の書き換え 送信メッセージの操作
アルゴリズムのコードの書き換え たとえば コンピュータウィルス， ボットプログラムの活動

35 移動ビザンチン故障 ビザンチン故障プロセス集合が時々刻々と変化 たとえば メモリの内容の書き換え 送信メッセージの操作
アルゴリズムのコードの書き換え たとえば コンピュータウィルス， ボットプログラムの活動 1

36 移動ビザンチン故障 ビザンチン故障プロセス集合が時々刻々と変化 たとえば メモリの内容の書き換え 送信メッセージの操作
アルゴリズムのコードの書き換え たとえば コンピュータウィルス， ボットプログラムの活動 1

37 移動ビザンチン合意問題 定義 [移動ビザンチン合意問題]
プロセス集合 P={P1, P2, …, Pn} の各プロセス Pi が 提案値 vi∈{0, 1} を持つ． また，合意値を書き込む変数 wi を持つ． 以下の条件を満たす合意値を決定するアルゴリズムを設計せよ． （合意性）　すべての正常なプロセスは同じ値を合意値とする （停止性）　すべての正常なプロセスはいずれ合意値を決定する （妥当性）　合意値はいずれかのプロセスの提案値である （合意維持性）　合意達成後は，正常プロセスは毎ラウンド終了 　　　　　　　　　　時点で合意性を満たす

38 定義：移動ビザンチン故障 Fr⊆P：ラウンド r でのビザンチン故障プロセス集合 復帰プロセス
故障数 f = maxr>0{|Fr|} 復帰プロセス ひとつ前のラウンドでの故障していた正常プロセス 例）書き換えられた合意値，コードをもつ可能性 P1 P2 P3 時刻 第1ラウンド 第2ラウンド 第3ラウンド ビザンチン

39 ビザンチン合意アルゴリズム適用は困難 補題1：正常プロセスで終了する x∈Tf+1 について，ある値bが存在し，任意の正常プロセスPi において，ui(x) = maji(x) = b 補題2： 故障プロセスのみから成る y∈Tf+1 は値共有 補題2のベースケースで使用した性質 (故障プロセスのみから成る系列)(正常プロセス) という系列が作成できない 合意値の一致を保証できない 情報を大量に集めても有効ではない l (空系列)

40 アイデア 少ない情報交換で合意値を決める 最終的にはリーダーに従う 提案値の一斉送信，過半数計算を繰り返す
各プロセスがフェーズごとに順にリーダー役 (IDで決定) 合意が取れていない時は，リーダーの提案値を採用 補題3 毎時間故障プロセス集合が変化する時，f>0で合意は不可能 故障しないプロセスを1つだけ仮定すれば合意可能 (Garay, 1994)

41 移動ビザンチン合意アルゴリズム MobileByz-Cons
wi = (Pi の提案値) 第2ラウンド 合意性，停止性を保証 正常プロセスがリーダー となれば，合意達成 第1ラウンド 合意維持性を保証 一度合意すれば， 過半数計算で十分 第1ラウンド 全隣接プロセスに wi を送信； 受信値の過半数以上が1なら， wi = 1, otherwise wi = 0； counti = (wi の出現回数)； リーダーなら wi を送信； counti < n-2f ならば wi = (リーダーの合意値)； 第2ラウンド

42 移動ビザンチン合意アルゴリズム MobileByz-Cons
wi = (Pi の提案値) 第2ラウンド 合意性，停止性を保証 正常プロセスがリーダー となれば，合意達成 第1ラウンド 合意維持性を保証 一度合意すれば， 過半数計算で十分 第1ラウンド 全隣接プロセスに wi を送信； 受信値の過半数以上が1なら， wi = 1, otherwise wi = 0； counti = (wi の出現回数)； 復帰プロセスでは counti の値が正しい保証なし リーダーなら wi を送信； counti < n-2f ならば wi = (リーダーの合意値)； 第2ラウンド

43 復帰プロセスのカウンタ値 修復が必要 第1ラウンドでの値が必 要 再度全プロセスから合意 値を収集 第1ラウンド 第2ラウンド
wi = (Pi の提案値) 修復が必要 第1ラウンドでの値が必 要 再度全プロセスから合意 値を収集 第1ラウンド 全隣接プロセスに wi を送信； 受信値の過半数以上が1なら， wi = 1, otherwise wi = 0； counti = (wi の出現回数)； P1 P2 P3 P4 P5 P6 P7 リーダーなら wi を送信； counti < n-2f ならば wi = (リーダーの合意値)； 第2ラウンド

44 カウンタ値の修復 手順 全プロセスで第1ラウンドで受信した合意値，送信者を交換 受信値からラウンド1での受信値を再計算 P1 P7 P2

45 カウンタ値の修復 手順 n-2f 個以上値bがあるなら， 復元値=b, otherwise 0
全プロセスで第1ラウンドで受信した合意値，送信者を交換 受信値からラウンド1での受信値を再計算 P1 P2 Pk Pn 1 Pj … Pj から 受信した情報 n-2f 個以上値bがあるなら， 復元値=b, otherwise 0 復元した 受信値 1 …

46 移動ビザンチン合意アルゴリズム MobileByz-Cons
wi = (Pi の提案値) 合意性 停止性 妥当性 合意維持性 定理4 アルゴリズムMobileByz-Consは n>6f，かつ，少なくとも1プロセスが故障しない同期システムで 移動ビザンチン合意問題を解く 第1ラウンド 全隣接プロセスに wi を送信； 受信値の過半数以上が1なら， wi = 1, otherwise wi = 0； counti = (wi の出現回数)； 第1ラウンドの受信値の復元リーダーなら wi を送信； counti < n-2f ならば wi = (リーダーの合意値)； 第2ラウンド

47 今後の展開

48 通信ネットワーク 完全ネットワーク 一般ネットワークへ 一般ネットワークでのビザンチン合意の必要十分条件 （Dolev, 1982）
任意の2プロセス間で直接通信可能 一般ネットワークへ 任意の2点間で通信可能の保証なし 複数プロセスで通信を中継 一般ネットワークでのビザンチン合意の必要十分条件 （Dolev, 1982） 点連結度 d > 2f

49 通信ネットワーク(Contd.) 移動ビザンチン合意については未解決 一部には光明（佐々木，2013）
情報伝搬に時間がかかるほど，移動ビザンチンが悪影響 一部には光明（佐々木，2013） 故障数の上界：n < 6t で合意不可能 グラフ上での移動ビザンチン合意アルゴリズム 完全k部グラフ：n-3(n/k-1)>8t の場合 リングの d/2 冪グラフ： max{d, 4d-2n+4} > 8t の場合

50 完全k部グラフ上での 移動ビザンチン合意問題
各頂点が直接通信可能なのは n(k-1)/k 頂点 残りの n/k 頂点との距離は2 MobileByz-Consを拡張 第1ラウンド：過半数計算 第2ラウンド：リーダーの合意値配布 第3ラウンド：過半数計算 　　　　　　　　(リーダーの合意値配布)

51 完全k部グラフ上での 移動ビザンチン合意問題
定理5 通信ネットワークが完全k部グラフであるとき， n -3(n/k-1) > 8f，かつ，少なくとも1プロセスが故障しない 同期システムで移動ビザンチン合意問題を解くことができる． 故障数の上界( n > 6f ) にはまだギャップ 一般のグラフに対してはまだ不明

52 その他の関連研究 乱択ビザンチン合意アルゴリズム 認証機能付きシステムでのビザンチン合意問題 非同期システムでの不可能性の打破
乱数実現の手法 ローカルなコイントス グローバルなコイント 認証機能付きシステムでのビザンチン合意問題 公開鍵暗号のような認証機能付き （中継値を書き換えられない） n>f でビザンチン合意可能

53 まとめ：ビザンチン故障と分散制御 ビザンチン合意問題，移動ビザンチン合意問題 未解決問題： 一般ネットワーク上の移動ビザンチン合意問題
分散環境での局所性vsビザンチン故障 不可能性：故障プロセス数の上限 ビザンチン合意問題：提案値の相互一貫性問題 移動ビザンチン合意問題： リーダー提案値の一斉送信，合意値の維持 未解決問題： 一般ネットワーク上の移動ビザンチン合意問題

54 関連文献 J. A. Garay, Reaching (and Maintaining) Agreement in the Presence of Mobile Faults, In Proc. of Workshop on Distributed Algorithms, pp.253–264,1994. N. Banu, S. Souissi, T. Izumi, and K. Wada, An Improved Byzantine Agreement Algorithm for Synchronous System with Mobile Byzantine Faults, International Journal of Computer Applications, 43 (21), 2011. M. Pease, R. Shostak, and L. Lamport, Reaching Agreement in the Presence of faults, J. of the Association for Computing Machinery, 27 (2), pp.228—234, 1980. 佐々木 徹，山内 由紀子，来嶋 秀治，山下 雅史，一般のネットワーク 上の移動ビザンチン合意問題について，第143回アルゴリズム研究会， 2013，3月（発表予定）． 増澤利光，山下雅史，適応的分散アルゴリズム，共立出版，2010．

55