1

我想知道是否存在确保终止的非确定性领导者选举算法（在单向环中）。我想不出一个，也找不到一个不确定的。我发现的一些是：

  • 选择具有最高进程 ID 的节点作为领导者（确定性）并终止。

  • 随机决定一个节点是否想成为leader，如果环中有另一个节点想成为leade，则重新启动整个过程。这个不会终止，但有终止的概率。

有人可以给我一些关于如何创建分布式非确定性领导选举算法的提示吗？也许用外行的方式解释它。

感谢一切！

4

2 回答 2

1

不存在同时具有保证终止和保证正确性（只有一个领导者）的概率（匿名）领导者选举算法。如果我没记错的话，你会在 N. Lynch 关于分布式系统的书中找到一个证明。

然而，对于足够长的算法运行时间，存在对于不终止的概率限制为零的算法。此外，预期的运行时间相当短（AFIR，对于 k 个启动器，大约为 ln(k)）。

这种算法的主要思想遵循您的第二种方法。但是，不要简单地在出现多个领先者的情况下重新启动该过程，而只允许上一轮的获胜者成为下一轮的候选人。

编辑1-3：

如果您要求进行非匿名领导人选举，有几种概率算法可以保证终止。例如，采用正常的环算法并以一定的概率延迟消息，ID越小延迟的机会越大。这样，获胜机会低的消息会被更早地删除，从而导致整体消息更少。

如果您想为非匿名成员提供不同的结果，您可以例如使用两阶段算法：

  1. 执行经典的领导人选举 => 具有最高 ID 的节点 A 获胜
  2. 让 A 掷骰子来确定实际的领导者。

幸运元素也可以分布：

  1. 任何节点都知道身份集（S）（如果不知道，使用泛洪算法来判断）
  2. 所有节点随机选择一个 ouf S 的 ID 并将其发送给任何其他节点
  3. 最常被命名的 ID 获胜。如果有多个这样的 ID，则以确定的方式选择其中一个，例如中位数。

两种算法都允许终止和非确定性结果。但是，第一个具有较低的平均消息复杂度（n log n与n²；最坏情况的复杂度相同）并且更公平（即，ID 获胜的概率是均匀分布的，而第二个则不是这样算法）。我很确定，至少最后一个缺点可以通过更复杂的算法消除，但这里的问题是这种算法的普遍存在。

于 2013-03-13T21:17:08.720 回答
0

根据我对问题的理解，您实际上并不是在寻找一种选举算法，而只是一种分布式算法，可以公平地随机选择一个客户作为“领导者”，其中没有客户子集可以共同作弊。

这实际上很容易。将每个客户视为一副牌中的一张牌，然后使用心理扑克算法（一种分布式算法，公平且随机地打乱一副牌）对其进行洗牌。然后只需将第一张牌作为领导者。

于 2013-03-15T19:42:04.020 回答