algorithm - 有向超立方体的领导者选举算法

Question

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

Answer 1

我已经很长时间没有研究分布式系统了，但我希望这能有所帮助:)

问题: Leader election在具有 hypercube 的网络中拓扑学。在此拓扑中，每个节点恰好有 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。