チャンドラ・トゥエグ合意アルゴリズム
 |
1996 年に Tushar Deepak Chandra と Sam Toueg によって発表されたChandra–Toueg コンセンサス アルゴリズム は、最終的に強力な障害検出器を備えた信頼性の低いプロセスのネットワークでコンセンサスを解決するためのアルゴリズムです。障害検出器はタイムアウトの抽象バージョンであり、他のプロセスがクラッシュした可能性がある場合に各プロセスに信号を送ります。最終的に強力な障害検出器は、初期の混乱期間の後に特定の障害のないプロセスが障害が発生したと識別することはなく、同時に、最終的にはすべての障害のあるプロセスが障害が発生したと識別します (障害のあるプロセスとは、最終的に失敗するかクラッシュするプロセスであり、障害のないプロセスは決して失敗しません)。Chandra–Toueg コンセンサス アルゴリズムでは、障害のあるプロセスの数 ( f ) が n/2 未満 (つまり少数派)、つまりf < n /2 (n はプロセスの総数) であると想定します。
アルゴリズム
このアルゴリズムはラウンド単位で進行し、ローテーションするコーディネータを使用します。各ラウンドrにおいて、r mod nで与えられる ID を持つプロセスがコーディネータとして選択されます。各プロセスは、現在の優先決定値（初期値はプロセスの入力値）と、決定値を変更した最後のラウンド（値のタイムスタンプ）を記録します。各ラウンドで実行されるアクションは以下のとおりです。
- すべてのプロセスは (r、preference、timestamp) をコーディネータに送信します。
- コーディネータは、少なくとも半数のプロセス (自分自身を含む) からのメッセージを受信するまで待機します。
- 次に、送信された値の中から最新のタイムスタンプを持つ値を優先値として選択します。
- コーディネータはすべてのプロセスに (r, preference) を送信します。
- 各プロセスは、（1）コーディネータから（r、preference）を受信するか、（2）障害検出器がコーディネータのクラッシュを識別するまで待機します。
- 最初のケースでは、自身の設定をコーディネータの設定に設定し、ack(r) で応答します。
- 2 番目のケースでは、コーディネータに nack(r) を送信します。
- コーディネータは、大多数のプロセスから ack(r) または nack(r) を受信するまで待機します。
- 多数からack(r)を受信した場合、すべてのプロセスにdecide(preference)を送信します。
- 初めて decide(preference) を受信したプロセスは、decide(preference) をすべてのプロセスに中継し、その後、preference を決定して終了します。
このアルゴリズムは 1 つの値のみを決定するために使用されることに注意してください。
正確さ
問題の定義
コンセンサス問題を「解決する」アルゴリズムは、次の特性を確保する必要があります。
- 終了: すべてのプロセスが値を決定します。
- 合意：すべてのプロセスが同じ値を決定する。そして
- 妥当性: すべてのプロセスは、あるプロセスの入力値であった値を決定します。
仮定
Chandra-Toueg コンセンサス アルゴリズムが上記の 3 つの特性を満たしていることを主張する前に、このアルゴリズムにはn = 2* f + 1 個のプロセスが必要であり、そのうち最大で f 個に障害があることを思い出してください。
さらに、このアルゴリズムは、最終的に強力な障害検出器（アクセス可能であり、ノードのクラッシュを検出するために使用できる）の存在を前提としていることに注意してください。最終的に強力な障害検出器とは、初期の混乱期間の後、特定の非障害（または正常な）プロセスが障害を起こしたとは決して判定せず、同時に、最終的にはすべての障害のあるプロセスを障害を起こしたと判定する検出器です。
正しさの証明
終了は、最終的に障害検出器が故障していないプロセスpを疑わなくなり、最終的にpがコーディネータとなるため成立する。あるラウンドrでこれが起こる前にアルゴリズムが終了していない場合、ラウンドrのすべての故障していないプロセスはpのpreferenceの受信を待ち、ack(r)で応答する。これにより、pはdecide(preference)を送信するのに十分な確認応答を収集でき、すべてのプロセスが終了する。あるいは、故障したコーディネータが少数のプロセスにのみdecideを送信し、これらのプロセスのいずれかが故障していない場合は、残りのすべてのプロセスに決定をブロードキャストし、すべてのプロセスが決定して終了する。
有効性は、すべての設定が何らかのプロセスの入力として開始されるという事実から生じます。プロトコルには新しい設定を生成するものは何もありません。
合意は潜在的に最も達成が難しい。あるラウンドrにおいて、あるコーディネーターが何らかの値vから決定メッセージを送信し、それが少数のプロセスにしか伝播しないうちに、後のラウンドr'において別のコーディネーターが別の値v'の決定メッセージを送信する、といった状況が起こり得る。このような事態が発生しないことを示すために、最初のコーディネーターが決定(v)を送信する前に、過半数のプロセスからack(r)を受信している必要があることを観察する。しかし、その後に続くコーディネーターが過半数のプロセスにポーリングを行うと、後の過半数が前のプロセスと重なり、vが最新の値となる。したがって、決定メッセージを送信する2つのコーディネーターは同じ値を送信する。
参考文献
