我想知道是否存在确定终止的非确定性领导者选举算法（在单向环中） . 我想不出一个，也找不到一个不确定的 . 我发现的一些是：
选择具有最高进程ID的节点作为领导者（确定性）并终止 .
随机决定节点是否想要成为领导者，如果在环中有另一个节点想要成为领导者，则重新启动整个过程 . 这个没有终止，但有终止的可能性 .
有人可以给我一些关于如何创建分布式非确定性leade选举算法的提示吗？也许用外行术语来解释它 .
谢谢你的一切！
不存在具有保证终止和保证正确性（仅一个领导者）的概率（匿名）领导者选举算法 . 如果我没记错的话，你会在N. Lynch的分布式系统书中找到证据 .
然而，对于算法的足够长的运行时间，存在对于非终止的概率极限为零的算法 . 此外，预期的运行时间相当短（AFIR，对于k个启动器，顺序为ln（k）） .
这种算法的主要思想遵循第二种方法 . 但是，如果有几位领导者，不要简单地重启这个过程，但只允许最后一轮的获胜者成为下一轮的候选人 .
EDIT 1-3:
如果你要求非匿名领导者选举，有几种概率算法可以保证终止 . 例如，采用正常的环算法并以一定的概率延迟消息，ID越小，延迟的机会越大 . 通过这种方式，获胜机会较低的消息会被更早删除，从而减少整体消息 .
如果您希望非匿名成员获得不同的结果，您可以例如使用两阶段算法：
执行经典领导者选举=>具有最高ID的节点A获胜
让A掷骰子以确定真正的领袖 .
也可以分发偶然因素：
任何节点都知道身份集（S）（如果没有，请使用泛洪算法来判断）
所有节点偶然选择ouf S的ID并将其发送到任何其他节点
最常命名的ID获胜 . 如果存在多于一个这样的ID，则以确定的方式选择它们中的一个，例如中值 .
对于两种算法都给予终止和非确定性结果 . 然而，第一个具有较低的平均消息复杂度（n = 427230_ n对n²;最坏的情况复杂性是相同的）并且更公平（即，ID获胜的概率是等分布的，对于第二个是不正确的算法） . 我很确定，至少最后一个缺点可以通过更复杂的算法消除，但这里的问题是这种算法的普遍存在 .
根据我对这个问题的理解，你实际上并不是在寻找一种选举算法，只是一种分布式算法，可以公平地随机选择一个客户作为“领导者”，其中没有任何客户端可以共同作弊 .
这实际上非常简单 . 将每个客户端视为一副卡片中的卡片，然后使用mental poker算法（这是一种分布式算法来公平地随机地改组一副卡片）来对其进行随机播放 . 然后把第一张牌作为领导者 .
2 回答
不存在具有保证终止和保证正确性（仅一个领导者）的概率（匿名）领导者选举算法 . 如果我没记错的话，你会在N. Lynch的分布式系统书中找到证据 .
然而，对于算法的足够长的运行时间，存在对于非终止的概率极限为零的算法 . 此外，预期的运行时间相当短（AFIR，对于k个启动器，顺序为ln（k）） .
这种算法的主要思想遵循第二种方法 . 但是，如果有几位领导者，不要简单地重启这个过程，但只允许最后一轮的获胜者成为下一轮的候选人 .
EDIT 1-3:
如果你要求非匿名领导者选举，有几种概率算法可以保证终止 . 例如，采用正常的环算法并以一定的概率延迟消息，ID越小，延迟的机会越大 . 通过这种方式，获胜机会较低的消息会被更早删除，从而减少整体消息 .
如果您希望非匿名成员获得不同的结果，您可以例如使用两阶段算法：
执行经典领导者选举=>具有最高ID的节点A获胜
让A掷骰子以确定真正的领袖 .
也可以分发偶然因素：
任何节点都知道身份集（S）（如果没有，请使用泛洪算法来判断）
所有节点偶然选择ouf S的ID并将其发送到任何其他节点
最常命名的ID获胜 . 如果存在多于一个这样的ID，则以确定的方式选择它们中的一个，例如中值 .
对于两种算法都给予终止和非确定性结果 . 然而，第一个具有较低的平均消息复杂度（n = 427230_ n对n²;最坏的情况复杂性是相同的）并且更公平（即，ID获胜的概率是等分布的，对于第二个是不正确的算法） . 我很确定，至少最后一个缺点可以通过更复杂的算法消除，但这里的问题是这种算法的普遍存在 .
根据我对这个问题的理解，你实际上并不是在寻找一种选举算法，只是一种分布式算法，可以公平地随机选择一个客户作为“领导者”，其中没有任何客户端可以共同作弊 .
这实际上非常简单 . 将每个客户端视为一副卡片中的卡片，然后使用mental poker算法（这是一种分布式算法来公平地随机地改组一副卡片）来对其进行随机播放 . 然后把第一张牌作为领导者 .