异步无向树中的领导者选举

Question

我有一个异步网络无向树（V，E），其中n = | V |流程。我对我的网络唯一了解的是，所有进程都有唯一的ID（UID），他们知道邻居的数量，但是他们不知道网络的直径和大小。我试图在这样的网络中构建领导者选举算法，如下所示：

  A convergecast of <leader> messages is initiated starting from the 
  leaves of the tree. 

  Each leaf node is initially enabled to send a <leader> message to 
  its unique neighbor. Any node that receives <leader> messages from 
  all but one of its neighbors is enabled to send an <leader> message 
  to its remaining neighbor.

  In the end,
    1. Some particular process receives <leader> messages along all
    of its channels before it has sent out an <leader> message
     the process at which the <leader> messages converge elects
    itself as the leader.

    2. <leader> messages are sent on some particular edge in both
    directions.
    the process with the largest pid among the processes that are
    adjacent to this edge elects itself as the leader.

我的想法正确吗，以上算法是否在知道领导者的所有过程中终止？

Answer 1

您的算法是正确的，但具有以下限制：

1. 节点现在仅是其下一个领导者，而不是全局领导者。我不知道您的目标是每个节点都认识全球领导者还是其个人领导者。
2. 全局领导者不一定是具有最大pid的过程，也不是树的根节点。示例：假设有5个节点的链，第二个节点为根。此图是一棵树，第一和第五个节点为叶。给根节点最大的pid。您的算法选择了链的第三个节点作为全局领导者。
3. 您的算法实际上不是确定性的：假设有一棵平衡树。假设一次请假延迟提交领导信息（实际上可能发生）。选择的全球领导者取决于延迟。
4. 您的算法仅适用于树木。

我不知道这些限制对您是否有问题。由于我的信誉不足，无法对您的问题发表评论，因此我也无法提出要求。

算法的正确性可以通过数学归纳证明。

1. 基本情况：具有单个节点的树。显然，您的算法是正确的。

2. 归纳步骤：将节点添加到树中。有两种情况：

   a）新节点连接到以前不是叶的节点。

   b）新节点连接到先前为叶的节点。

   在两种情况下都不难证明算法的输出正确。因此，该算法对于所有树木都是正确的。