distributed-computing - 在 paxos 中，如果提议者在其提议被拒绝后出现故障，会发生什么情况？

Question

在这个图中，X 的提议被拒绝了。

在时间线结束时，S1 和 S2 接受 X，而 S3、S4 和 S5 接受 Y。提议者 X 现在应该重新发送值为 Y 的提议。

但是如果提议者 X 在那个时候倒下了会发生什么？S1 和 S2 最终如何学习 Y 值？

提前致谢！

标签： distributed-computingdistributed-systemdistributed-transactionspaxos

Answer 1

从您共享的图表片段中很难回答这个问题，因为尚不清楚它的确切含义。如果您可以链接到该图表的来源，这将很有帮助，以便我们可以看到您问题的更多上下文。这个答案的其余部分是基于对其含义的猜测。

Paxos 中有三个不同的角色，通常称为提议者、接受者和学习者，我认为将事物划分为这三个角色有助于理解。您共享的图表看起来像是在说明一组五个接受者以及它们作为基本 Synod 算法（又名单实例 Paxos）的一部分发送的消息。一般来说，系统中的学习者集和接受者集之间没有关系：可能只有一个学习者，也可能有数千个，我认为将这些概念分开是有帮助的。由于 S1 和 S2 是接受者，而不是学习者，因此询问他们学习价值是没有意义的。然而，询问如何处理没有学习价值的学习者是有效的。

在实际系统中，通常还有另一个领导者角色，负责使用超时、重试和故障检测器等推动系统向前发展，以确保所有学习者最终都学习到选择的值或死去尝试，但这超出了范围这里似乎说明了基本算法。换句话说，这个算法保证安全（“没有坏事发生”）但不保证活跃性（“有好事发生”）。如果一些学习者从未学习过选择的值，这是可以接受的。

领导者可以做各种事情来确保所有的学习者最终都学习到所选择的价值。最简单的策略之一是从任何学习者那里获取学习值并将其广播给其他学习者，只要至少有一个正在运行的学习者成功学习了所选值，这种方法就很有效并且有效。如果没有这样的学习者，领导者可以触发另一轮算法，这通常会导致学习到所选择的值。如果没有，那么它唯一的选择是重试，并继续重试，直到最终其中一轮成功。