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