algorithm - 分布式系统 : Leader Election

Question

我目前正在分布式系统上工作，我们必须在其中实现某种 Leader Election .问题是我们想避免所有计算机都必须相互认识——但只有领导者。有没有一种快速的方法可以让我们使用例如广播来实现我们想要的？

或者我们是否只需要知道至少一个，就可以进行良好的领导者选举？

假设所有计算机都在同一个子网上。

感谢您的帮助。

Answer 1

The problem is that we would like to avoid that all computers have to know each other - but only the leader.

领导者选举是从一组潜在的领导者候选人中选出一个领导者的问题。将其视为具有两个必需属性: active 和安全性。在这里，活跃性 意味着“大多数时候，有一个领导者”，而安全性 意味着“有零个或一个领导者”。让我们考虑如何使用广播解决您示例中的此安全属性。

让我们选择一个简单的(损坏的)算法，假设每个节点都有一个唯一的 ID。每个节点广播其 ID 并进行监听。当收到比自己更高的 ID 时，它会停止参与。如果它接收到的 ID 比它自己的 ID 低，它会再次发送自己的广播。假设一个同步网络，每个人收到的最后一个 ID 是领导者的 ID。现在，介绍一个网络分区。该协议(protocol)将愉快地在分区的任一侧继续进行，并且将选出两位领导者。

对于这个损坏的协议(protocol)是这样，但对于所有可能的协议(protocol)也是如此。如果您不知道(至少)有多少节点存在，您如何区分无法通信的节点和不存在的节点？因此，第一个安全结果是:您需要知道存在多少个节点，否则您无法确保只有一个领导者。

现在，让我们将安全 约束放宽为概率约束:“可以有零个或多个领导者，但大多数时候只有一个”。这使得问题变得容易处理，一个广泛使用的解决方案是八卦(流行病协议(protocol))。例如，参见 A Gossip-Style Failure Detection Service其中讨论了这个确切问题的变体。这篇论文主要关注概率正确的故障检测和枚举，但如果你能做到这一点，你也可以进行概率正确的领导人选举。

据我所知，如果不至少枚举参与者，就无法在一般网络中进行安全的非概率领导人选举。