distributed-computing - 在 Paxos 中，Acceptor 可以在接受一个值之后再接受一个不同的值吗？

Question

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

接收:准备(N)

回复: promise (N，空)

接收:接受!(N，V1)

回复:接受(N，V1)

接收:接受!(N+1，V2)

回复: ？

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

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

Answer 1

我不同意其他两个答案。

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

取消接受消息违反了 Paxos 算法。 接受者应该接受所有值，除非它 promise 不接受它。 (允许但不推荐忽略；这只是因为允许丢弃的消息。)

对此也有一个优雅的解决方案。问题在于领导者的回合数(问题中的 N+1)。

以下是一些假设:

您有一个方案，使得所有节点的轮 id 不相交(Paxos 无论如何都需要)。

您可以确定哪个节点是每个 Paxos 实例的领导者(Multi-Paxos 需要)。 Leader 能够从一个 Paxos 实例更改为下一个。
旁白:The Part-time Parliament建议这是由领导者赢得先前的 Paxos 实例来完成的(第 3.1 节)，并指出只要她还活着或最富有，她就可以继续担任领导者(第 3.3.1 节)。我有一个通过 Paxos 提出的显式 ELECT_NEW_LEADER: 值。

Leader 只在每个实例的第一轮跳过 Prepare 阶段；并在随后的回合中使用完整的 Basic Paxos。

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

它之所以有效，是因为另一个节点(我称他为 Stewart)必须通过完整的 Paxos 协议(protocol)才能提出任何建议，并且 他的回合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。

Acceptor 或 Stewart 都没有特殊的逻辑。以及领导者上的最小特殊逻辑(即选择一个非常低的 INITIAL_ROUND_ID)。

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

接收:准备(N)

回复:Promise(N, null)

接收:接受!(N，V1)

回复:接受(N，V1)

接收:接受!( N-1 ，V2)

回复:纳克(N, V1)

但就目前而言，他的回答打破了 Paxos 算法；应该是接受!

接收:准备(N)

回复:Promise(N, null)

接收:接受!(N，V1)

回复:接受(N，V1)

接收:接受!( N+1 ，V2)

回复:接受!(N+1，V2)