指向性ハイパーキューブのリーダー選出アルゴリズム

Question

指向性ハイパーキューブのリーダー選出アルゴリズムを設計する必要があるという問題で立ち往生しています。これは、ハイパーキューブの次元 D に等しいラウンド数のトーナメントを使用して行う必要があります。各ステージ d では、1 <= d < D で、隣接する d 次元ハイパーキューブの 2 つのリーダー候補が、それぞれのハイパーキューブを結合した (d+1) 次元ハイパーキューブの単一のリーダー候補になるために競合する必要があります。

Answer 1

分散システムを勉強してから長い時間が経ちましたが、これが少しでも役立つことを願っています:)

問題： リーダー選挙 とのネットワーク内で ハイパーキューブ トロポジー。このトポロジでは、すべてのノードにちょうど D 個の近傍ノードがあります (D はハイパーキューブの次元です)。ハイパーキューブなので、 指向性のある, 、ノードは、どのリンクがすべての次元に対応するかを知っています。また、この種の問題ではよくあることですが、すべてのノードには何らかの一意の ID が付けられていると想定します。

解決策のガイドラインをよく理解していれば、アルゴリズムは単純だと思われます。ノードには正確に D 状態があります。1<=d<=D のすべての状態で、d 軸に沿って隣接する状態と通信します。この通信は、認識している最良の候補の ID (d=1 の場合、これは単に自身の ID) を送信し、それをピアが受信した ID と比較することで構成されます。これで、ノードは、それが属する次数 d (軸 1、2...、d によって定義される) のサブキューブの最適な ID を認識します。このようにして、ステップ D ですべてのノードがグローバル ベストを認識し、アルゴリズムは合意を得て完了します。

たとえば、次のトポロジ (D=2) と ID 値を想定します。

   (1)    (2)
    1-----2
    |     |
    |     |
    4-----3
   (4)    (3)

括弧内の ID は、これまでに各ノードで認識されている最良の ID を示します。

最初の反復 (d=1) は水平軸に沿って動作し、次のように終了します。

   (2)    (2)
    1-----2
    |     |
    |     |
    4-----3
   (4)    (4)

2 番目 (最後の) の反復 (d=2) は垂直軸に沿って動作し、次のように終了します。

   (4)    (4)
    1-----2
    |     |
    |     |
    4-----3
   (4)    (4)

必要に応じて、ノード番号 4 が選択されています (最も高い ID)。

メッセージ数の複雑さ

ハイパーキューブのすべてのエッジに対して、正確に 2 つのメッセージ (各方向に 1 つ) があります。次元 D のハイパーキューブ内のエッジの数の公式は E=D*2^(D-1) であるため、正確に M=D*2^D のメッセージが得られます。N (ノード数) の関数として複雑さを計算するには、N = 2^D であるため、M=N*log N であることを思い出してください。