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

Question

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

Answer 1

很久没研究分布式系统了，希望对大家有所帮助:)

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

括号中的 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。