Total Order Broadcast

ニュアンス的に、Atomic Broadcastは実時間の話、Total Order BroadcastはLogical Clockの話っぽい? (kekeho)
Lamport Clockを使用すると、メッセージの順序付けをした配送が可能だが、Fault toleranceはない
アルゴリズムによってメッセージのOmission fault, Timing failure, Byzantine failureに耐える
- どれもflooding(Gossip Protocol等)ベースのBroadcastが基盤となっている

Atomic Broadcast Input

$n$ 個のプロセッサが同時にブロードキャストするメッセージのストリーム Output
以下の特性を満たす、順番に配送されるメッセージ特性
Atomicity: いずれかの正しいプロセッサがそのクロックの指す時刻 $U$ にUpdateを配信した場合、そのUpdateはそれぞれの正しいプロセッサーたちにもそれらのクロックが指す時刻 $U$ で配信される
- みんなにとって、時刻 $U$ で見える
- ここでの時刻は実時間(kekeho)
Order: 正しいプロセッサーによって配信されたすべてのUpdateは、すべての正しいプロセッサに同じ順序で配信される
Termination: 正しいプロセッサが、そのクロックが指す時刻 $T$ でブロードキャストを開始したUpdateは、すべての正しいプロセッサに、それらのクロックが指す時刻 $T + Δ$ で配信される
- 一定の時間内に配信が終わる、ということなのでしょう(kekeho)

Atomic Broadcastは物理時間に基づく話をしているけど、Logical Clockに置き換えたバージョンが一般的。これはTotal Order Broadcastと呼ばれる問題である。

Input

n個のプロセッサが同時にブロードキャストするメッセージのストリーム Output
以下の特性を満たす、順番に配送されるメッセージ特性
Validity: 正しいプロセスがメッセージmをTotally Ordered Broadcastすれば、最終的に(Eventually)そのプロセスはmをTotally Ordered Deriveryする
- ここでの「正しさ」は、動作が仕様と一致しているかどうか。そうでなければ故障している
Uniform Agreement: あるプロセスがメッセージmをTotally Ordered Deriveryする場合、すべての正しいプロセスは最終的に(Eventually)mをTotally Ordered Deliverする
Uniform Integrity: For any message m, every process TO-delivers m at most once, and only if m was previously TO-broadcast by sender(m).
- 送信者がいる場合にのみ、1回だけ送られるよー(kekeho)
- データの整合性の話っぽい(kekeho)
(Gap-free)Uniform Total Order: もしプロセスpとqがメッセージm, m’をTO-Deliverした場合、q TO-delivers m before m’していたら、p TO-delivers m before m’となる
- こちらは順序の話(kekeho)
Uniform Total Orderを除くと、「Reliable Broadcast」と呼ばれる
- こちらは順序について何も保証していない
ValidityとUniform AgreementはLivenessに関わる

その他

[Distributed Consensus]と等価であることが知られている
- Consensus algorithmの代わりに使える - 証明した論文
- コンセンサスと同様、FLP ImpossibilityはTotal order broadcastにも適用される

参考

notes.kekeho.net