Un algoritmo di elezione leader di un ipercubo orientata

Question

mi sono bloccato con qualche problema di dove devo progettare un algoritmo di elezione leader di un ipercubo oriented. Questo dovrebbe essere fatto utilizzando un torneo con un numero di giri pari alla dimensione D dell'ipercubo. In ogni fase d, con 1 <= d

Answer 1

E 'stato un lungo periodo di tempo da quando ho studiato sistemi distribuiti, ma spero che questo aiuta un po':)

Il problema: elezione leader in una rete con un ipercubo tolopogy. In questa topologia, ogni nodo è esattamente vicini D (dove D è la dimensione del ipercubo). Dal momento che l'ipercubo è orientato , i nodi si sa quale dei loro legami corrisponde a ogni dimensione. Inoltre, presumo che tutti i nodi sono etichettati con un po 'di ID univoco, come tipico di questo tipo di problemi.

Se ho capito bene le vostre linee guida di soluzione, l'algoritmo sembra essere semplice: un nodo ha esattamente gli stati D. In tutti gli stati 1 <= d <= D comunica con il suo vicino lungo l'asse d. Questa comunicazione si compone di inviarlo l'id del miglior candidato è a conoscenza (quando D = 1 questo è semplicemente il proprio id), e nel confronto con l'id ricevuta dal peer. Ora il nodo conosce meglio id del sub-cubo di ordine d (definito da assi 1,2 ..., d) appartiene. In questo modo, al passo D tutti i nodi sono a conoscenza delle Completa globali migliori, e l'algoritmo con un consenso.

Per esempio, assumere la seguente topologia (D = 2) e valori id:

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

I ids in parentesi indicano le migliori ids conosciuti da ciascun nodo finora.

La prima iterazione (d = 1) lavori lungo l'asse orizzontale, e termina come segue:

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

Il secondo (e ultimo) iterazione (d = 2) funziona lungo l'asse verticale, e termina come segue:

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

Il numero di nodo 4 è stato scelto, come richiesto (ID massimo).

Messaggio conteggio complessità

Per ogni vantaggio nel ipercubo abbiamo esattamente 2 messaggi (uno per ogni direzione). Poiché la formula per il numero di archi in un ipercubo di dimensione D è E = D * 2 ^ (D-1), abbiamo esattamente M = D * 2 ^ D messaggi. Per calcolare la complessità come funzione di N (il numero di nodi), richiamo che N = 2 ^ D, quindi M = N * log-N.