Document

3.3 非同期システムにおける合意

仮定
 故障

クラッシュ故障のみ
 通信


送ったメッセージはいつか届く
扱う問題
 コンセンサス問題

ビザンチン将軍問題より簡単
3.3 コンセンサス問題
プロセス={P1, P2, …}
 Pi (i=1,2,..): propose(vi),
 Pi (i=1,2,..): decide(wi)
 条件

 停止性
 合意:
Pi, Pjが正常なら，wi = wj
 妥当性: Piが正常のとき，wi = vj となるPjが存在
(j=iでもよい）
propose(1)
decide(3)
A
propose(2)
decide(3)
B
C
propose(3)
decide(3)
propose(1)
A
decide(3)
propose(3)
propose(2)
decide(3)
B
C
コンセンサスの応用
非ブロッキング原子コミット (3.4.4)
 原子ブロードキャスト (3.5.2)

 プロセス多重化
(3.5)
 データ多重化 (3.6)
非同期システムでのコンセンサス

無理
 FLP不可能性

(FLP impossibility result)
１プロセスのクラッシュ故障でも不可能
 故障ノードと遅いノードとを区別できない
P1
Di
Di
P1
Dto
P2
Dto
!
時間
(a)
Di
Di
Dto
P2
Dto
!
時間
(b)
非同期システムでのコンセンサス

まず停止性以外の条件を満たすことを考える



合意: Pi, Pjが正常なら，wi = wj
妥当性: Piが正常のとき，wi = vj となるPjが存在
Chandra-Touegアルゴリズム
1.
2.
各プロセスが4ステップからなるラウンドを繰り返し実行
調停者プロセスによって決定する値が定まった場合，そ
の値を高信頼ブロードキャスト
高信頼ブロードキャスト

ブロードキャスト
 全ノードにメッセージを伝えること

高信頼ブロードキャスト
 故障が起きても，正常な全ノードにつたわるか，
どのノードにも伝わらない
A
R-deliver(m)
A
A
R-bcast(m)
B
R-deliver(m)
C
R-deliver(m)
B
C
B
C
高信頼ブロードキャスト
アルゴリズム
R-bcast(m)

R-bcast(m)を実行:
P1
send(m) to 全ノード
2. R-deliver(m)
P2
1.

mを受信:
1.
if (mを初めて受信)
1.
2.
send(m) to 全ノード
R-deliver(m)
P3
P4
R-bcast(m)
P1
P2
P3
P4
Chandra-Touegアルゴリズム
ステップ1

調停者プロセスに，候補となる値(e)と，その値を得
たラウンド番号(u)を送信する
 巡回調停者
 ラウンド1: P1 → ラウンド2: P2 →ラウンド3: P3 →ラウンド4: P1
→
v1,0
propose(v1) P1
e1:= v1
u1:= 0 v ,0
2
r1:= 1
propose(v2) P2 e2:= v2
u2:= 0
r2:= 1
propose(v3) P3 e3:= v3
u3:= 0
r3:= 1
v3,0
Chandra-Touegアルゴリズム
ステップ2


調停者は過半数のプロセスからのメッセージを待ち，最も新
しいもの（uの値が大きいもの）を選び，全てのプロセスにそ
のvの値を送信する
調停者以外のプロセスは何も行わない
P1
P2
P3
v1,0
v1
e1:= v1
u1:= 0 v ,0
2
r1:= 1
e2:= v2
u2:= 0 v3,0
r2:= 1
e3:= v3
u3:= 0
r3:= 1
v1
v1
Chandra-Touegアルゴリズム
ステップ3

メッセージを受け取った場合，e，uを更新し，ackを調停者に
送信する


e:= 受信した値，u:=現在のラウンド番号r
故障していると判断した場合，nackを調停者に送信する
P1
P2
P3
v1,0
e1:= v1
u1:= 1
v1
e1:= v1
u1:= 0 v ,0
2
r1:= 1
e2:= v2
u2:= 0 v3,0
r2:= 1
e3:= v3
u3:= 0
r3:= 1
v1
v1
Ack
Ack
e2:= v1
u2:= 1
e3:= v1
u3:= 1
Ack
Chandra-Touegアルゴリズム
ステップ4

調停者は過半数のプロセスからの返信を待つ
 すべてAckなら，値を高信頼ブロードキャスト
 Nackが一つでもあれば，ステップ1へ戻る

調停者以外のプロセスはステップ1へ戻る
P1
P2
P3
v1,0
e1:= v1
u1:= 1
v1
e1:= v1
u1:= 0 v ,0
2
r1:= 1
e2:= v2
u2:= 0 v3,0
r2:= 1
e3:= v3
u3:= 0
r3:= 1
ラウンド 1
v1
Ack
v1を高信頼ブロードキャスト
decide(v1)
Ack
decide(v1)
r2:= 2
v1
e2:= v1
u2:= 1
Ack
e3:= v1
u3:= 1
r3:= 2
decide(v1)
ラウンド 2
Chandra-Touegアルゴリズム
ステップ3 故障と判断した場合


メッセージを受け取った場合，e，uを更新し，ackを
調停者に送信する
故障していると判断した場合，nackを調停者に送信
する
P1
P2
P3
v1,0
e1:= v1
u1:= 1 v1
ラウンド 1
v1を高信頼ブロードキャスト
v1
v1
v2,0
v3,0
Ack
v1 Ack
Nack
v1
Ack
e3:= v1
u3:= 1
v2,0
v1,1
e2:= v1
u2:= 2
ラウンド 2
v1を高信頼ブロード
v1
キャスト
Ack
Chandra-Touegアルゴリズム
耐故障性

ステップ2，ステップ4で，調停者は過半数のプロセ
スからのメッセージで動作する
 1/2未満のプロセスの故障に耐性がある
P1
P2
P3
v1,0
u1:= 1
v1
Ack
e1:= v1
u1:= 0 v ,0
2
r1:= 1
v1
Ack
e2:= v2
u2:= 0 v3,0
r2:= 1
e3:= v3
u3:= 0
r3:= 1
ラウンド 1
v1を高信頼ブロードキャスト
r2:= 2
v1
e2:= v1
u2:= 1
Pi: decide(wi)
合意: Pi, Pjが正常なら，wi = wj
合意
P1
P2
P3
v1,0
e1:= v1
u1:= 1 v1
ラウンド 1
v1を高信頼ブロードキャスト
v1
v1
v2,0
v3,0
Ack
v1 Ack
Nack
v1
Ack
e3:= v1
u3:= 1
v2,0
v1,1
e2:= v1
u2:= 2
v1を高信頼ブロード
v1
キャスト
Ack
ラウンド 2

高信頼ブロードキャストするラウンドでは，過半数のプロセスが値を更新
更新される値は，過半数のプロセスで，最も新しい（最近更新された）値
過半数同士の集合には共通プロセスが存在

ブロードキャスト後は，常にその値が更新値として選ばれる


一律合意 Uniform Agreement
一律合意が満たされる
 合意


Pi, Pjが正常なら，wi = wj
一律合意

故障プロセスPiについても，decide(wi)を実行したなら，wi = wj
一律合意ではない
propose(1)
decide(3)
B
propose(2)
decide(3)
propose(1)
decide(2)
A
C
propose(3)
decide(3)
B
propose(2)
decide(2)
A
C
propose(3)
decide(3)
停止性

進行しない場合
 Step


3で故障した調停者を故障と判定しない場合
タイムアウトで対処可能
動き続ける場合
 Step
3で故障と判定することが続く場合
Ack
P1
Nack
Nack
P2
Nack
P3
Nack
停止性
正常な調停者プロセスを，正常だと判断でき
るラウンドに達すればよい．
 何らかの同期に関する仮定が必要

 (FLP不可能性)

部分的同期性の例 (3.3.4)
 メッセージの遅延，命令の実行時間に上限があ
るがその値が分かっていない
故障検出
部分的同期性の例

 メッセージの遅延，命令の実行時間に上限があ
るがその値が分かっていない
P1
Di
Di
Di
Dto
P2
Di
Dto
!
Dto
遅延を短めに見積もりすぎ
Di
Dto
!
Dto := Dto+a
検出に失敗した場合，タイム
アウト時間を延長
その他


結局，コンセンサスが解ける条件は，故障検出能力
に依存
障害検出器 failure detector (3.3.4)
 形式的に故障検出能力を定義したもの
 コンセンサス
 将来的強(eventually strong)以上が必要
 ビザンチン将軍問題（クラッシュ故障のみ）
 完全が必要

その他のアルゴリズム
 Paxos
(3.3.5)

Download Report