在Paxos中，提案编号需要唯一吗

Question

如果用相同的ProposalId发布两个提案，会发生什么？如果它们具有相同的价值，就不会产生任何问题。但不同的价值观呢？我可以想出一个场景，在失败时它会危及生命，但它会给协议的安全带来任何问题吗？

Answer 1

这是一个不错的主意，因为它可以缓解实用系统的一个恼人的设计要求：设计一个方案来确保提出者有不同的，但不断增加的整数。

不幸的是，它不起作用。

让我们将PaxosPrime定义为Paxos的变体，其中允许不同的提议者具有相同的整数。我们通过矛盾证明了PaxosPrime不是一个一致性算法。

证明草图：假设PaxosPrime是一致性算法。让我们考虑一下每个受体有不同的值，但对于同一轮(w.l.o.g，我们将选择3(。每个人也将在3点做出承诺。然后，我们让一对提议者在系统中进行交互。

A1    | A2    | A3
v   p | v   p | v   p  
------+-------+------
x@3 3 | y@3 3 | z@3 3

1. P1准备第4轮(即阶段1.A(，并接收所有三个值x@3、y@3和z@3。Paxos中没有关于平局打破的规定，所以我们让它选择x
2. P2也准备第4轮并且分别从A2和A3接收y@3和z@3。我们会让它选择y
3. P1发送对x@4的接受(即阶段2.A(，接受方都处理它。此时，所有接受方的值都为v@4，并承诺为4系统对x的取值有共识
4. P2发送对轮y@4的接受，并且接受方A2和A3成功地处理它。大多数接受方现在具有值y@4系统对值y有共识

这是从接受者的角度来看的跟踪：

A1    | A2    | A3
v   p | v   p | v   p  
------+-------+------
x@3 3 | y@3 3 | z@3 3  # Start
x@3 4 | y@3 4 | z@3 4  # Process P1's propose command
x@3 4 | x@3 4 | x@3 4  # Process P1's accept command
x@3 4 | y@3 4 | y@3 4  # Process P2's accept command

系统首先对值x达成共识，然后对值y达成共识。这是共识定义上的矛盾；因此PaxosPrime不是一致性算法。

É

---

Answer 2

Synod算法在技术上不要求提案编号在所有流程中都是唯一的。单调增加的需求只是一种优化。从技术上讲，我们可以选择一个随机的提案编号，并且仍然有一个正确的算法。

该算法从提议者向所有接受者发送准备(提议编号(开始。只有在大多数接受方还没有看到提案编号高达或高于该编号的情况下，它才能在提案中使用该提案编号，并成功地发回每个提案编号只能发生一次的承诺。在此阶段之后，如果提议者能够继续，那么该提议编号实际上是唯一的。因此，该算法已经强制要求提案中实际使用的提案编号的唯一性。