Document

3.2 合意問題 agreement problems

例．時計同期

メッセージを交換して，プロセスの持つlocal
clock(局所時計)の値を一定の誤差の範囲に保
つこと
1:00
1:00
A
1:00
0:00
B
1:00
0:00
2:00
A
2:00
0:00
(a) 正常
C
2:00
1:00
B
1:00
0:00
2:00
3:00
2:00
C
2:00
(b) BがByzantine 故障
(“Dual-faced”)
ビザンチン故障

平均を取る場合
(0:00 + 2:00 + 1:00)/3 = 1:00
A
1:00
B
0:00
1:00
0:00
2:00
0:00
(0:00 + 2:00 + 1:00)/3 = 1:00
1:00
A
2:00
1:00
C
B
2:00
1:00
0:00
2:00
1:00
2:00
C
2:00
(3:00 + 1:00 + 2:00)/3 = 2:00
3: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)
司令官
Po
司令官
Po
v0
副官1
P1
v0
x
v0
副官2
P2
decide(v0) decide(v0)
sensor
副官3
P3
副官1
P1
y
z
副官2
P2
副官3
P3
decide(w) decide(w) decide(w)
Module 1
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)
A
1:00
propose(0:00)
B
1:00
0:00
2:00
0:00
2:00
C
propose(2: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
1:00
B
1:00
0:00
2:00
3:00
一致
2:00
propose(2:00)
C
decide(1:00, c, 2:00)
ビザンチン将軍問題vsインタラクティ
ブコンセンサス問題
ビザンチン将軍問題A
propose(1:00)
A
ビザンチン将軍問題B
2:00
1:00
1:00
decide(c)
0:00
ビザンチン将軍問題C
2:00
decide(2:00)
B
C
3:00
インタラクティブ合意問題
ビザンチンビザンチン将軍
decide(1:00, c, 2:00)
将軍問題B 問題C
propose(2:00)
3.2.2 アルゴリズム


同期ラウンドモデルを仮定
n < 3k+1の場合，アルゴリズムは存在しない
n

= プロセス数，k = 故障プロセス数
司令官
例．n = 3, k =1 の時
司令官
 Ｐi (i = 1, 2,..) : 副官i
 提案値：「攻撃」か「退却」
 Po:
副官1
副官2
副官1には区別できない
司令官
司令官
攻撃
攻撃
副官1
副官2
司令官が退却を
命令
decide(攻撃) (a)
退却
攻撃
副官1
副官2
司令官が退却を
命令
decide(攻撃) (b)
副官2には区別できない
司令官
司令官
退却
退却
副官1
副官2
司令官が攻撃を
命令
decide(退却)
攻撃
退却
副官1
副官2
司令官が攻撃を
命令
decide(退却)
アルゴリズム OM


n > 3kを仮定
OM(0)
1.

OM(m)
1.
2.
3.

副官に値を送り，受信した副官は，その値を結果とする
副官に値を送る
値を受信した副官は，司令官となって，他の副官を対象
に，OM(m-1)を実行．送る値は，受信した値．
副官は，２で受信した値と，他の副官が実行した
OM(m-1)によって得られた値のうち，過半数を占めるも
のを結果とする．(なければ，デフォルト値)
スタート OM(k)
司令官
n=4,k=1
副官1
v:0
OM(1)
副官2
副官3
v:0
v:0
v:0,1
副官1
v:0,1
副官2
v:0,1
v:0,2
y:0,3
v:0
v:0,2
y:0,3
副官3
v:0,1
v:0,2
z:0,3
過半数のものを選択
v
OM(0) ×3
n=4,k=1
司令官
v0
副官1
x
副官2
副官3
副官1
v0
v0
y
x
v0
v0
v0
v0
司令官
x
y
z
副官2
副官3
y
x
y
z
(a)
{v0, v0, y} {v0, v0,x}
z
(b)
{x, y, z}
{x, y, z}
{x, y, z}
OM(2)
n=7,
k=2
v:0
1
v:0
2
3
4
5
6
2
3
4
5
6
4
5
6
OM(1) ×6
v:0,1
v:0,2
v:0,3
v:0,4
v:0,5
v:0,6
1
v:0,3,1
1
v:0,2,3
v:0,2,4
v:0,2,5
v:0,2,6
v:0,4,2
v:0,4,3
v:0,4,5
v:0,4,6
v:0,3,2
v:0,3,4
v:0,3,5
v:0,3,6
v:0,5,2
v:0,5,3
v:0,5,4
v:0,5,6
2
OM(0) ×6 ×5
v:0,2,1
3
v:0,6,2
v:0,6,3
v:0,6,4
v:0,6,5
v:0,2,3
v:0,2,4 v:0,2
v:0,2,5
v:0,2,6
v:0,3,2
v:0,3,4 v:0,3
v:0,3,5
v:0,3,6
過半数
を選択
w:0,2
w:0,3
w:0,2
w:0,3
w:0,4
w:0,5
w:0,6
v:0
過半数
を選択
w
アルゴリズム SM

ディジタル署名が使える場合
･･･認証アルゴリズム
n

> kで動作するアルゴリズムが存在
司令官は署名して値vを送信
 メッセージ

v:0
値が初めて受け取ったもので，署名している副官が
k未満なら，署名していない副官に自分の署名を加
えて，送信
 P1がv:0:3:2
を受信→P3, P2以外にv:0:3:2:1を送信
n=3,k=1
司令官
司令官
攻撃:0
攻撃:0
副官1
副官2
{攻撃}
副官1
副官2
{攻撃}
攻撃:0:1
副官1
{退却}
攻撃:0:1
副官2
攻撃:0:2
{攻撃}
退却:0
攻撃:0
注：退却:0:2
は送れない
副官1
副官2
退却:0:2
{攻撃, 退却}
{攻撃,退却}
受け取った値の集合が一致
司令官
n=4,k=2
攻撃:0
攻撃:0
副官2
副官1
副官3
{攻撃}
{攻撃}
攻撃:0:1
退却:0:3
副官2
副官1
攻撃:0:2
副官3
攻撃:0:2
攻撃:0:3
{攻撃} {攻撃,退却}
副官2
副官1
退却:0:3:2
{攻撃,退却} {攻撃,退却}
副官3
3.2.3 時計同期

プロセスの持つlocal clock(局所時計)の値を一定
の誤差の範囲に保つこと
P1 00:00:00
P2

H2
00:00:00
10:00:00
Clock: C1 := C1 +CORR1
10:00:25
C2 := C2 +CORR2
| Ci(t) - Cj(t) |  e を満たすように，メッセージを交換
して，新しい値を計算
 Ci(t)
:実時刻（real-time）tでのPiのクロックCiの値
時計同期

考慮すべき要素
Clockの故障
2. Clockのスピードの差
1.

3.
ドリフト率r
メッセージ遅延
時間の範囲[ -, +]内に収まると仮定
P1
t
P2
0



Fault-Tolerant Clock
Synchronization Algorithm
例．Interactive Convergence Algorithm
 間隔R毎にメッセージ交換を行いクロック値を
調整

R
P1
R
P2
t
Interactive Convergence Algorithm
1.
アルゴリズム
| Ci(t) - Cj(t) | ≤ eが成り立っていることを仮定
 全プロセスの時刻の平均をとる
 ただし， +eより誤差が大きい場合は故障とみ
なし，自分の時刻を用いる

2.
Clockの故障
nをプロセス数, kを耐えられる故障の数とした時
3k+1n
概要 ( = 0)
e =1:00 (≥|B - C|)
A
A
B :=
(A+1:00+2:00+0:00)/4
1:00
B
A
2:00
1:00
0:00 (DB)
3e/4 (=3:00/4) ≥ |B - C|
D
C
C :=
(A+1:00+2:00+3:00)/4
2:00
3:00 (DC)
|DB -DC| ≤ 3e
3k+1=nの場合， e  2(3k+1)( + rR)
問題点：精度がeに依存
インタラクティブコンセンサスによる時
計同期

認証アルゴリズムを想定
propose(1:00) decide(1:00, c, 2:00)
A
1:00
B

n > 2k
1:00
0:00
2:00
3:00
中央値を選択
2:00
propose(2:00)
C
decide(1:00, c, 2:00)
 故障プロセスの提案値が中央値となるのを避ける

Download Report