Um algoritmo eleitoral líder para um hipercubo orientado

Question

Estou com algum problema em que tenho que projetar um algoritmo eleitoral de líder para um hipercubo orientado. Isso deve ser feito usando um torneio com várias rodadas iguais à dimensão d do hipercubo. Em cada estágio d, com 1 <= d <D, dois líderes candidatos de hipercubos D-dimensionais vizinhos devem competir para se tornar o líder candidato único do hipercubo (D+1)-que é a união de seus respectivos hipercubos.

Answer 1

Faz muito tempo desde que estudei sistemas distribuídos, mas espero que isso ajude um pouco :)

O problema: Eleição líder em uma rede com um Hypercube TOLOPOGIA. Nesta topologia, todo nó tem exatamente v vizinhos (onde D é a dimensão do hipercubo). Como o hipercubo é orientado, os nós sabem qual de seus links corresponde a todas as dimensões. Além disso, presumo que todos os nós sejam rotulados com algum ID exclusivo, como típico com esse tipo de problema.

Se eu entendi bem as diretrizes de suas soluções, o algoritmo parece ser simples: um nó tem exatamente d estados. Em todos os estados 1 <= d <= d, ele se comunica com seu vizinho ao longo do eixo D. Essa comunicação consiste em enviar o ID do melhor candidato que está ciente (quando d = 1, este é simplesmente seu próprio ID) e compará -lo com o ID recebido pelo par. Agora, o nó conhece o melhor ID do subcubo da ordem D (definido por eixos 1,2 ..., d) a que pertence. Dessa forma, na etapa D, todos os nós estão cientes do melhor global, e o algoritmo é concluído com um consenso.

Por exemplo, suponha a seguinte topologia (d = 2) e valores de identificação:

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

Os IDs entre parênteses indicam os melhores IDs conhecidos por cada nó até agora.

A primeira iteração (d = 1) funciona ao longo do eixo horizontal e termina da seguinte maneira:

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

A segunda (e a última) iteração (d = 2) funciona ao longo do eixo vertical e termina da seguinte forma:

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

O nó número 4 foi escolhido, conforme necessário (ID mais alto).

Complexidade da contagem de mensagens

Para cada borda no hypercube, temos exatamente 2 mensagens (uma em cada direção). Como a fórmula para o número de arestas em um hipercubo da dimensão d é e = d*2^(d-1), temos exatamente m = d*2^D mensagens. Para calcular a complexidade em função de n (o número de nós), lembre -se de que n = 2^d, então m = n*log n.