3.2 合意問題 agreement problems 例．時計同期 メッセージを交換して，プロセスの持つlocal clock(局所時計)の値を一定の誤差の範囲に保つこと 1:00 1:00 A A 2:00 2:00 1:00 1:00 1:00 1:00 0:00 0:00 2:00 2:00 B C B C 0:00 0:00 3:00 2:00 2:00 (a) 正常 (b) BがByzantine 故障 (“Dual-faced”)

ビザンチン故障 平均を取る場合 差が縮まらない (0:00 + 2:00 + 1:00)/3 = 1:00 A 1:00 A B C 3:00 2:00 1:00 0:00 1:00 2:00 1:00 1:00 0:00 2:00 B C 0:00 2:00 0:00 2:00 (3:00 + 1:00 + 2:00)/3 = 2:00 差が縮まらない

3.2.2 問題の定義 ビザンチン将軍問題 プロセス={Po, P1, P2, …} Po: propose(v0), Pi (i=1,2,..): decide(wi) 条件 停止性 合意: Pi, Pjが正常なら，wi = wj 妥当性: Poが正常のとき，Piが正常ならv0 = wi

propose(v0) decide(v0) decide(v0) decide(w) decide(w) decide(w) v0 v0 司令官 Po 司令官 Po v0 v0 v0 x y z 副官1 P1 副官2 P2 副官3 P3 副官1 P1 副官2 P2 副官3 P3 decide(v0) decide(v0) decide(w) decide(w) decide(w) Module 1 sensor 多数決 Module 2 Module 3

インタラクティブコンセンサス問題 プロセス={P1, P2, …} Pi (i=1,2,..): propose(vi), Pi (i=1,2,..): decide(wi) wi = (wi1, wi2, …) (ベクトル) 条件 停止性 合意: Pi, Pjが正常なら，wi = wj 妥当性: Pjが正常のとき，Piが正常ならwij = vj

propose(1:00) decide(1:00, 0:00, 2:00) propose(2:00) propose(0:00) A 2:00 1:00 1:00 0:00 2:00 propose(2:00) B C propose(0:00) 0:00 decide(1:00, 0:00, 2:00) decide(1:00, 0:00, 2:00) propose(1:00) decide(1:00, c, 2:00) A B C 3:00 2:00 1:00 0:00 一致 propose(2:00) decide(1:00, c, 2:00)

ビザンチン将軍問題vsインタラクティブコンセンサス問題 ビザンチン将軍問題A propose(1:00) A B C 3:00 2:00 1:00 0:00 ビザンチン将軍問題B decide(c) ビザンチン将軍問題C decide(2:00) インタラクティブ合意問題 decide(1:00, c, 2:00) ビザンチン将軍問題B ビザンチン将軍問題C propose(2:00)

3.2.2 アルゴリズム 同期ラウンドモデルを仮定 n < 3k+1の場合，アルゴリズムは存在しない 例．n = 3, k =1 の時 Po: 司令官 Ｐi (i = 1, 2,..) : 副官i 提案値：「攻撃」か「退却」 司令官 副官1 副官2

副官1には区別できない decide(攻撃) decide(攻撃) 副官2には区別できない decide(退却) decide(退却) 司令官 司令官 攻撃 攻撃 攻撃 退却 副官1 副官1 副官2 副官2 司令官が退却を命令 司令官が退却を命令 decide(攻撃) (a) decide(攻撃) (b) 副官2には区別できない 司令官 司令官 退却 退却 攻撃 退却 副官1 副官1 副官2 副官2 司令官が攻撃を命令 司令官が攻撃を命令 decide(退却) decide(退却)

アルゴリズム OM n > 3kを仮定 OM(0) OM(m) スタート OM(k) 副官に値を送り，受信した副官は，その値を結果とする OM(m) 副官に値を送る 値を受信した副官は，司令官となって，他の副官を対象に，OM(m-1)を実行．送る値は，受信した値． 副官は，２で受信した値と，他の副官が実行したOM(m-1)によって得られた値のうち，過半数を占めるものを結果とする．(なければ，デフォルト値) スタート OM(k)

n=4,k=1 OM(1) OM(0) ×3 v:0 v:0 v:0 v:0,1 v:0,1 v:0,1 v:0,1 v:0,2 v:0,2 司令官 OM(1) 副官1 副官2 副官3 OM(0) ×3 v:0 v:0 v:0 v:0,1 v:0,1 副官1 副官2 副官3 v:0,1 v:0,1 v:0,2 v:0,2 y:0,3 z:0,3 v:0 過半数のものを選択 v:0,2 v y:0,3

n=4,k=1 {v0, v0, y} {v0, v0,x} {x, y, z} {x, y, z} {x, y, z} v0 v0 x y 司令官 司令官 v0 v0 x y z v0 v0 x 副官1 副官2 副官1 x 副官2 z 副官3 副官3 v0 v0 y y v0 x y z (a) (b) {v0, v0, y} {v0, v0,x} {x, y, z} {x, y, z} {x, y, z}

n=7, k=2 OM(2) v:0 1 2 3 4 5 6 OM(1) ×6 v:0,1 1 2 3 4 5 6 OM(0) ×6 ×5 過半数を選択 v:0,2,3 v:0,2,4 v:0,2,5 v:0,2,6 v:0,2 過半数を選択 w:0,2 w:0,2 w:0,3 v:0,3,2 v:0,3,4 v:0,3,5 v:0,3,6 w:0,4 v:0 v:0,3 w:0,3 w:0,5 w:0,6 w

アルゴリズム SM ディジタル署名が使える場合 ･･･ 認証アルゴリズム 司令官は署名して値vを送信 n > kで動作するアルゴリズムが存在 司令官は署名して値vを送信 メッセージ　v:0 値が初めて受け取ったもので，署名している副官がk未満なら，署名していない副官に自分の署名を加えて，送信 P1がv:0:3:2 を受信→P3, P2以外にv:0:3:2:1を送信　

n=3,k=1 注：退却:0:2は送れない 受け取った値の集合が一致 {攻撃} {攻撃} {退却} {攻撃} {攻撃, 退却} 司令官 司令官 攻撃:0 攻撃:0 攻撃:0 退却:0 副官1 副官2 副官1 副官2 {攻撃} {攻撃} {退却} 攻撃:0:1 攻撃:0:1 副官1 副官2 副官1 副官2 攻撃:0:2 退却:0:2 {攻撃} {攻撃, 退却} {攻撃,退却} 注：退却:0:2は送れない 受け取った値の集合が一致

n=4,k=2 {攻撃} {攻撃} {攻撃} {攻撃,退却} {攻撃,退却} {攻撃,退却} 攻撃:0 攻撃:0 攻撃:0:1 退却:0:3 司令官 攻撃:0 攻撃:0 副官1 副官2 副官3 {攻撃} {攻撃} 攻撃:0:1 退却:0:3 副官1 副官2 副官3 攻撃:0:2 攻撃:0:2 攻撃:0:3 {攻撃} {攻撃,退却} 副官1 副官2 副官3 退却:0:3:2 {攻撃,退却} {攻撃,退却}

3.2.3 時計同期 プロセスの持つlocal clock(局所時計)の値を一定の誤差の範囲に保つこと | Ci(t) - Cj(t) | ≤ e を満たすように，メッセージを交換して，新しい値を計算 Ci(t) :実時刻（real-time）tでのPiのクロックCiの値 00:00:00 10:00:00 P1 Clock: C1 := C1 +CORR1 H2 00:00:00 10:00:25 P2 C2 := C2 +CORR2

時計同期 考慮すべき要素  Clockの故障 Clockのスピードの差 メッセージ遅延 ドリフト率r 時間の範囲[ -d, +d]内に収まると仮定 P1 t P2  d d

Fault-Tolerant Clock Synchronization Algorithm 例．Interactive Convergence Algorithm 間隔R毎にメッセージ交換を行いクロック値を調整 R t P1 R P2

Interactive Convergence Algorithm アルゴリズム | Ci(t) - Cj(t) | ≤ eが成り立っていることを仮定 全プロセスの時刻の平均をとる ただし， d+eより誤差が大きい場合は故障とみなし，自分の時刻を用いる Clockの故障 nをプロセス数, kを耐えられる故障の数とした時3k+1n

概要 (d = 0) 問題点：精度がeに依存 e =1:00 (≥|B - C|) A B := (A+1:00+2:00+0:00)/4 0:00 (DB) 3:00 (DC) 3e/4 (=3:00/4) ≥ |B - C| |DB -DC| ≤ 3e D 3k+1=nの場合， e  2(3k+1)(d + rR) 問題点：精度がeに依存

インタラクティブコンセンサスによる時計同期 認証アルゴリズムを想定 n > 2k 故障プロセスの提案値が中央値となるのを避ける propose(1:00) decide(1:00, c, 2:00) A B C 3:00 2:00 1:00 0:00 中央値を選択 propose(2:00) decide(1:00, c, 2:00)