用于面向超立方体的领导者选举算法

Question

我坚持了一些问题，其中我要设计的领导者选举算法用于面向超立方体。这应该通过使用与比赛了数发子弹来完成等于超立方体的尺寸d。在每个阶段d，1 <= d

Answer 1

以来，它一直我研究分布式系统很长一段时间，但我希望这有助于一点：）

<强>的问题： 领导人选举与网络中 超立方体 tolopogy。在这种拓扑结构中，每个节点恰有ð邻居（其中d是超立方体的尺寸）。由于超立方体是取向的，节点知道哪个其链接的对应于每个维度。另外，我假设所有节点被标记有一些独特的ID，如与典型的这类问题。

如果我的理解以及解决方案的指导方针，该算法似乎很简单：一个节点恰好有d状态。在每一个国家1 <= d <= d它与它的沿d轴的邻居通信。该通信包括发送它的最佳候选者的ID的它知道的（当d = 1，这是简单地其自身的ID），以及与由所述对等体接收到的ID比较它。现在节点知道顺序d的子立方体的最好的ID（由轴线限定的1,2 ...，d）它属于。通过这种方式，在步骤d的所有节点都知道有一个共识，全球最好的，算法完成的。

例如，假设以下的拓扑（d = 2）和id的值：

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

在括号中的IDS表示到目前为止由每个节点目前已知最好的id

在第一次迭代（d = 1）沿水平轴的工作原理，和终止如下：

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

在第二个（和最后）一次迭代（d = 2）沿垂直轴的工作原理，和终止如下：

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

节点编号4已被选择，根据需要（最高ID）。

<强>消息计数复杂

有关在我们恰好具有2个消息（一个在每个方向）的超立方体的每个边缘。由于用于边缘在尺寸d的超立方体的数目公式为E = d * 2 ^（d-1），我们有恰好M = d * 2 ^ d消息。在为了计算复杂度的N（节点的数目）的函数，回想N = 2 ^ d，因此M = N *日志N