4

最近、ビザンチンのフォールト トレランスに関する多くの論文を読んでいます。m 個のビザンチン障害を処理するには 3m+1 台のコンピューターが必要であるという一般的な証拠があります。一般的な証明は次のようになります。

A、B、C の 3 人の「将軍」がいます。将軍が次のように通信するとします。ここで、C は「裏切り者」です。

A --> B "Attack", A --> C "Attack"
B --> A "Attack", B --> C "Attack"
C --> A "Attack", C --> B "Retreat"

A receives "Attack" from both sources, and will attack.
B receives "Attack" from A but "Retreat" from C and doesn't know what to do.
C is a traitor, so his action could be anything.

したがって、アクターの大多数がコンセンサスに達することを保証することはできません。

私はその証明をある程度理解していますが、重要な点を見逃しているようです. A、B、C も、何をすべきかについて独自の内部計算を行っていませんか? ここでは A と B が「忠実な」将軍なので、「正しい」行動は攻撃することだと思われます。B は、何をすべきかを決定する際に、B 自身の計算を考慮することが許されませんか? その場合、彼は競合する A&C 入力の間の結びつきを簡単に破り、攻撃を決定することができます。次に、A と B の両方の攻撃を行い、問題を解決します。これは、古典的なビザンチン将軍の問題とは異なる問題ですか?

4

3 に答える 3

0

あなたが説明しているのは、すべての参加者が自分の意見を持つことができる 3 方向のコンセンサスです。ビザンチン将軍問題は、1 人の将軍が他の将軍に命令を送ることで構成されます。すべての忠実な将軍は、グループとして、命令に従うか、従わない必要があります。司令官が言ったことに全員が同意するようにすることです。

次に例を示します。

まず第一に、司令官またはビザンチンの将軍であることは簡単なケースです。あなたは他人がどう思おうと気にしません。難しい部分は、他の誰かから命令を受ける忠実な将軍であることです.

3 人の将軍が攻撃すべきかどうかを判断しようとしている場合、2 つのケースが考えられます。

  • 司令官がビザンチンの将軍である場合、2 人の将軍に異なるコマンドを送ることができます。司令官から得た情報が違うので賛成できず、賛成票と反対票が同数になってしまう。
  • ビザンチン将軍が指揮官でない場合、指揮官から得た命令について嘘をつくことができます。再び、忠実な将軍は (司令官から) 賛成 1 票、反対 1 票 (ビザンチンの将軍が嘘をついたため) を得ました。

忠実な将軍であるあなたは、指揮官が他の将軍に実際に何を言ったかを知らないので、指揮官があなたに嘘をついたのか、それとも他の将軍が嘘をついたのかわかりません。

于 2016-04-02T19:28:55.917 に答える
0

忠実な将軍は、同じ質問に対して同じ答えを返すと考えるのが一般的です。つまり、A と B の両方が「攻撃」または「後退」のいずれかを返します。しかし、BFT シナリオではそうではありません。BFT では、各忠実な将軍は問題の異なる部分を見ているため、異なる答えを出すことができます。したがって、忠実な将軍は「攻撃」と言うことができ、別の忠実な将軍は「退却」と言うことができます.

適切な使用例は、飛行機の高度センサーです。彼らは異なるデータを「見る」ため、それぞれが異なる答えを与えることができます (それらはすべて異なる場所にあり、異なる要因の影響を受けています)。

元の論文を引用するには (Lamport、1982):

信頼性を達成するための多数決の使用は、すべての正常なプロセッサが同じ出力を生成するという仮定に基づいています。これは、すべてが同じ入力を使用する限り当てはまります。ただし、単一の入力データは、単一の物理コンポーネント (たとえば、信頼性の高いコンピューターの他の回路、またはミサイル防衛システムのレーダー サイト) から取得され、誤動作しているコンポーネントが異なるプロセッサに異なる値を与える可能性があります。

ここでは投票システムが機能しません。欠陥のあるコンポーネントが相反する情報を忠実な将軍に送信して騙す可能性があるためです。つまり、C（悪意）はBに「攻撃」、Aに「退却」を送ることができます。

B (忠誠心) が「撤退」と言ったとしましょう (他はすべて同じです):

A --> B "Attack",  A --> C "Attack"
B --> A "Retreat", B --> C "Retreat"
C --> A "Attack",  C --> B "Retreat"

この例では、彼らは何もするべきではありません (同意しないため) が、A は攻撃し、B は後退します。正直なノードは、合意に達したと思っていますが、合意していません。この場合、裏切り者 C は正直者 A と B の将軍をうまく騙すことができました。

余談ですが、正直なコンポーネントが同じ答えを返すことが期待されるシナリオにいる場合は、投票システムを使用できます (Lamport 自身が彼の論文で示唆しているように)。たとえば、各ノードが同じデータを持つ RAID システムで使用できます。実際のデータとして大多数が返すものを使用するだけです。

于 2019-03-23T23:16:02.347 に答える