在Paxos中，Acceptor在已经接受了一个值之后还可以接受不同的值吗？

Question

在 Multi-Paxos 算法中，从接受者的角度考虑这个消息流：

接收：Prepare(N)

回复：Promise(N, null)

接收：Accept!(N, V1)

回复：Accepted(N, V1)

接收：接受！（N+1，V2）

回复：？

根据协议，在这种情况下，接受者应该有什么反应？它应该回复 Accepted(N+1, V2)，还是应该忽略第二个 Accept!？

我相信这种情况可能会发生在 Multi-Paxos 中，当第二个提议者上线并相信他是（并且一直是）领导者时，因此他在没有准备的情况下发送了 Accept。或者如果他的准备根本没有到达接受者。如果这种情况可能不会发生，您能解释一下原因吗？

Answer 1

我不同意其他两个答案。

1. Multi-Paxos 并没有说 Leader 是唯一的提议者； 这会导致系统出现单点故障。即使在网络分区期间，系统也可能无法继续运行。 Multi-Paxos 是一种优化，允许单个节点（Leader）跳过一些准备阶段。其他节点认为领导者已死亡，可能会尝试代表她继续实例，但仍必须使用完整的 Basic-Paxos 协议。

2. 对接受消息进行 Nack 违反了 Paxos 算法。 接受者应该接受所有值，除非它承诺不接受它。（允许忽略，但不推荐；这只是因为允许丢弃消息。）

3. 那里也是一个优雅的解决方案。问题在于领导者的轮数（问题中的 N+1）。

以下是一些假设：

• 您有一个方案，使得所有节点上的轮 ID 都是不相交的（无论如何 Paxos 都需要）。
• 您有办法确定哪个节点是每个 Paxos 实例的 Leader（Multi-Paxos 需要）。 Leader 能够从一个 Paxos 实例更改为下一个实例。
  旁白：兼职议会 表明这是通过领导者赢得先前的 Paxos 实例来完成的（第 3.1 节），并指出只要她还活着或最富有，她就可以保持领导者身份（第 3.3.1 节）。我有一个明确的 ELECT_NEW_LEADER:;通过 Paxos 提出的值。
• 领导者仅在每个实例的初始轮中跳过准备阶段；并在后续回合中使用完整的 Basic Paxos。

有了这些假设，解决方案就非常简单了。领导者只是为它的初始接受阶段选择一个非常低的回合 ID。这个 id（我将其称为 INITIAL_ROUND_ID）可以是任何值，只要它低于所有节点的回合 id 即可。根据您的 id 选择方案，-1、0 或 Integer.MIN_VALUE 都可以。

它之所以有效，是因为另一个节点（我称他为 Stewart）必须通过完整的 Paxos 协议才能提出任何建议，并且他的回合 id 始终大于 INITIAL_ROUND_ID。有两种情况需要考虑：Leader 的 Accept 消息是否到达 Stewart 的 Prepare 消息到达的任何节点。

当 Leader 的 Accept 阶段尚未到达任何节点时，Stewart 将不会在任何 Promise 中返回任何值，并且可以像常规 Basic-Paxos 一样继续进行。

而且，当 Leader 的 Accept 阶段已经到达一个节点时，Stewart 将在 Promise 中返回一个值，它使用该值继续算法，就像在 Basic-Paxos 中一样。

在任何一种情况下，由于 Stewart 的回合 ID 大于 INITIAL_ROUND_ID，因此节点从 Leader 接收到的任何缓慢的 Accept 消息都将始终导致 Nack。

接受者或斯图尔特都没有特殊的逻辑。 Leader 上的特殊逻辑最少（即选择一个非常低的 INITIAL_ROUND_ID）。

---

请注意，如果我们将 OP 的问题更改一个字符，则 OP 的自我回答是正确的：Nack。

• 接收：准备(N)
• 回复：Promise(N，null)
• 接收：接受！(N，V1)
• 回复：接受(N，V1)
• 接收：接受！(N-1，V2)
• 回复： Nack(N, V1)

但就目前情况而言，他的答案打破了 Paxos 算法；应该是接受！

• 接收：准备(N)
• 回复：Promise(N，null)
• 接收：接受！(N，V1)
• 回复：接受(N，V1)
• 接收：接受！(N+1，V2)
• 回复：接受！(N+1，V2)

Answer 2

Multi-Paxos 的正确性取决于领导者（即提议者）在连续的 Paxos 实例之间不发生变化的要求。来自兼职议会 第 3.1 节（多法令议会议定书）：

从逻辑上讲，议会协议 [又名 Multi-Paxos] 使用了
每个法令编号的完整 Synod 协议 [又名 Paxos] 的单独实例。然而，
为所有这些实例选择了一位总统[又名提议者/领导者]，并且他执行了第一个
协议的两个步骤只需一次。
_{[添加的重点是我的。]}

因此，Multi-Paxos 做出这样的假设：您描述的情况 - 当第二个提议者上线并相信他是（而且一直是）领导者——永远不会发生。如果发生这种情况，那么就不应该使用 Multi-Paxos。对于第二种可能性——当第二个提议者的 Prepare 没有到达接受者时——第二个提议者已经发出了一个 Accept! 意味着它之前已经发出了由一定数量的接受者承诺的Prepare。由于接受者已经在第N轮中向第一个提议者做出承诺，因此第二个提议者的Prepare必须在第N轮之前发送出去。因此，最终的Accept!(N+1,V2) 的计数器必须小于 N。

编辑：还应该注意的是，这个版本的协议对于拜占庭并不稳健失败：

[Paxon 议会协议] 不容忍任意、恶意的失败，也不保证有限时间响应。
_{—兼职议会，第 4.1 节}

Answer 3

也许一个更简单的答案是观察这种情况，即当Prepare(N+1)命令被不包括相关接受者的大多数人接受时。

详细说明：一旦领导者知道某些大多数人已承诺（N+1），它就会向所有接受者发送Accept（N+1，x），即使一些其他大多数接受者回复接受(N+1)，则达成共识。

这种情况并不罕见。

Answer 4

（回答我自己的问题。）

我目前的理解是，我不应该接受 N+1 中的值（即根本不回答或发送 NACK），从而迫使领导者可能开始另一轮准备（如果大多数人尚未达成共识）。当我收到Prepare(N+2)后，我将回复Promise(N+2, V1)并照常继续。