はじめに
前回は,
コーディネーションとは
並列データ処理系におけるコーディネーションは,
コーディネーションにおいては,
- 任意のプロセスがクラッシュしうる。ただし,
ビザンチン故障 (※1) は想定しない - メッセージの送信にかかる時間は有限だが上限がない。すなわち,
分散システムモデルにおける非同期システム (Asynchronous System) を想定する - 複数のプロセス間においては,
固定的なマスタ/ スレーブの関係は存在しない
コーディネーションには,
- 分散排他制御
(Distributed Mutual Exclusion) - 選挙
(Election/ Leader Election) - グループ通信
(Group Communication/ Multicast) - コンセンサス
(Consensus)
分散排他制御は,
また,
これらのコーディネーションにおいては,
今回は,
- ※1)
- ビザンチン故障は,
プロセスの動作において仮定をおかない故障です。すなわち, ビザンチン故障状態であるプロセスは任意の動作を実行する可能性があり, たとえば, 要求に対して不正または一貫しない応答を返します。
コンセンサスアルゴリズム
代表的なコンセンサスアルゴリズムである,
準備(分散システムにおける順序について)
コンセンサスにおいては,
- FIFO ordering
- 受信側において,
送信側のメッセージ送信順序でメッセージが到達する性質 - Causal ordering
- あるメッセージが別のメッセージの前に送られた場合,
当該メッセージ間には因果関係があるとし, 受信側では当該因果関係が保たれるようにメッセージが到達する性質 - Total ordering
- あるプロセスであるメッセージが別のメッセージより前に到達した場合,
すべてのプロセスにおいてその順序でメッセージが到達する性質
補足すると,
コンセンサスを用いるアプリケーションにおいては,