我正在研究 Paxos 提出的简单论文，并且我正在努力解决这样一个事实，即如果 2 个提议者以更高的提议数量相互竞争，Paxos 不能保证进度，并且正如论文中所建议的那样，为了保证进度，必须是杰出的提议者选择这使他成为领导者。
但是问题来了，因为人们建议使用 Paxos 来选举杰出的提议者，这再次需要领导者来保证进度。
我知道给定的场景可能是特定于实现的，例如，如果给进程选择的区分集是有序的，我的意思是 P1 集 < P2 集。
但我想了解在实际实现中这是如何处理的？
问问题
386 次
1 回答
2
通常的方法是简单地使用随机超时，其中延长领导者决斗的可能性较低。如果您在论文中搜索“超时”，那么它会提到这一点。
如果一个稳定的领导者出现并取得进展平均需要 X 秒（我们可以使用最小的消息往返次数来估计），那么我们可以简单地让每个节点在某个时间间隔内随机超时，该时间间隔是 X 的倍数。通过在每次尝试成为领导者时使用一个新的随机数，我们延长领导者决斗的概率很低。
如果我们将 X 的更大倍数设置为随机超时的上限，我们就有更低的领导者对决的概率。然而，在领导者出现之前，我们也有更长的平均时间。所以这是一个权衡。
如果一个实现需要一个非常快速的故障转移，我们可以使用一个低超时随机间隔，但尝试实现一个领导者决斗快速解决的机制。您可以发明任意机制。
确保一个节点具有成为领导者的优势的简单机制如下。每个节点都有一个唯一的编号，用于对其选票进行排序。在领导者决斗期间，每个节点都可以使用指数退避，该退避由其自己的唯一编号进行缩放。例如，如果每次尝试成为领导者失败时节点编号为 N，我们可以将其超时窗口的上限乘以 1+1/N。这意味着在任何决斗中，具有最高 N 的节点将更积极地尝试成为领导者，因为其他节点将更快地退避。
于 2017-02-15T19:44:52.550 回答