paxos - 为什么paxos proposalId需要是唯一的

Question

谁能告诉我为什么提案 Id 在 Paxos 中需要是唯一的？
我认为这个proposalId需要唯一的原因是我们需要使用它来拒绝旧提案并对最大投票进行排序。所以如果我们做第一阶段:acceptor 只接受大于promiseId 的提议并且是增量的，它仍然可以保证一致性。

我们假设提议者 A 向接受者提出了一个提议 (proposalId x, value y)，然后他得到了多数同意的答复，另一个具有相同提议 id(x) 的提议者 B 发出提议请求，这个提议者 B 将被拒绝，对吧?最终，我们仍然可以达到一致性，对吧？

Answer 1

简短的回答是正确性的证明取决于每轮每个节点的唯一数字。

一个直观的答案如下:

如果提议编号在集群中的节点之间不唯一，您可以让两个节点为同一编号提议不同的值。在任意消息丢失的情况下，一些节点可能接受一个值，而一些则接受另一个值。潜在的新领导者将询问所有节点他们接受的最高值。然后它会得到相同数字的不同值的响应。然后它无法消除歧义并决定下一个选择哪个值以使集群保持一致性。使用唯一编号可确保每个值在每一轮中都有唯一编号。这确保了新的领导者可以正确选择最高的接受值。

人为场景:

具有节点 A 的五节点集群领导人。网络出问题了。节点 B认为它需要领先，因为它怀疑节点 A由于丢失消息而死亡。节点 B提出与 A 最后使用的相同的号码.节点 A和 B实际上都已启动并尝试将不同的值传输到其他节点。电源出现故障，所有节点都变暗，并且由于滚动电源故障导致网络中断，因此一些但并非所有消息都能通过。

接下来电源恢复，但节点 A和 E死了。节点 B , C和 D可以形成法定人数。节点 C提出一个新的高数，并为最高接受值取回两个不同的值。一个源于A另一个来自 B .现在它必须在它们之间做出选择。哪个值可以保证使集群达到正确的一致性？

想象一下，在幸存的仲裁中，只有一个节点具有 A值但两个节点具有 B值(value)。假设我们猜 B s 值，但这可能是错误的。死节点A和 E可能有 A s 值。节点 A碰巧看到在电源故障之前对其值的大多数响应，因为它的消息碰巧通过了其他两个节点。该值(value)是一笔付款，当它看到大多数人的回应时，它会将钱从公司中发出。然而幸存的法定人数决定 A s 值从未发生并使集群与 B 保持一致s 值。

修复:

您需要做的就是对每个节点进行唯一编号，并将节点唯一编号编码为选票编号的最低有效位。然后每个节点使用它唯一的数字，并且可以轻松生成一个新数字，该数字仅高于集群中使用的最后一个最高数字。如果我们这样做，只有一个值将是任何一轮接受的最高值。

如果最后一个领导者得到多数响应，则任何拥有多数的新领导者将看到最后一个领导者使用的最高值。新的领导者将不会与它将合作的最后一个领导者发生冲突。新的领导者不需要知道死去的领导者是否真的看到了多数响应并采取了行动。相反，它做出了保守的选择，并假设它可能有并采取适当的行动。