谁能告诉我为什么提案 ID 在 Paxos 中必须是唯一的？我认为这个proposalId需要唯一的原因是我们需要用它来拒绝旧的提案并对最大投票进行排序。所以如果我们做第一阶段：acceptor 只接受大于promisedId 的proposal 并且是增量的，它仍然可以保证一致性。
我们假设proposer A 向acceptors 提出一个proposal（proposalId x, value y），然后他得到了多数人的批准，另一个proposer B 具有相同的proposal id(x) 发出一个proposal request，这个proposer B 会被拒绝，对吧? 最终，我们仍然可以达到一致性，对吧？
简短的回答是，正确性的证明取决于每一轮每个节点的唯一数字。
一个直观的答案如下：
如果集群中的节点之间的提案编号不是唯一的，您可以让两个节点为相同的编号提出不同的值。在任意消息丢失的情况下，一些节点可能会接受一个值而另一些。潜在的新领导者将询问所有节点他们接受的最高值。然后它将返回相同数字的不同值的响应。然后它不能消除歧义并决定接下来要选择哪个值以使集群保持一致。使用唯一编号可确保每个值在每一轮中都有唯一编号。这确保了新领导者可以正确选择最高可接受的值。
人为场景：
A具有领导者节点的五节点集群。网络失控了。节点B认为它需要领导，因为它怀疑节点A由于丢失消息而死亡。节点B建议与上次使用的相同的数字A。节点A和B实际上都已启动并尝试向其他节点传输不同的值。电源发生故障，所有节点都变暗，并且由于滚动电源故障导致网络中断，一些但不是所有消息都通过了。
接下来电源重新打开，但节点A并E保持死机。节点B，C和D可以组成一个仲裁。节点C提出一个新的高数字，并为最高接受值取回两个不同的值。一个来自A，另一个来自B。它现在必须在它们之间做出选择。哪个值可以保证使集群达到正确的一致性？
想象一下，在幸存的仲裁中，只有一个节点有A值，但有两个节点有B值。因此，假设我们猜测Bs 的值，但这可能是错误的。死节点A，E可能有As 值。节点A碰巧在电源故障之前看到其值的大多数响应，因为它的消息恰好通过其他两个节点。价值是一笔付款，当它看到多数人的回应时，它会将钱从公司汇出。然而，幸存的仲裁决定As 值从未发生过，并使集群与Bs 值保持一致。
修复：
您需要做的就是对每个节点进行唯一编号，并将节点唯一编号编码为选票编号的最低有效位。然后每个节点使用它唯一的数字，并且可以轻松地生成一个新数字，该数字略高于集群中使用的最后一个最高数字。如果我们这样做，那么在任何一轮中只有一个值是最高接受的。
如果最后一个领导者得到多数响应，那么任何拥有多数席位的新领导者都将看到最后一个领导者使用的最高值。新的领导者不会与它将合作的最后一个领导者相矛盾。新领导人不需要知道死去的领导人是否真的看到了多数人的反应并采取了行动。相反，它会做出保守的选择，并假设它可能有并采取适当的行动。
还有一个额外的细节可能值得指出，@ideawu 在@simbo1905 的答案的评论线程中提到了这一点。我在下面给出的答案可能更适合作为对该线程的评论，但我没有所需的 Stack Overflow 声誉来发表评论。
在 Paxos 的经典描述（例如Paxos Made Simple）中，确实要求每个提议者的选票编号/id 是唯一的，即没有两个提议者可以在同一张选票中提议一个值，并且每个提议者不能为不同的提议重复使用选票编号。我的理解是，这只是为了保证对给定选票最多提出一个值。
正如@simbo1905 指出的那样，确保提案中选票号码唯一的一种方法是为每个提案人预先分配一组不相交的选票 ID。不过，这并不是实现选票唯一性的唯一方法。如果 acceptor 要求他们响应的 prepare（阶段 1a）消息的选票号码严格大于他们最近的 promise 的选票号码，那么这可以确保提议者永远不会在给定的选票号码上发生冲突，即使不同的提议者尝试使用不同的提案使用相同的选票号码。仲裁重叠属性确保了这一点，这是 Heidi Howard 的技术报告Distributed Consensus Revised中指出的事实，在第 3.9 节中，她指出（使用术语“epoch”而不是“ballot”）：
众所周知，如果接受者要求提议者的 epoch 严格大于最后一个承诺的提议，那么 Classic Paxos 并不要求 epoch 是唯一的。这意味着对于给定的 epoch，最多有一个提议者会到达第二阶段，因为到达第二阶段需要提议者已经就第一阶段达成多数同意，从而保证唯一性。
这支持@ideawu 在上面的评论中提出的想法。因此，如果我们确保接受者的这种“严格大于”行为，则不应从外部要求选票号码的唯一性，即协议将自动执行它。
或者，如果我们允许接受者响应准备消息，其选票数大于或等于对于他们最近承诺的投票，提案的选票号码的唯一性确实不能自动得到保证。这个事实大概是 Paxos 要求全球选票号码唯一性的最初动机。然而，我们可以通过稍微修改协议来解决这个问题。我们可以在每个接受者上添加一个额外的状态，用于存储它为最新承诺的投票所响应的提议者的身份。如果它收到来自不同提议者的同一张选票的准备请求，它可以拒绝它。霍华德在参考论文部分给出了一个精确的例子。这也是采用的方法，例如，在 Raft 共识协议中，它使用每个服务器上维护的votedFor变量来实现。
您可以在此 TLA+ 规范中看到对上述概念的更正式演示，该规范扩展了 Lamport 的 Paxos 规范之一，添加了一个明确的提议者概念。请注意，规范中的任何内容都不能确保不同的提议者从不相交的集合中选择选票号码。这是使用“大于或等于”条件和模型检查仅选择单个值的安全属性时产生的错误跟踪（反例） 。当使用“严格大于”条件时，模型检查器在集合定义为（两个提议者）和Proposer{p1,p2}Nat（确定一组可能的选票）被覆盖为{1,2,3}. 这绝不是安全的证明，但它提供了一点额外的信心，即推理是正确的。