algorithm - 如果修改 Paxos 算法使得接受器接受第一个值或最近的值，该方法是否会失败？

Question

我试图推理和理解算法在这些情况下是否失败，但似乎找不到他们会失败的例子。

如果他们不这样做，那么为什么不遵循其中的任何一个？

Answer 1

是的。

不要忘记，在后面的几轮中，领导者可能会提出与前几轮不同的价值观。因此，第一条消息可能具有错误的值。

此外，消息可能会重新排序。（考虑一个节点脱机，然后重新联机以查找以随机顺序出现的消息。）最近的消息可能不是最近发送的消息。

最后，不要忘记领导者的变化。接受者越快确信它在错误的领导者身上越好。

Answer 2

与其询问算法在这种情况下是否失败，不如考虑如果每个节点看到不同的消息丢失、延迟或重新排序，节点只接受它碰巧收到的第一个消息是否正确？显然答案是否定的。

该算法设计为在无法通过查看消息上的时间戳来确定“第一个”时工作，因为不同机器上的时钟可能不同步。该算法设计为在节点之间的网络路径、距离和拥塞可能不同时工作。节点可能会崩溃并重新启动，否则会挂起并继续使事情变得更加“敌对”。

因此，一个五节点集群可以让所有两个节点都尝试成为领导者，并且所有三个节点都会看到领导者消息是“第一”的随机顺序。那么在这种情况下，正确的答案是什么？该算法具有基于其规则的“正确”答案，可确保在所有“敌对”条件下获得一致的结果。

总而言之，Paxos 的要点是，我们作为程序员的“第一”逻辑思维模型是基于对一组完美的时钟、机器和网络的假设。这在现实世界中是不存在的。要尝试更改算法是否会出现问题，您需要使用上述所有内容“攻击”消息流。在任何变化下，您可能会找到一些方法来“破坏”事物。