Total Order Broadcast
ニュアンス的に、Atomic Broadcastは実時間の話、Total Order Broadcastは論理クロックの話っぽい? kekeho.icon Atomic Broadcast
Input
$ n個のプロセッサが同時にブロードキャストするメッセージのストリーム
Output
- 以下の特性を満たす、順番に配送されるメッセージ
特性
Atomicity: いずれかの正しいプロセッサがそのクロックの指す時刻$ UにUpdateを配信した場合、そのUpdateはそれぞれの正しいプロセッサーたちにもそれらのクロックが指す時刻$ Uで配信される みんなにとって、時刻$ Uで見える
ここでの時刻は実時間kekeho.icon
Order: 正しいプロセッサーによって配信されたすべてのUpdateは、すべての正しいプロセッサに同じ順序で配信される Termination: 正しいプロセッサが、そのクロックが指す時刻$ Tでブロードキャストを開始したUpdateは、すべての正しいプロセッサに、それらのクロックが指す時刻$ T + \Deltaで配信される 一定の時間内に配信が終わる、ということなのでしょうkekeho.icon
Total Order Broadcast
Atomic Broadcastは物理時間に基づく話をしているけど、論理クロックに置き換えたバージョンが一般的。これは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.icon
データの整合性の話っぽいkekeho.icon
(Gap-free)Uniform Total Order: もしプロセスpとqがメッセージm, m'をTO-Deliverした場合、q TO-delivers m before m'していたら、p TO-delivers m before m'となる こちらは順序の話kekeho.icon
こちらは順序について何も保証していない
その他
参考
Cristian F, Aghili H, Strong R, Dolev Dの論文
上記論文をベースにした解説
サーベイ論文