4

私は最近、Paxos について多くの調査を行ってきましたが、常に疑問に思っていたことの 1 つは、答えが見当たらないということです。

Paxos には増加する提案番号が含まれています (また、読んでいる論文の著者によっては、別のラウンド番号もある可能性があります)。そしてもちろん、リーダーになる予定の 2 人が決闘に巻き込まれ、悪循環の中でお互いが相手を追い越そうとすることもあります。しかし、私はビザンチンの P2P 環境で作業しているので、提案番号を非常に高く設定しようとする提案者についてどうすればよいかを考える必要があります。たとえば、最大 32 ビットまたは 64 ビット ワードです。

言語に依存せず、プラットフォームに依存しない Paxos ベースのプロトコルは、提案番号および/またはラウンド番号の整数の最大値をどのように処理する必要がありますか? 特に意図的/悪意のあるケースでは、オーバーフローを 0 に戻すモジュラー演算アプローチが少し魅力的ではありませんか?

4

1 に答える 1

4

私が読んだことから、これはまだ未解決の問題であり、文献では扱われていないと思います.

Byzantine Proposer Fast Paxosは、サービス拒否に対処しますが、インクリメント (提案) カウンターによるフラッディングに関連しない攻撃によってメッセージ送信を遅らせるような種類のもののみです。

そうは言っても、整数オーバーフローはおそらくあなたの問題の中で最も少ないものです。整数オーバーフローを考える代わりに、最初に (DoS による) メンバーシップ攻撃を検討することをお勧めします。いくつかのノードからのコンセンサス後にメンバーシップについて学習することは実行可能な戦略かもしれませんが、おそらくまだある程度のレベルでシビル攻撃に対して脆弱です.

もう 1 つの戦略は、大量のリクエストを制限するために、プロポーザルにプルーフ オブ ワーク システムを組み込むことです。ただし、これをバランスを取るための指標として何に使用すればよいかを判断するのは困難です (たとえば、ビットコインでブロック チェーンをマイニングするときの無料の通貨)。それは、構築しようとしているシステムのタイプに大きく依存します。システム内の情報の価値を考慮してから、回避するのに多少のコストがかかる作業証明システムを作成する必要があります。

ただし、プロポーザル カウンターの速度を下げることができるようになった後でも、(有効な) 操作の数が多いシステムでは、整数の最大値について心配する必要があります。固定精度カウンターを吹き飛ばすことなく、問題に遭遇することなくネットワークを何年/10年実行できるかを明確に判断できる、数値ラッピングまたは複数精度スキームの戦略を用意する必要があります。悪意のあるエンティティがあっても、システムが 100 年 (またはそれ以上) の間、固定精度カウンターを吹き飛ばすことなく動作すると判断できる場合は、物事を単純化することを選択できます。

もう 1 つの (重要な) 注意として、ほとんどの論文で使用されているシステム モデルは、実際の実装を実用的なものにするすべてを反映しているわけではありません ( Raftはこれに対する素晴らしい例外です)。どちらかといえば、一部の作成者は、答えが見つからない難しい問題を回避するように設計されたシステム モデルを作成したことで罪を犯しています。したがって、誰かが X がすべてを解決すると言っている場合、その人が定義した非常に具体的なシステム モデルですべてを解決することを意味しているだけであることに注意してください。これとは反対に、システム モデルは「Y は不可能」というステートメントと密接に結びついていると考える必要があります。この概念を説明する良い例は、Ben-Or コンセンサス アルゴリズムの完全な非同期メッセージ パッシングです。これは、システム モデルのステート マシンで非決定性を使用して、 FLP 不可能性の結果(システム モデルのステート マシンが決定論的である場合、コンセンサスが部分的に非同期のメッセージ パッシングを必要とすることを指定する)によって指定された制限を回避します。

したがって、「不可能」という証明を読んだ後も、「不可能」について考え続ける必要があります。Nancy Lynch は、こ​​の概念について素晴らしい記事を書いています。

私が本当に言っているのは、あなたの質問に対する良い解決策はまだ実際には存在しないということだと思います. あなたがそれを理解したら、それを公開してください(または、既存の論文を見つけたら私に知らせてください).

于 2014-02-05T16:53:58.017 に答える