Un algoritmo de elección de líder de un hipercubo orientada

Question

estoy atascado con algún problema en el que tengo que diseñar un algoritmo de elección de líder de un hipercubo orientado. Esto debe hacerse mediante el uso de un torneo con un número de asaltos igual a la dimensión D del hipercubo. En cada etapa d, con 1 <= d

Answer 1

Ha sido un largo tiempo desde que estudié sistemas distribuidos, pero espero que esto ayude un poco:)

El problema: elección de líder en una red con una hipercubo tolopogy. En esta topología, todos los nodos vecinos ha d exactamente (donde D es la dimensión del hipercubo). Dado que el hipercubo es orientada , los nodos saben cuáles de sus enlaces corresponde a todas las dimensiones. Además, supongo que todos los nodos están etiquetados con algún identificador único, como es típico en este tipo de problemas.

Si entiendo bien las directrices de su solución, el algoritmo parece ser simple: un nodo tiene exactamente los estados D. En cada estado 1 <= d <= D se comunica con su vecina a lo largo del eje d. Esta comunicación consiste en el envío que el id del mejor candidato es consciente de (cuando d = 1 esto es simplemente su propio ID), y comparándolo con el identificador recibida por los pares. Ahora el nodo sabe que la mejor identificación de los sub-cubo de orden d (definido por los ejes 1,2 ..., d) al que pertenece. De esta manera, en la etapa D todos los nodos son conscientes de las mejores a nivel mundial, y el algoritmo se completa con un consenso.

Por ejemplo, suponga que el siguiente topología (D = 2) y valores de ID:

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

Los ids en paréntesis indican los mejores ids conocidos por cada nodo hasta ahora.

La primera iteración (d = 1) funciona a lo largo del eje horizontal, y termina como sigue:

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

El segundo (y último) iteración (d = 2) funciona a lo largo del eje vertical, y termina como sigue:

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

El número de nodo 4 se ha elegido, como se requiere (la más alta id).

Mensaje recuento complejidad

Para todas las aristas en el hipercubo tenemos exactamente 2 mensajes (uno en cada dirección). Puesto que la fórmula para el número de bordes en un hipercubo de dimensión D es E = D * 2 ^ (D-1), tenemos exactamente m = D * 2 ^ D mensajes. Con el fin de calcular la complejidad como una función de N (el número de nodos), el recuerdo que N = 2 ^ D, por lo que M = N * log N.