Führend Wahlalgorithmus für einen orientierten hypercube

Question

Ich bin mit einigem Problem stecken, wo ich einen Führer Wahlalgorithmus für eine orientierte hypercube zu entwerfen. Dies sollte durch ein Turnier mit einer Anzahl von Runden gleich der Abmessung D des hypercube erfolgen. In jeder Stufe d, mit 1 <= d

Answer 1

Es ist schon eine lange Zeit, da ich Systeme studierte verteilt, aber ich hoffe, das hilft ein wenig:)

Das Problem: Leader-Wahl in einem Netzwerk mit einem hypercube tolopogy. In dieser Topologie hat jeder Knoten genau D Nachbarn (wobei D die hypercube der Dimension ist). Da die hypercube ist orientiert , wissen die Knoten jeder Dimension, welche ihrer Verbindungen zu entspricht. Außerdem gehe ich davon aus, dass alle Knoten mit einiger eindeutigen ID gekennzeichnet sind, wie es typisch mit dieser Art von Problemen.

Wenn ich gut Ihre Lösung Richtlinien verstehen, scheint der Algorithmus einfach zu sein: ein Knoten genau D Zustände hat. In jedem Zustand 1 <= d <= D steht mit seinem Nachbarn entlang der d-Achse. Diese Mitteilung besteht es die ID des besten Kandidaten zu senden ist es bekannt (wenn d = 1 ist dies einfach seine eigene ID), und durch die Peer erhält sie mit der ID zu vergleichen. Jetzt ist der Knoten kennt die beste ID des Unter Würfel der Ordnung d (definiert durch die Achsen 1,2 ..., d) es gehört. Auf diese Weise wird in Schritt D alle Knoten sind sich der globalen besten, und der Algorithmus schließt mit einem Konsens.

Zum Beispiel nimmt die folgende Topologie (D = 2) und ID-Werte:

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

Die IDs in Klammern geben die besten ids von jedem Knoten bekannt, so weit.

Die erste Iteration (d = 1) arbeitet entlang der horizontalen Achse und endet wie folgt:

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

Das zweite (und letzte) Iteration (d = 2) arbeitet entlang der vertikalen Achse und endet wie folgt:

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

Die Knotennummer 4 gewählt wurde, wie erforderlich (höchste id).

Nachrichtenanzahl Komplexität

Für jede Kante in der hypercube haben wir genau 2 Nachrichten (eine auf jeder Richtung). Da die Formel für die Anzahl von Kanten in einem Hypercube der Dimension D ist E = D * 2 ^ (D-1), haben wir genau M = D * 2 ^ D-Nachrichten. Um die Komplexität als Funktion von N (die Anzahl der Knoten), Rückruf, dass N = 2 ^ D, also M = N · log N.

zu berechnen,