アルゴリズム
\( \def\vector#1{\boldsymbol{#1}} \)

論文翻訳: Reaching Agreement in the Presence of Faults

Takami Torao 1979年の論文 #BFT
  • このエントリーをはてなブックマークに追加

ABSTRACT

ここで扱われている問題は 2 者間のメッセージによってのみ通信する、一部の未知の部分集合が故障している可能性のある、独立したプロセッサの集合に関するものである。故障していない各プロセッサは、他の互いに故障していないプロセッサと通信されなければならない情報のプライベートな値を有する。故障のないプロセッサは常に正しく通信するが、故障のあるプロセッサは嘘をつくことがある。論点は、プロセッサ自身が値を通信し、他から受信した値を中継して、故障していないプロセッサが互いのプロセッサの値を参照できるようにするアルゴリズムを考案することである。故障していないプロセッサについて参照される値はそのプロセッサのプライベート値でなければならず、故障したプロセッサについて推測される値は、他の故障していないプロセッサによって推測される対応する値を一致しなければならない。

この問題は \(n \ge 3m + 1\) に対してのみ解決可能であることが示されている。ここで \(n\) はプロセッサの総数、\(m\) は障害のあるプロセッサ数である。また、故障したプロセッサが情報を渡すことを拒否できるが誤った情報を中継することができない場合、問題は任意の \(n \ge m \ge 0\) に対して解決可能であることも示されている。

KEY WORD AND PHRASES. 合意, 認証, 一貫性, 分散実行, 障害回避, 障害耐性, 同期, 投票
CR CATEGORIES: 3.81, 4.39, 5.29, 5.39, 6.22

Table of Contents

  1. ABSTRACT
  2. 1. Introduction
  3. 2. The Single-Fault Case
  4. 3. A Procedure for \(n \ge 3m+1\)
  5. 4. Proof of Impossibility for \(n \lt 3m+1\)
  6. 5. An Algorithm Using Authenticators
  7. 6. Conclusions
  8. REFERENCES
  9. 翻訳抄

1. Introduction

しばしばフォールトトレラントシステムは独立したプロセッサまたはプロセスがある正確な相互合意に達することのできる手段を必要とする。例えば、冗長システムのプロセッサがそれらのそれらの内部クロックを周期的に同期させることが必要であるかもしれない。あるいは、それぞれにわずかに異なる測定値を与える時変入力センサーの値を決定しなければならないかも知れない。故障がなければ、十分な相互合意に達することは通常容易なことである。ほとんどの場合、単に値を交換し (時刻, クロック同期の場合) ある種の平均を計算するだけで十分である。しかし、欠陥のあるプロセッサが存在する場合は単純な交換が信用できない; 不良プロセッサはある値を特定のプロセッサに報告し、別の値を他のプロセッサに報告してそれぞれが異なる "平均" を計算する可能性がある。

故障のあるプロセッサの影響は複数回の情報交換ラウンドによる投票方式を使うことによって対処できると考える人もいるだろう; そのようなスキームは故障しているプロセッサが故障であることを明らかにするか、または少なくとも故障していないプロセッサに対して、後者が正確な一致に達することを可能にするのに十分な一貫して動作することを強制する可能性がある。これから述べるように、例え故障したプロセッサが少数派であることが分かっていたとしても、この種のスキームを考案することは必ずしも可能ではない。しかし、故障していないプロセッサの数が故障したプロセッサの数を十分に上回る場合には、故障していないプロセッサが正確に一致することを可能にするアルゴリズムが存在する。

我々の結果は相互一貫性 (interactive consistency) の概念を用いて以下のように定式化する: \(n\) 個の独立したプロセッサの集合を考慮し、そのうち \(m\) 個以下が故障であることが分かっている。ただし、どのプロセッサが故障しているかは不明である。プロセッサは 2 者間のメッセージによってのみ通信できると仮定する。通信媒体はフェールセーフであり遅延は無視できると想定する。さらに、メッセージの送信者は受信者から常に識別可能である。また各プロセッサ \(p\) はプライベート値の情報 \(V_p\) (クロック値やセンサーの読み取り値など) を有する者とする。論点は、与えられた \(m, n \ge 0\) に対して故障していないプロセッサ \(p\) が \(n\) 個のプロセッサそれぞれの要素を用いて値のベクトルを計算することを可能にするメッセージの交換に基づいて、以下のようなアルゴリズムを考案することが可能かどうかである。

  1. 故障のないプロセッサは正確に同じベクトルを計算する;
  2. 特定の故障していないプロセッサに対応するこのベクトル要素は、そのプロセッサのプライベート値である。

このアルゴリズムはどのプロセッサが故障しているかを明らかにする必要はなく、故障したプロセッサに対応する計算されたベクトルの要素は任意で有り得ることに留意されたい; 問題となるのは故障していないプロセッサが故障しているプロセッサに対して正確に同じ値を計算することだけである。

このようなアルゴリズムは、故障していないプロセッサが故障したプロセッサを含む全てのプロセッサが保持している値の一貫した見方を得ることを可能にするため相互一貫性を達成すると述べている。計算されたベクトルは interactive consistency (i.c.) ベクトルと呼ばれる。相互一貫性が達成されると、故障していない各プロセスはアプリケーションの必要に応じて、平均化またはフィルタリング機能を i.c. ベクトルに適用することができる。故障していない各プロセッサはこの機能を同じベクトル値に適用するので必然的に厳密な一致に達する。

以下のセクションでは \(n \ge 3m + 1\) となる \(n, m\) でのみ相互一貫性を保証するアルゴリズムを考案できることを示す。特に、単一障害の場合には最低 4 つのプロセッサが必要となる。しかし、我々は、故障プロセッサが他のプロセッサから得た情報を渡すことを拒否できるが、その情報を書き換えて報告することができないと仮定した場合、任意の \(n \ge m \ge 0\) に対して相互一貫性を保証できることも示す。この仮定はセクション 5 で論議する認証コード (authenticator) を使用して実際に近づくことができる。

セクション 2 では単一障害ケースの説明から始める。セクション 3 は \(n \ge 3m+1\) への一般化、セクション 4 は \(n \le 3m\) に対する不可能性議論である。セクション 5 では上記の制限された仮定の下で働く任意の \(n \ge m \ge 0\) ののためのアルゴリズムを与える。結論と今後の研究課題についてはセクション 6 で述べる。ここで考察した問題と同様の問題は Davis and Wakerly[1] によって研究されている。

2. The Single-Fault Case

問題に対する感覚を読者に与えるために \(m=1, n=4\) の単純な場合で相互一貫性を得るための手順から始める。手順はメッセージの交換からなり、それに続いて交換の結果に基づいて相互一貫性ベクトルの計算を行う。

2 回の情報交換が必要である。最初のラウンドでプロセッサはプライベート値を交換する。第 2 ラウンドでは、第 1 ラウンドで得られた結果を交換する。もちろん、問題のあるプロセッサは "嘘をつく" し、メッセージ送信の拒否もする。故障していないプロセッサ \(p\) が他のプロセッサから期待されるメッセージを受信できない場合、\(p\) は単に値をランダムに選択し、その値が送信されたかのように動作する。

交換が完了すると故障していないプロセッサ \(p\) は、\(p\) 自身に対応する相互一貫性の要素について、そのプライベート値 \(V_p\) を記録する。他の全てのプロセッサ \(q\) に対応する要素は、受信した 3 つの \(q\) の値のレポートを調べることによって得られる (これらのうち 1 つは第1ラウンドで \(q\) から直接取得され、残りの 2 つのプロセッサは第 2 ラウンドで \(q\) から取得される)。3 つのレポートのうち少なくとも 2 つが一致する場合、過半数の値が使用される。それ以外の場合は "NIL" などのデフォルト値が使用される。

この手順によって相互一貫性が保証されることを確認するには、まず \(q\) が故障していない場合、\(p\) は \(q\) と他の故障していないプロセッサの両方から \(V_q\) を受け取ることに注目する。従って、\(p\) は希望通り \(q\) の \(V_q\) を記録する。ここで \(q\) が故障しているとすると、我々は \(p\) と他の 2 つの故障していないプロセッサが \(q\) に対して同じ値を記録することだけを示す必要がある。故障していない全てのプロセッサが NIL を記録していれば作業は完了である。そうでなければ、ある故障していないプロセッサ、例えば \(p\) は、少なくとも 2 つの他のプロセッサから非 NIL 値 \(v\) を受け取ることで \(v\) を記録する。ここで、\(p\) が故障していない他のプロセッサの両方から \(v\) を受け取った場合、故障していない全てのプロセッサは \(p\) 以外の全てのプロセッサから (おそらく \(p\) からも) \(v\) を受け取らなければならない; 従って故障していない全てのプロセッサは \(v\) を記録する。そうでなければ、\(p\) は他の故障していないプロセッサ \(p'\) 以外の全てのプロセッサから \(v\) を受け取っていなければならない。この場合、\(p'\) は \(q\) 以外の全てのプロセッサから \(v\) を受信し (つまり \(p'\) は \(v\) を記録する)、他の全ての故障していないプロセッサは \(p'\) 以外の全てのプロセッサから \(v\) を受信する。従って故障のない全てのプロセッサは必然的に \(v\) を記録する。

3. A Procedure for \(n \ge 3m+1\)

直前のセクションで説明した手順では 2 回の情報交換が必要であったことを示した。最初の交換は "my private value is" という主旨の通信であり、2 回目は "process \(x\) told me his private value is..." という主旨の通信である。\(m\) 個の故障の一般的な場合では \(m+1\) ラウンドが必要とされる。アルゴリズムを説明するためには、このメッセージ交換をより正式な方法で特徴付けることが便利である。

\(\vector{P}\) をプロセッサの集合、\(\vector{V}\) を値の集合とする。\(k \ge 1\) に対する \(k\)-レベルのシナリオを \({\rm length} \le k+1\) の \(\vector{P}\) から \(\vector{V}\) への空でない列の集合 (おそらく繰り返しを含む) として定義する。\(k\)-レベルシナリオ \(\sigma\) と列 \(w=p_1, p_2, \cdots, p_r\)、\(2 \le r \le k+1\) に対して、\(\sigma(w)\) は \(p_1\) が \(p_2\) から、\(p_2\) は \(p_3\) から、\(p_3\) は \(p_4\) から… \(p_{r-1}\) は \(p_r\) から \(p_r\) がプライベート値であることを伝える。単一要素列 \(p\) に対して、\(\omega(p)\) は単に \(p\) のプライベート値 \(\vector{V}_r\) を指定する。従って \(k\)-レベルのシナリオでは \(k\) ラウンドの情報交換の結果が要約されている。(故障しているプロセッサが誰に情報を提供したかを判断する場合、与えられた値について嘘をつく事と等価であることに注意。) また、特定の故障していないプロセッサのサブセットについては特定のマッピングのみが考えられる; 特に、故障していないプロセッサは常に情報の中継に正しいため、シナリオは正常なプロセッサ \(q\)、任意のプロセッサ \(p\)、列 \(w\) に対して \[ \sigma(pqw) = \sigma(qw) \] を満たす必要がある。

シナリオ \(\sigma\) におけるプロセッサ \(q\) が受信するメッセージは、\(p\) で始まる列に対する \(\sigma\) の制約 \(\sigma_p\) によって与えられる。任意の \(m \ge 0\), \(n \ge 3m+1\) に対してここで示している手続きは、与えられた \(\sigma_p\) に対して、各プロセッサ \(q\) に対応する相互一貫性ベクトルの要素 \(p\) の計算に関して説明されている。計算は次の通り:

  1. \({\rm size} \gt (n+m)/2\) の \(\vector{P}\) のあるサブセット \(\vector{Q}\) および値 \(v\) に対して \({\rm length} \le m\) の \(\vector{Q}\) 上の全ての列 \(w\) に対して \(\sigma_p(pwq) = v\) であるなら、\(p\) は \(v\) を記録する。
  2. そうでなければ \(m-1\), \(n-1\) に対するアルゴリズムは、\(\vector{P} - \{q\}\) 上の \({\rm length} \le m\) の全ての列 \(w\) に対して \(\vector{P}\) を \(\vector{P} - \{q\}\) に置き換え、\(\sigma_p\) を以下に定義する \(\hat{\sigma}_p\) に変換して再帰的に適用される。\[ \hat{\sigma}_p(pw) = \sigma_p(pwq) \] 再帰呼び出しで得られたベクトル内の \(n-1\) 個の要素の少なくとも \(\lfloor (n+m)/2\rfloor\) が一致する場合、\(p\) は共通の値を記録し、そうで無ければ \(p\) は NIL を記録する。

\(\hat{\sigma}_p\) は \(q\) が除外され各プロセッサの値が \(\sigma\) 内の \(q\) から直接得られた値である事に注意。またアルゴリズムは \(m=1\), \(n=4\) の場合に本質的に直前のセクションで与えられたものに帰着する事にも注意。

上記で与えられたアルゴリズムが確かに相互一貫性を保証すると言う証明は \(m\) の帰納によって導かれる:

Basis \(m=0\)。この場合、どのプロセッサも故障しておらず、アルゴリズムは常にステップ (1) で終了し、\(p\) は \(q\) に対する \(V_q\) を記録する。

Induction Step \(m \gt 0\)。最初に、\(q\) が故障していない場合、故障していないプロセッサの集合上の \({\rm length} \le m\) の各列 \(w\) (空の列を含む) に対して \(\sigma_p(pwq) = V_q\) であることに注意。この集合は \(n-m\) のメンバーを持ち (ここで \(n \gt 3m\) であるため \(\gt (n+m)/2\))、アルゴリズムのステップ (1) の \(\vector{Q}\) に対する要件を満たす。さらに、これらの要件を満たす全ての集合は故障していないプロセッサを含まなければならず (\({\rm size} \gt (n+m)/2\) と \(n \ge 3m+1\) より)、従って共通の値として \(V_q\) も得なければならない。従ってアルゴリズムはステップ (1) で終了し \(p\) は必然的に \(V_q\) と \(q\) を記録する。

ここで \(q\) が故障していると仮定する。我々は \(p\) が \(q\) に対して記録する値が、他のプロセッサ \(p'\) が \(q\) に対して記録する値と一致することを示す必要がある。

最初に適当な集合 \(\vector{Q}\) に存在する \(p\) と \(p'\) の両方がステップ (1) の手続きを終了するケースについて考える。そのような集合の全てが \((n+m)/2\) 以上のメンバーを持っており、\(\vector{P}\) が \(n\) メンバーのみを持っていることから、二つの集合は \(2((n+m)/2)-n=m\) 以上の共通のメンバーを持たなければならない。それらの少なくとも一つは故障していない必要があるため、2 つの集合は必然的に同じ値 \(v\) を生成する必要がある。

次に \(p'\) がステップ (1) で終了し、適当な集合 \(\vector{Q}\) と共通の値 \(v\) を見つけ、\(p\) がステップ (2) を実行すると仮定する。我々は \(p\) が再帰呼び出しで計算する \(\hat{\vector{Q}} = \vector{Q} - \{q\}\) 個に対応する要素は \(v\) に等しいことを主張する。\(\hat{\vector{Q}}\) は少なくとも \(\lfloor (n+m)/2 \rfloor\) 個のメンバーを持つことから、ステップ (2) に従い \(p\) は \(v\) を記録するだろう。\(\vector{Q}\) のメンバーに対応する要素が実際に \(v\) と等しいことを確認するため、再帰呼び出しでベクトルを計算するために \(p\) が使用するマッピング \(\hat{\sigma}_p\) は、\(\vector{P}-\{q\}\) 上で \({\rm length} \le m\) の列 \(w\) それぞれに対する \[ \hat{\sigma}_p(w) = \sigma(wq) \] で定義された \(m\)-レベルのシナリオ \(\hat{\sigma}_p\) の \(p\) で始まる列の制約である。帰納仮定によってこのベクトルは再帰呼び出しによって作られた \(p'\) を持つ \(\hat{\sigma}\) の制約 \(\hat{\sigma}_{p'}\) を使って計算された \(p'\) と同一である。さらに、\(\hat{\vector{Q}}\) と \(v\) がアルゴリズムのステップ (1) を満たすため、値 \(p'\) は \(\hat{\vector{Q}}\) で与えられる \(q'\) に対応するこのベクトルの要素について計算された \(v\) でなければならない。(\(\hat{\vector{Q}}\) は \({\rm size} \ge \lfloor (n+m)/2 \rfloor \gt [(n-1)+(m-1)]/2\)、\(\hat{\vector{Q}}\) 上の \({\rm length} \le m-1\) の各列 \(w\) に対して \(\sigma_{p'}(p'wq') = \sigma_{p'}(p'wq'q) = v\) であることに注意。) \(p\) がステップ (1) で終了し \(p'\) がステップ (2) で終了するケースも同様に扱われる。

残りの 1 つは \(p\) と \(p'\) がステップ (2) で終了するケースである。この場合、両方が再帰し、帰納仮定により正確に同じベクトル、つまり \(q\) に対して同じ値を算出しなければならない。Q.E.D.

4. Proof of Impossibility for \(n \lt 3m+1\)

直前のセクションの手続きは \(n \ge 3m+1\) のみの相互一貫性を保証する。このセクションでは \(3m+1\) 境界が厳しいことを示す。我々は \(m+1\) 回の情報交換で \(n \lt 3m+1\) の相互一貫性を保証することが不可能ということだけではなく、無限回の交換 (例えば \(\vector{P}\) 上の全ての空でない列から \(V\) へマッピングするシナリオを使うなど) ができるとしてもそれが不可能であることを証明する。

なぜ \(3m\) のプロセッサでは足りないかという直感を得るために 3 つのプロセッサ \(A,B,C\) の \(C\) が故障している場合について考える。正しい方法を濁すことで一貫性を得るための \(A\) と \(B\) の取り組みを \(C\) は妨げることができる。特に \(C\) から \(A\) へのメッセージは \(C\) のプライベート値が 1 で \(B\) が故障していることを示唆するようにできるし、同様に \(C\) から \(B\) へのメッセージでは \(C\) のプライベート値が 2 で \(A\) が故障していることを示唆するようにもできる。\(C\) がそのカードを正しくプレイした場合、\(A\) は \(B\) と \(C\) のどちらが故障しているか、また \(B\) は \(A\) と \(C\) のどちらが故障しているかを判断できないだろう。従って \(A\) は \(C\) の値として 1 を記録する他に選択肢がないし、\(B\) は 2 を記録しなければならず、相互一貫性を失うことになる。

不可能であることの結果とその証明の正確な記述を行うためにいくつかの公式を定義する必要がある。

最初に、シナリオを \(\vector{P}\) 上の全ての空でない列 \(\vector{P}^+\) から \(\vector{V}\) への写像を定義する。与えられた \(p \in \vector{P}\) に対して、\(p\) から始まる列から成る \(\vector{P}^+\) のサブセットから \(\vector{V}\) への写像として \(p\)-シナリオを定義する。

次に、与えられた \(\vector{N} \subseteq \vector{P}\) の故障していないプロセッサの選択と、与えられたシナリオ \(\sigma\) に対して、それぞれ \(q \in \vector{N}\), \(p \in \vector{P}\), \(w \in \vector{P}^*\) (\(\vector{P}\) 上の全ての列の集合) の時に \(\sigma(pqw) = \sigma(qw)\) であれば、\(\sigma\) は \(\vector{N}\) と一致するとする。(言い換えれば、\(\vector{N}\) 内の各プロセッサが常に真実の知っている、聞いていることを報告するとき、\(\sigma\) は常に \(\vector{N}\) と一致する。)

ここで相互一貫性の概念を以下のように定義する。各 \(p \in \vector{P}\) に対して、\(F_p\) を \(p\)-シナリオ \(\sigma_p\) とプロセッサ \(q\) を引数とし \(\vector{V}\) の値を返す写像とする。(直感的に、\(F_p\) は \(p\) が \(sigma_p\) に基づく \(q\) に対応する相互一貫性ベクトルの要素を算出する値を与える。) \(\vector{N} \subseteq \vector{P}\) の各選択に対して、\(|\vector{N}| \ge n-m\), \(\vector{N}\) と一致する各シナリオ \(\sigma\) である場合、

  1. 全ての \(p,q \in N\), \(F_p(\sigma_p, q) = \sigma(q)\) に対して
  2. 全ての \(p,q \in N\), \(r \in \vector{P}, F_p(\sigma_p, r) = F_p(\sigma_q, r)\) に対して

\(\{F_p|p \in \vector{P}\}\) は \(m\) 個の故障に対する相互一貫性を保証している。ここで \(\sigma_p\) と \(\sigma_q\) はそれぞれ \(p\) と \(q\) で始まる列に対する制限 \(\sigma\) を示す。

直感的には、節 (i) はそれぞれの故障していないプロセッサ \(p\) がそれぞれの故障していないプロセッサ \(p\) のプライベート値を正しく計算することを要求し、節 (ii) は 2 つの故障していないプロセッサがそれぞれ同じベクトルを計算することを要求している。

THEOREM . もし \(|V| \ge 2\) で \(n \ge 3m\) であるなら、\(m\) 個の故障に対する相互一貫性を保証する \(\{F_p|p \in \vector{P}\}\) は存在しない。

PROOF. 反対に \(\{F_p|p \in \vector{P}\}\) が \(m\) 個の故障に対して相互一貫性を保証すると仮定する。\(n \le 3m\) であるため、\(\vector{P}\) は 3 つの空でない集合 \(\vector{A}\), \(\vector{B}\) および \(\vector{C}\) に分割でき、それぞれは \(m\) 以下のメンバーを持つ。\(v\) と \(v'\) を \(V\) 内の 2 つの異なる値とする。我々の一般的な計画は、\(\alpha\) が \(N = \vector{A} \cup \vector{C}\)、\(\beta\) が \(N = \vector{B} \cup \vector{C}\)、\(\sigma\) が \(N = \vector{A} ^cup \vector{B}\) とそれぞれ一致するような 3 つのシナリオ \(\alpha\), \(\beta\), \(\sigma\) を構築することである。\(\vector{C}\) のメンバーは全て、プライベート値 \(v\) を \(\alpha\) に、\(v'\) を \(\beta\) に与えられるだろう。さらに \(\alpha\), \(\beta\), \(\sigma\) は、どのような \(a \in \vector{A}\) も \(\alpha\) を \(\sigma\) と区別することができず (例えば \(\alpha_a = \sigma_a\))、どのようなプロセッサ \(b \in \vector{B}\) も \(\beta\) を \(\sigma\) と区別することができない (例えば \(\beta_b = \sigma_b\) ような方法で構築されるだろう。これはシナリオ \(\sigma\) に対して \(\vector{A}\) と \(\vector{B}\) のプロセッサが \(\vector{C}\) のメンバーに対して異なる値を算出することに繋がるだろう。

我々はシナリオ \(\alpha\), \(\beta\), \(\sigma\) を以下のように再帰的に定義する:

  1. \(\vector{C}\) のメンバーで終わらない各 \(w \in \vector{P}^+\) に対して、\[ \alpha(w) = \beta(w) = \sigma(w) = v \] とする。
  2. \(a \in \vector{A}\), \(b \in \vector{B}\), \(c \in \vector{C}\) それぞれに対して、\[ \begin{array}{ccl} \alpha(c) & = & \alpha(ac) = \alpha(bc) = \alpha(cc) = v, \\ \beta(c) & = & \beta(ac) = \beta(bc) = \beta(cc) = v', \\ \sigma(c) & = & \sigma(ac) = \sigma(cc) = v, \ \ \sigma(bc) = v' \end{array} \] とする。
  3. \(a \in \vector{A}\), \(b \in \vector{B}\), \(c \in \vector{C}\), \(p \in \vector{P}\), \(w \in \vector{P}^*c\) (つまり \(w\) は \(c\) で終了する \(\vector{P}\) 上の任意の列) それぞれに対して \[ \alpha(paw) = \alpha(aw),\ \ \beta(paw) = \beta(aw) \\ \alpha(pbw) = \alpha(bw),\ \ \beta(pbw) = \beta(bw) \\ \alpha(pcw) = \alpha(cw),\ \ \beta(pcw) = \beta(cw) \\ \sigma(paw) = \sigma(aw) \\ \sigma(pbw) = \sigma(bw) \\ \sigma(pcw) = \alpha(cw) \\ \sigma(bcw) = \beta(cw) \] とする。

\(\alpha\), \(\beta\), \(\sigma\) がそれぞれ実際に \(N=\vector{A} \cup \vector{C}, \vector{B} \cup \vector{C}, \vector{A} \cup \vector{B}\) と一致していることを検査することによって検証することは容易である。さらに、全ての \(a \in \vector{A}\), \(b \in \vector{B}\), \(w \in \vector{P}^*\) に対して、\(w\) の長さの簡単な帰納証明によって \[ \alpha(aw) = \sigma(aw),\ \ \ \beta(bw) = \sigma(bw) \] であることを示すことができる。

そしてそれは相互一貫性の定義からどのような \(a \in \vector{A}\), \(b \in \vector{B}\), \(c \in \vector{C}\) に対しても \[ v = \alpha(c) = F_a(\alpha_a,c) = F_a(\sigma_a,c) = F_b(\sigma_b,c) = F_b(\beta_b,c) = v' \] を導くことになり矛盾する。Q.E.D.

5. An Algorithm Using Authenticators

前セクションの否定的な結果は、故障したプロセッサが他のプロセッサから受け取った値を渡すことを拒否するか、またはねつ造した値を渡すことができるという仮定に強く依存している。このセクションでは後者の可能性が排除された状況を扱う。言い換えれば、故障したプロセッサはそれ自身の値に "嘘をつく" ことがあり、受け取った値を中継することを拒否することができるが、自分自身が故障していることを暴露することなしに改ざんした値を中継することができない。

実際に、この仮定は認証子 (authenticator) を使用して任意の高い確率で満たすことができる。認証子は、理想的にはデータの発信元によってのみ作成されることができるデータ項目への冗長な拡張である。プロセッサ \(p\) はデータ項目 \(d\) に対して \(A_p[d]\) を計算することによって認証子を構築する。ここで \(A_p\) は \(p\) のみが知っている何らかのマッピングである。\(p\) 以外のプロセッサ \(q\) が、与えられた \(d\) に対して認証子 \(A_p[d]\) を生成できることは高い確率で不可能でなければならない。同時に、与えられた \(p\), \(v\), \(d\) に対して \(q\) が \(v = A_p[d]\) であることを検証するのが容易でなければならない。このような特性を持つマッピングを考案することは暗号理論の問題である。それらの構築方法は [2] と [3] で論議されている。故障が悪意をもった巧者ではなくランダムなエラーによる故障を想定する多くのアプリケーションでは、"適切にランダム化した" データのマッピングで十分である。

シナリオ \(\sigma\) は以下のようにして実行される。以前と同様に \(v=\sigma(p)\) が \(p\) のプライベート値を示すとする。\(p\) は 3 つの \(\langle p, a, v \rangle\) からなるメッセージを \(r\) に送信することでこの値を伝達する。ここで \(a = A_p[v]\) である。\(r\) はメッセージを受信すると \(a = A_p[v]\) であることを確認する。もしそうであれば \(r\) は \(v\) を \(\sigma(rp)\) の値であるとして受け入れる。そうでなければ、\(r\) は \(\sigma(rp)={\rm NIL}\) とする。より一般的には、もし \(r\) が \((p_1, a_1(p_2, a_2, \ldots (p_k, a_k, v), \ldots))\) 形式のメッセージを正確に 1 つだけ受信する。ここで \(a_k = A_k[v]\) であり、そして \(1 \le i \le k - 1\), \(a_i = A_i[(p_{i+1}, a_{i+1}, \ldots (p_k, a_k, v)]\) に対して \(\sigma(rp_1, \ldots, p_k) = v\) である。そうで無ければ \(\sigma(rp_1, \ldots, p_k) ={\rm NIL}\) である。

このようにして構築されたシナリオ \(\sigma\) は、全てのプロセッサ \(p \in N\), \(q \in \vector{P}\) と \(\vector{P}\) 上の列 \(w\), \(w'\) の場合、故障していないプロセッサの与えられた選択 \(N\) と一致する。

  1. \(\sigma(qpw) = \sigma(pw)\)
  2. \(\sigma(w'pw)\) は \(\sigma(pw)\) または NIL のいずれか

条件 (i) は故障していないプロセッサが常に正しく振る舞うことを保証する。条件 (ii) はプロセッサが故障していないプロセッサから受信した情報を改ざんして中継できないことを保証する。

ここで、\(m+1\)-レベルの認証されたシナリオを使用して、あらゆる \(n \ge m\) に対して相互一貫性を保証する手順を提示する。前述のように、故障していないプロセッサ \(p\) が \(\sigma_p\) に基づいて、特定のプロセッサ \(q\) について記録する値について説明されている:

\(\vector{S}_{pq}\) を全ての非 NIL 値 \(\sigma_p(pwq)\) の集合とする。ここで \(w\) は \(\vector{P} - \{p,q\}\) 上の \({\rm length} \le m\) の異なる要素の列を範囲とする。もし \(\vector{S}_{pq}\) が正確に 1 つの要素 \(v\) を持つ場合 \(p\) は \(q\) に対する \(v\) を記録する; そうでなければ \(p\) は NIL を記録する。

相互一貫性が保証されていることを確認するためにまず \(q\) が故障していないケースを考える。この場合、\(\sigma_p(pwq)\) は条件 (ii) によってそれぞれの適当な \(w\) に対して \(\sigma(q)\) か NIL のどちらかを取る。特に、(i) によって \(\sigma_p(pq) = \sigma(q)\) であるため \(\vector{S}_{pq} = \{\sigma(q)\}\) である。従って \(p\) は必然的に \(q\) に対する \(\sigma(q)\) を記録する。

もし \(q\) が故障していれば、故障していない 2 つのプロセッサ \(p\) と \(p'\) それぞれについてだけ \(\vector{S}_{pq} = \vector{S}_{p'q}\)、例えば \(\vector{P}-\{p,q\}\) 上で \({\rm length} \lt m\) の繰り返しのないある列 \(w\) に対して \(v = \sigma_p(pwq)\) を示せば十分である。(\(w=w_1 p' w_2\) として) \(p'\) が \(w\) に現れるとすると (ii) により \(\sigma(pwq) = \sigma(p'w_2 q)\) となる; 従って \(v = \sigma(pwq) \in \vector{S}_{p'q}\) である。最後に、もし \(p'\) が \(w\) に現れず \(w\) の長さが \(m\) なら、\(w\) は \(w_1 r w_2\) の形式でなければならない。ここで \(r\) は故障しておらず、\(v = \sigma(pwq) = \sigma(rw_2q)\) ((ii) により) \(= \sigma(p'rw_2q)\) ((i) により) \( \in \vector{S}_{p'q}\) である。どのようなケースでも \(v \in \vector{S}_{p'q}\) である。対称的な論議は、もし \(v \in \vector{S}_{p'q}\) であれば \(v \in \vector{S}_{pq}\) であることを示している。従って必然的に \(\vector{S}_{p'q} = \vector{S}_{pq}\) である。Q.E.D.

6. Conclusions

相互一貫性を得るという問題は実行制御が分散されているフォールトトレラントシステムの設計において非常に根本的であるように見える。SRI で開発されている SIFT [4] フォールトトレラントコンピュータでは、設計の少なくとも 3 つの側面 ─ クロック同期、センサーからの入力安定性、および診断テスト結果に関する合意で一貫性のある整合性システムが必要となる。このシステム設計の予備段階では、これらの状況を処理するために単純な過半数投票スキームが考案されることが素朴に想定されていた。単純な過半数では不十分であるという漸進的な認識はここで報告される結果に繋がった。

これらの結果は相互一貫性に関して提起できる全ての問題に答えるものではない。ここで定義されたアルゴリズムはその存在を実証することを意図している。こうりつてきなアルゴリズムと制限された通信の仮定の下で動作するアルゴリズムの構築は将来の研究のためのトピックである。考慮されるであろう他の問題には、おおよその合意に達すること、および様々な確率的仮定の下で合意に達することの問題が含まれている。

ACKNOWLEDGMENTS. The authors gratefully acknowledge the substantial contribution of ideas to this paper by K. N. Levitt, P. M. Melliar-Smith, and J. H. Wensley, and the reviewers. We are especially grateful to E. Migneault of NASA-Langley for his perceptive insights into the importance and difficulty of the problem.

REFERENCES

  1. DAVIES, D, AND WAKERLY, J. Synchronization and matching in redundant systems IEEE Trans on Comptrs. C-27, 6 (June 1978), 531-539.
  2. DIFFIE, W, AND HELLMAN, M. New directions in cryptography. IEEE Trans Inform. Theory IT-22, 6 (Nov 1976), 644-654
  3. RIVEST, R.L., SHAMIR, A, AND ADLEMAN, L A A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM 21, 2 (Feb 1978), 120-126.
  4. WENSLEY, J H., ET AL. SIFT: design and analysis of a fault-tolerant computer for aircraft control Proc. IEEE 66, 10 (Oct. 1978), 1240-1255.

RECEIVED NOVEMBER 1978; REVISED APRIL 1979; ACCEPTED MAY 1979

翻訳抄

ビザンチン故障を含むネットワークでの分散合意が可能な条件についての 1979 年の論文。