为什么paxos proposalId需要是唯一的
why does paxos proposalId need to be unique
谁能告诉我为什么提案Id在Paxos中需要是唯一的？
我认为这个 proposalId 需要唯一的原因是我们需要用它来拒绝旧提案并对最大投票进行排序。所以如果我们做第一阶段：acceptor只接受大于promisedId的proposal并且是增量的，还是可以保证一致性的。
我们假设proposer A向acceptor提出了一个提案(proposalId x, value y)，然后他得到了多数赞成的答复，另一个具有相同proposal id(x)的proposer B发出了proposal request，这个proposer B会被拒吧？最终，我们仍然可以达到一致性，对吗？
简短的回答是正确性的证明取决于每一轮每个节点的唯一数字。
一个直观的答案如下：
如果建议编号在集群中的节点之间不是唯一的，您可以让两个节点为相同的编号建议不同的值。在任意消息丢失的情况下，一些节点可能接受一个值而另一些节点接受另一个值。一个潜在的新领导者将向所有节点询问他们的最高接受值。然后它会得到相同数字的不同值的响应。然后它不能消除歧义并决定下一个要选择哪个值以使集群保持一致。使用唯一编号可确保每个值在每一轮中都具有唯一编号。这确保了新领导者可以正确地选择最高接受值。
人为的场景：
一个五节点集群，节点 A 是领导者。网络失控。节点 B 认为它需要领导，因为它怀疑节点 A 由于丢失消息而死亡。节点 B 提议与 A 上次使用的号码相同。节点 A 和 B 实际上都已启动并尝试将不同的值传输到其他节点。断电，所有节点都变暗，一些但不是所有的消息都通过了，因为网络由于滚动断电而中断。
接下来电源恢复，但节点 A 和 E 仍然没有电。节点 B、C 和 D 可以形成法定人数。节点 C 提出一个新的高数并返回两个不同的值作为最高接受值。一个来自 A，另一个来自 B。它现在必须在它们之间做出选择。哪个值可以保证使集群达到正确的一致性？
想象一下，在幸存的群体中只有一个节点具有 A 值，但两个节点具有 B 值。所以假设我们猜测 B 的值，但这可能是错误的。死节点 A 和 E 可能有 As 值。节点 A 在电源故障之前碰巧看到了大多数对其值的响应，因为它的消息碰巧传递到另外两个节点。该价值是一笔付款，当它看到多数人回应时，它将钱从公司中汇出。然而，幸存的法定人数决定 A 的值从未发生过，并使集群与 B 的值保持一致。
修复：
您需要做的就是对每个节点进行唯一编号，并将节点唯一编号编码为选票编号的最低有效位。然后每个节点都使用它唯一的数字，并且可以轻松地生成一个新数字，该数字刚好高于集群中使用的最后一个最高数字。如果我们这样做，那么只有一个值将是任何一轮中接受的最高值。
如果最后一位领导者获得多数响应，任何拥有多数的新领导者将看到最后一位领导者使用的最高值。新的领导者不会与它将合作的最后一个领导者相矛盾。新领导人不需要知道已故领导人是否真的看到多数人的回应并据此采取行动。相反，它做出了保守的选择，并假设它可能有并采取适当的行动。
@ideawu 在 @simbo1905 的回答的评论线程中提到了一个额外的细节可能值得指出。我在下面给出的答案作为对该线程的评论可能更合适，但我没有 post 评论所需的 Stack Overflow 声誉。
在Paxos的经典描述中（例如Paxos Made Simple），确实要求选票numbers/ids对于每个提议者都是唯一的，即没有两个提议者可以在同一个选票中提出一个值，并且每个提案人不能为不同的提案重复使用选票编号。我的理解是，这只是为了保证给定选票最多只能提出一个值。
正如@simbo1905 指出的那样，确保提案中唯一选票编号的一种方法是 pre-allocating 每个提案人的一组不相交的选票 ID。不过，这并不是实现选票唯一性的唯一方法。如果接受者要求他们响应的准备（阶段 1a）消息的选票数严格大于他们最新承诺的选票数，那么这可以确保提议者永远不会在给定的问题上发生冲突选票号，即使不同的提议者试图对不同的提案使用相同的选票号。法定人数重叠 属性 确保了这一点，这是 Heidi Howard 的技术报告 Distributed Consensus Revised 中指出的事实，她在第 3.9 节中指出（使用术语“纪元”而不是“选票”） :
It has long been known that Classic Paxos does not require that epochs
are unique if acceptors require that a proposer’s epochs be strictly
greater than the last promised proposal. This means that at most one
proposer will reach phase two for a given epoch, since reaching phase
two requires a proposer to have already reached majority agreement for
phase one, thus guaranteeing uniqueness.
这支持@ideawu在上面评论中提出的想法。因此，如果我们确保接受者的这种“严格大于”行为，则不应从外部要求选票编号的唯一性，即协议将自动强制执行。
或者，如果我们允许接受者响应准备消息，其选票编号 大于或等于 他们最新承诺的选票，那么提案的选票编号的唯一性确实是, 不自动保证。据推测，这一事实是 Paxos 要求全球选票编号唯一性的最初动机。然而，我们可以通过稍微修改协议来解决这个问题。我们可以在每个接受者上添加一个额外的状态，用于存储它响应其最新承诺的投票的提议者的身份。如果它收到不同提议者对同一张选票的准备请求，它可以拒绝它。霍华德在参考论文部分给出了一个精确的例子。这也是采用的方法，例如在 Raft 共识协议中，它是使用每个服务器上维护的 votedFor 变量实现的。
您可以在 this TLA+ specification, which extends one of Lamport's Paxos specifications to add an explicit notion of proposers. Note that nothing in the specification ensures that different proposers choose ballot numbers from disjoint sets. Here is an error trace (counterexample) that is produced when using the "greater than or equal to" condition and model checking the safety property that only a single value is chosen. When using the "strictly greater than" 条件下看到上述概念的更正式的演示，模型检查器在 Proposer 集定义为 [=11= 的模型上终止且没有错误]（两个提议者）和 Nat（确定可能的选票集）被覆盖为 {1,2,3}。这绝不是安全证明，但它提供了一点额外的信心，即推理正确。
接受的答案实际上是不正确的 - 不要求轮数在节点之间是唯一的。唯一的要求是“每个提议对于给定的提议者都是唯一编号的”和“数字 n 必须大于该提议者之前任何准备消息中使用的任何数字。” - 这些引自维基百科 - 在精神上，这是相同的要求。
让我通过一个例子来解释为什么没有全局唯一性要求（并从最初接受的答案“It[Leader] 然后会得到相同数字的不同值的响应”来解决这个论点。）。
假设我们有一个有两个提议者和三个接受者（以及几个学习者）的系统：
- 两个提议者都向所有接受者发送了 PREPARE(1) - 相同的数字。
- 基于 paxos 规则，只有一个提议者将获得大部分 PROMISE 消息 - 这是基于接受者承诺的规则，如果 PREPARE 的数量远远大于接受者之前看到的任何其他消息。
- 现在我们处于一种状态，其中一个提议者有两个（或三个）N=1 的 PROMISES，而另一个提议者有一个（或零个）N = 1 的 PROMISE。
- 只有第一个提议者可以在获得多数时发出 ACCEPT(1, V)。另一个提议者没有大多数的 PROMISES，必须用更大的 N 重试。
- 在其他提议者重试后，它将使用比之前看到的任何其他提议都大的 N - 因此它将尝试使用 N=2
- 从现在开始，一切都以相同的方式工作——提议者准备，如果它的 N 获得了大多数 PROMISE，那么提议者发出 ACCEPT(N, VALUE_ACCORDING_TO_PROTOCOL)
对 paxos 的关键理解是无法发送两个 ACCEPT(N, V) 消息，其中相同的 N 将具有不同的 V，因此不存在两个提议者使用相同 N 的问题。
至于用一些唯一的 ID 启动每个节点 - 没关系；它会提高性能 - 这是一个大问题，我还没有看到正式的证据。
谁能告诉我为什么提案Id在Paxos中需要是唯一的？ 我认为这个 proposalId 需要唯一的原因是我们需要用它来拒绝旧提案并对最大投票进行排序。所以如果我们做第一阶段：acceptor只接受大于promisedId的proposal并且是增量的，还是可以保证一致性的。
我们假设proposer A向acceptor提出了一个提案(proposalId x, value y)，然后他得到了多数赞成的答复，另一个具有相同proposal id(x)的proposer B发出了proposal request，这个proposer B会被拒吧？最终，我们仍然可以达到一致性，对吗？
简短的回答是正确性的证明取决于每一轮每个节点的唯一数字。
一个直观的答案如下：
如果建议编号在集群中的节点之间不是唯一的，您可以让两个节点为相同的编号建议不同的值。在任意消息丢失的情况下，一些节点可能接受一个值而另一些节点接受另一个值。一个潜在的新领导者将向所有节点询问他们的最高接受值。然后它会得到相同数字的不同值的响应。然后它不能消除歧义并决定下一个要选择哪个值以使集群保持一致。使用唯一编号可确保每个值在每一轮中都具有唯一编号。这确保了新领导者可以正确地选择最高接受值。
人为的场景：
一个五节点集群，节点 A 是领导者。网络失控。节点 B 认为它需要领导，因为它怀疑节点 A 由于丢失消息而死亡。节点 B 提议与 A 上次使用的号码相同。节点 A 和 B 实际上都已启动并尝试将不同的值传输到其他节点。断电，所有节点都变暗，一些但不是所有的消息都通过了，因为网络由于滚动断电而中断。
接下来电源恢复，但节点 A 和 E 仍然没有电。节点 B、C 和 D 可以形成法定人数。节点 C 提出一个新的高数并返回两个不同的值作为最高接受值。一个来自 A，另一个来自 B。它现在必须在它们之间做出选择。哪个值可以保证使集群达到正确的一致性？
想象一下，在幸存的群体中只有一个节点具有 A 值，但两个节点具有 B 值。所以假设我们猜测 B 的值，但这可能是错误的。死节点 A 和 E 可能有 As 值。节点 A 在电源故障之前碰巧看到了大多数对其值的响应，因为它的消息碰巧传递到另外两个节点。该价值是一笔付款，当它看到多数人回应时，它将钱从公司中汇出。然而，幸存的法定人数决定 A 的值从未发生过，并使集群与 B 的值保持一致。
修复：
您需要做的就是对每个节点进行唯一编号，并将节点唯一编号编码为选票编号的最低有效位。然后每个节点都使用它唯一的数字，并且可以轻松地生成一个新数字，该数字刚好高于集群中使用的最后一个最高数字。如果我们这样做，那么只有一个值将是任何一轮中接受的最高值。
如果最后一位领导者获得多数响应，任何拥有多数的新领导者将看到最后一位领导者使用的最高值。新的领导者不会与它将合作的最后一个领导者相矛盾。新领导人不需要知道已故领导人是否真的看到多数人的回应并据此采取行动。相反，它做出了保守的选择，并假设它可能有并采取适当的行动。
@ideawu 在 @simbo1905 的回答的评论线程中提到了一个额外的细节可能值得指出。我在下面给出的答案作为对该线程的评论可能更合适，但我没有 post 评论所需的 Stack Overflow 声誉。
在Paxos的经典描述中（例如Paxos Made Simple），确实要求选票numbers/ids对于每个提议者都是唯一的，即没有两个提议者可以在同一个选票中提出一个值，并且每个提案人不能为不同的提案重复使用选票编号。我的理解是，这只是为了保证给定选票最多只能提出一个值。
正如@simbo1905 指出的那样，确保提案中唯一选票编号的一种方法是 pre-allocating 每个提案人的一组不相交的选票 ID。不过，这并不是实现选票唯一性的唯一方法。如果接受者要求他们响应的准备（阶段 1a）消息的选票数严格大于他们最新承诺的选票数，那么这可以确保提议者永远不会在给定的问题上发生冲突选票号，即使不同的提议者试图对不同的提案使用相同的选票号。法定人数重叠 属性 确保了这一点，这是 Heidi Howard 的技术报告 Distributed Consensus Revised 中指出的事实，她在第 3.9 节中指出（使用术语“纪元”而不是“选票”） :
It has long been known that Classic Paxos does not require that epochs are unique if acceptors require that a proposer’s epochs be strictly greater than the last promised proposal. This means that at most one proposer will reach phase two for a given epoch, since reaching phase two requires a proposer to have already reached majority agreement for phase one, thus guaranteeing uniqueness.
这支持@ideawu在上面评论中提出的想法。因此，如果我们确保接受者的这种“严格大于”行为，则不应从外部要求选票编号的唯一性，即协议将自动强制执行。
或者，如果我们允许接受者响应准备消息，其选票编号 大于或等于 他们最新承诺的选票，那么提案的选票编号的唯一性确实是, 不自动保证。据推测，这一事实是 Paxos 要求全球选票编号唯一性的最初动机。然而，我们可以通过稍微修改协议来解决这个问题。我们可以在每个接受者上添加一个额外的状态，用于存储它响应其最新承诺的投票的提议者的身份。如果它收到不同提议者对同一张选票的准备请求，它可以拒绝它。霍华德在参考论文部分给出了一个精确的例子。这也是采用的方法，例如在 Raft 共识协议中，它是使用每个服务器上维护的 votedFor 变量实现的。
您可以在 this TLA+ specification, which extends one of Lamport's Paxos specifications to add an explicit notion of proposers. Note that nothing in the specification ensures that different proposers choose ballot numbers from disjoint sets. Here is an error trace (counterexample) that is produced when using the "greater than or equal to" condition and model checking the safety property that only a single value is chosen. When using the "strictly greater than" 条件下看到上述概念的更正式的演示，模型检查器在 Proposer 集定义为 [=11= 的模型上终止且没有错误]（两个提议者）和 Nat（确定可能的选票集）被覆盖为 {1,2,3}。这绝不是安全证明，但它提供了一点额外的信心，即推理正确。
接受的答案实际上是不正确的 - 不要求轮数在节点之间是唯一的。唯一的要求是“每个提议对于给定的提议者都是唯一编号的”和“数字 n 必须大于该提议者之前任何准备消息中使用的任何数字。” - 这些引自维基百科 - 在精神上，这是相同的要求。
让我通过一个例子来解释为什么没有全局唯一性要求（并从最初接受的答案“It[Leader] 然后会得到相同数字的不同值的响应”来解决这个论点。）。
假设我们有一个有两个提议者和三个接受者（以及几个学习者）的系统：
- 两个提议者都向所有接受者发送了 PREPARE(1) - 相同的数字。
- 基于 paxos 规则，只有一个提议者将获得大部分 PROMISE 消息 - 这是基于接受者承诺的规则，如果 PREPARE 的数量远远大于接受者之前看到的任何其他消息。
- 现在我们处于一种状态，其中一个提议者有两个（或三个）N=1 的 PROMISES，而另一个提议者有一个（或零个）N = 1 的 PROMISE。
- 只有第一个提议者可以在获得多数时发出 ACCEPT(1, V)。另一个提议者没有大多数的 PROMISES，必须用更大的 N 重试。
- 在其他提议者重试后，它将使用比之前看到的任何其他提议都大的 N - 因此它将尝试使用 N=2
- 从现在开始，一切都以相同的方式工作——提议者准备，如果它的 N 获得了大多数 PROMISE，那么提议者发出 ACCEPT(N, VALUE_ACCORDING_TO_PROTOCOL)
对 paxos 的关键理解是无法发送两个 ACCEPT(N, V) 消息，其中相同的 N 将具有不同的 V，因此不存在两个提议者使用相同 N 的问题。
至于用一些唯一的 ID 启动每个节点 - 没关系；它会提高性能 - 这是一个大问题，我还没有看到正式的证据。