Un algorithme d'élection de leader pour un hypercube orienté

Question

Je suis coincé avec un problème où je dois concevoir un algorithme d'élection de leader pour un hypercube orienté. Cela devrait être fait en utilisant un tournoi avec un nombre de tours égal à la dimension D de l'hypercube. Dans chaque étape d, avec 1 < = d < D deux leaders candidats d'hypercubes voisins d-dimensionnels doivent rivaliser pour devenir le seul candidat leader de l'hypercube (d + 1) -dimensional qui est l'union de leurs hypercubes respectifs.

Answer 1

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

Le problème:Leader election dans un réseau avec un hypercube tolopogy. Dans cette topologie, chaque nœud a exactement D voisins (où D est la dimension de l'hypercube). Puisque l'hypercube est orienté, les nœuds savent lequel de leurs liens correspond à chaque dimension. En outre, je suppose que tous les nœuds sont étiquetés avec un identifiant unique, typique de ce type de problèmes.

Si je comprends bien les directives de votre solution, l'algorithme semble être simple: un nœud a exactement les états D. Dans chaque état 1 < = d < = D il communique avec son voisin le long de l'axe d. Cette communication consiste à lui envoyer l'id du meilleur candidat dont il a connaissance (quand d = 1 c'est simplement son propre id), et à le comparer à l'identifiant reçu par le pair. Maintenant, le nœud connaît le meilleur id du sous-cube d'ordre d (défini par les axes 1,2 ..., d) auquel il appartient. De cette façon, à l'étape D, tous les nœuds sont conscients du meilleur global, et l'algorithme se termine par un consensus.

Par exemple, supposons que la topologie suivante (D = 2) et les valeurs id:

(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 de la manière suivante:

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

Le deuxième (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, si nécessaire (identifiant le plus élevé).

Le nombre de messages complexité

Pour chaque bord dans l'hypercube, nous avons exactement 2 messages (un sur chaque direction). Puisque la formule pour le nombre d'arêtes dans un hypercube de dimension D est E = D * 2^(D-1), nous avons exactement M = D * 2^D messages. Pour calculer la complexité en fonction de N (le nombre de nœuds), rappelez que N = 2^D, donc M = N * log N.