2

指向性超立方体のリーダー選出アルゴリズムを設計しなければならないという問題に悩まされています。これは、超立方体の次元Dに等しいラウンド数のトーナメントを使用して行う必要があります。各ステージdで、1 <= d <Dの場合、隣接するd次元超立方体の2つの候補リーダーは、それぞれの超立方体の結合である（d + 1）次元超立方体の単一の候補リーダーになるために競合する必要があります。

4

1 に答える 1

4

分散システムを勉強してから久しぶりですが、少しお役に立てば幸いです:)

問題： 超立方体のトロポジーを備えたネットワークでのリーダー選出。このトポロジでは、すべてのノードに正確に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 *logNであることを思い出してください。

于 2010-05-15T22:56:01.657 に答える