0

同期ネットワークのコンテキスト内でのLCRとFloodmaxの実際的な違いを理解しようとしています。

Floodmaxの時間計算量はO（N）であり、本質的に次のように機能することを理解しています。

  • すべてのプロセスは、これまでに確認した最大のUID（最初は独自のUID）を保持します。
  • 各ラウンドで、各プロセスはこの最大値をすべての発信ネイバーに送信します。
  • 直径が丸められた後、最大値がプロセスのUIDである場合は、それ自体がリーダーを選択します。それ以外の場合は、非リーダーになります。

一方、LCR：

  • 各プロセスは、そのUIDをリングの周りに送信します。プロセスがUIDを受信すると、これを自身のUIDと比較します。
  • 着信UIDが大きい場合、このUIDを次のプロセスに渡します。
  • 着信UIDが小さい場合、それは破棄されます。
  • それが等しい場合、プロセスはそれ自体をリーダーとして宣言します。

それもO（N）の時間計算量を持っています。したがって、本質的に、両方のアルゴリズムはトークンリングネットワークでUIDを渡します。2つの間に本当の違いや利点はありますか？

4

1 に答える 1

2

その名前が示すように、FloodMax アルゴリズムはネットワークをメッセージで「フラッディング」します。LCR とは異なり、FloodMax はネットワーク トポロジがリングでなくても機能します。FloodMax アルゴリズムの前提条件は、ネットワークの直径が既知である必要があり (LCR ではこれは当てはまりません)、直径ラウンドの時間の複雑さを持っていることです。一方、LCR では、ネットワークの直径を知る必要はありません。このため、リーダーは自分自身を選択した後に終了するように他のすべてのプロセスに通知する必要があるため、追加の通信オーバーヘッドが必要になります。

于 2013-01-21T20:16:53.163 に答える