既知の論文Impossibility of Distributed Consensus with one Faulty Process (JACM85)で、FLP (Fisher、Lynch、および Paterson) は、完全に非同期のコンセンサス プロトコルでは、1 つの未発表のプロセスの停止さえ許容できないという驚くべき結果を証明しました。
補題 3 では、D が 0 価と 1 価の配置の両方を含むことを示した後、次のように述べています。
1 つのステップで一方が他方の結果である場合、2 つの構成ネイバーを呼び出します。簡単な帰納法により、Dᵢ = e(Cᵢ) が i 価、i = 0, 1 となる近傍 C₀, C₁ ∈ C が存在します。
彼らがそのようなC₀とC₁の存在を主張する場合を除いて、私は証明全体に従うことができます. ヒントを教えてください。
De( の要素に適用した後の可能な構成のセットC) には、0 価の構成と 1 価の構成の両方が含まれます (2 価の構成は含まれないと見なされます)。
つまり、すべての要素を0 価または 1 価の構成にeマップします。Cの定義により、一連の「隣接C」関係によって他のすべての要素に接続されているルート要素が存在する必要がありますC。の後に 1 価の構成につながるe要素。Ce
が 0 価である場合、そうでない場合は1 価でfあるようなマッピングを定義します。f(C) = 0e(C)f(C) = 1e(C)
は二価ではあり得ないため、 が二価構成を持たないe(C)と仮定すると、0 または 1 のいずれかになります。Df(C)
ツリー内の最初の二価構成からアクセス可能な構成を配置します。ツリー内にはf(C0) != f(C1). そうでない場合、すべてf(C)が同じであるため、Dすべて 0 価の構成またはすべて 1 価の構成のいずれかしかないことを意味します。
私はかつて、これらすべての論文を読む道をたどりましたが、それが完全に時間の無駄であることに気づきました。
結果はまったく驚くべきことではありません。
あなたが言及している論文「[1つの欠陥のあるプロセスによる分散コンセンサスの不可能性]」1
は複雑な数学的証明の長いリストであり、単純に次のようになります。
1) コンセンサスは決定論的な状態です
2) 環境内の 1 つ (または複数) の障害のあるシステムは、非決定論的環境です。
3) 非決定論的な環境では、決定論的な状態、アクション、または結果に到達することはできません。
終わり。これ以上考える必要はありません。
これは、学界の外の現実の世界でどのように機能するかです。
エージェントがコンセンサスに達することを望む場合は、同期 (タイミング モデル) 近似構造を追加して、特定の一連の制約内で環境を決定論的にする必要があります。たとえば、Timeouts、Ack/Nack、Handshake、Witness などの単純な構造、またはより複雑な構造です。
同期決定論的モデルに近づくほど、構造は複雑になります。仮想的な同期モデルには、無限に複雑な構造が含まれます。また、完全に決定論的な同期モデルは、非自明な分散システムでは実現できないことに注意してください。これは、変数の初期状態を持つ自明でない動的多変量システムでは、任意の時点で可能な状態、アクション、および結果が無限に存在するためです。カオス理論
ホップ番号 21 のルーターでバッファ オーバーフロー エラーが原因でドロップされた TCP パケットを検出するための構造の複雑さを考えてみましょう。