The Byzantine Generals Problem

July 31, 2021

ビザンチン将軍問題は、故障したコンポーネントが別のコンポーネントに誤ったメッセージを送りうるとき、コンポーネント間でメッセージを交換した結果、全コンポーネントが一つの正しいメッセージを合意する手段を問う。 2つのアルゴリズムがあり、署名付きメッセージを使うかどうかで分かれる。 署名付きメッセージを使うと、受信したメッセージが改ざんされたかをコンポーネントが判断できる。 署名を使わない場合、3分の2より多くのコンポーネントが正常でなければシステム全体が正しい1つのメッセージについて合意にできないことを示した。

署名を使わないアルゴリズムをOral Message algorithm OM(\(m\))という。 \(m\)は誤ったメッセージを送りうるコンポーネントの数である。 ここで、\(n\)をコンポーネントの総数として、与えられた引数から大半を占める値を返す関数\(\text{majority}(v_1,\dots , v_{n-1})\)を定義する。 「大半を占める」の定義には、\(v_i\)に順序関係があれば、中央値を選ぶ。 順序関係がなく過半数が同じ値であれば、その値を選ぶ。それ以外では\(\texttt{RETREAT}\)を返す関数にする。

このとき、OM(\(0\))は次の手順をとる。

  1. コンポーネント(commander)は、ほかのコンポーネント(lieutenant)に値を送る。
  2. 各lieutenantは、commanderから受信した値を使う。受信していなければ\(\texttt{RETREAT}\)を使う。

OM(\(m\))は、再帰的な手続きであり、\(m>0\)の場合は次の手順にしたがう。

  1. commanderは各lieutenantに値を送る。
  2. lieutenant \(i\)は、commanderとして、値\(v_i\)を受信した場合は\(v_i\)を、そうでなければ\(\texttt{RETREAT}\)を、OM(\(m-1\))にしたがって、ほかの\(n-2\)のlieutenantに送る。
  3. \(i\neq j\)とする。lieutenant \(i\)がlieutenant \(j\)から2.で受信したメッセージ、もしくは、受信していなければ\(\texttt{RETREAT}\)を\(v_j\)とみなして、lieutenant \(i\)は\(\text{majority}(v_1,\dots , v_{n-1})\)に合意する。

署名付きメッセージを使うアルゴリズムSM(\(m\))は、順序関係のあるメッセージを仮定し、\(\text{majority}\)のかわりに、関数を\(\text{choice}\)を使う。 \(\text{choice}\)は、\(\text{choice}(\{v\})=v\), choice\((\emptyset) =\texttt{RETREAT}\)でなければならない。 集合の要素が2つ以上である場合は、中央値を返すと自然な定義になる。

\(i\)の署名付きの値\(x\)を\(x:i\)で表す。 このとき、\(v:j:i\)は、\(j\)の署名つき値\(v:j\)に対して、\(i\)が署名した値を示す。

lieutentnt \(i\)は、署名付きの値の集合\(V_i\)をもち、次の手順にしたがう。

  1. \(V_i = \emptyset\)に初期化する。
  2. commander(0) が署名付きの値をlieutenantに送る。
  3. 各\(i\)について
    1. lieutenant \(i\)が\(v:0\)を受信し、ほかの値を受信していないなら、\(V_i\)を\(\{v\}\)とし、\(v:0:t\)をほかのlieutenantに送る。
    2. \(i\)が署名付き値\(v:0:j_1:\cdots :j_k\)を受信し、\(v\)が\(V_i\)の要素でなければ
      1. \(v\)を\(V_i\)に加える。
      2. \(k< m \)であれば、\(v:0:j_1:\cdots :j_k:i\)を\(j_1,\dots j_k\)以外のlieutenantに送る。
  4. 各\(i\)について、lieutenant \(i\)にメッセージがこなくなったら、\(\text{choice}(V_i)\)の値に合意する。

論文をこちらからダウンロードできます。