Un algorithme d'élection du chef d'un hypercube orienté

Question

Je suis coincé avec un problème où je dois concevoir un algorithme d'élection du chef d'un hypercube orienté. Cela devrait être fait à l'aide d'un tournoi avec un certain nombre de rounds égal à la dimension D de l'hypercube. Dans chaque étape d, avec 1 <= d

Answer 1

Il a été longtemps que je distribuais a étudié les systèmes, mais j'espère que cela aide un peu:)

Le problème: électorale Leader dans un réseau avec un hypercube tolopogy. Dans cette topologie, chaque nœud a exactement les voisins D (où D est la dimension de l'hypercube). Depuis l'hypercube est orienté , les nœuds qui savent de leurs liens correspond à toutes les dimensions. Je suppose aussi que tous les nœuds sont étiquetés avec certains identifiant unique, comme typique avec ce genre de problèmes.

Si je comprends bien vos directives de solution, l'algorithme semble être simple: un nœud a exactement états D. Dans chaque état 1 <= d <= D il communique avec son voisin le long de l'axe d. Cette communication consiste à envoyer l'identifiant du meilleur candidat, il est au courant (quand d = 1 ceci est tout simplement son propre identifiant), et en le comparant avec l'identifiant reçu par les pairs. Maintenant, le nœud connaît le meilleur id du sous-cube d'ordre d (défini par des axes 1,2 ..., d) il appartient. De cette façon, à l'étape D tous les noeuds sont conscients des meilleurs mondiaux, et l'algorithme se termine avec un consensus.

Par exemple, supposons que la topologie suivante (D = 2) et des valeurs d'identité:

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

Les ids entre parenthèses indiquent les meilleurs ids connus par chaque nœud jusqu'à présent.

La première itération (d = 1) fonctionne le long de l'axe horizontal, et se termine comme suit:

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

La seconde (et dernière) itération (d = 2) fonctionne le long de l'axe vertical et se termine comme suit:

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

Le numéro de noeud 4 a été choisi, le cas échéant (la plus élevée id).

Compte message complexité

Pour chaque bord dans l'hypercube, nous avons exactement 2 messages (un sur chaque direction). Etant donné que la formule pour le nombre de bords dans un hypercube de dimension D est E = D * 2 ^ (D-1), on a exactement M = D * 2 ^ D messages. Afin de calculer la complexité en fonction de N (le nombre de noeuds), rappelons que N = 2 ^ D, de sorte que M = N * log n.