algorithm - 一种面向超立方体的领导者选举算法

Question

我遇到了一些问题，我必须为有向超立方体设计一个领导者选举算法。这应该通过使用轮数等于超立方体的维度 D 的锦标赛来完成。在每个阶段 d 中，当 1 <= d < D 时，相邻 d 维超立方体的两个候选领导者应该竞争成为 (d+1) 维超立方体的单个候选领导者，该超立方体是它们各自超立方体的并集。

Answer 1

很久没学分布式系统了，希望对大家有一点帮助：）

问题：具有 超立方体拓扑的网络中的领导者选举。在这个拓扑中，每个节点都有 D 个邻居（其中 D 是超立方体的维度）。由于超立方体是有方向的，因此节点知道它们的哪些链接对应于每个维度。另外，我假设所有节点都标有一些唯一的 id，这是这类问题的典型代表。

如果我很好地理解了您的解决方案指南，那么该算法似乎很简单：一个节点恰好具有 D 个状态。在每个状态 1<=d<=D 中，它沿 d 轴与其邻居通信。这种通信包括向它发送它知道的最佳候选者的 id（当 d=1 时，这只是它自己的 id），并将其与对等方接收到的 id 进行比较。现在节点知道它所属的 d 阶子立方体（由轴 1,2...,d 定义）的最佳 id。这样，在步骤 D，所有节点都知道全局最佳，算法以共识完成。

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

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

括号中的 id 表示迄今为止每个节点已知的最佳 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*log N。