在Paxos中,Acceptor在接受了它之后是否可以接受不同的值？

Question

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

接收:准备(N)

回复:承诺(N,null)

接收:接受!(N,V1)

回复:已接受(N,V1)

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

回复:？

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

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

Answer 1

我不同意其他两个答案.

Multi-Paxos并没有说领导者是唯一的提议者; 这会导致系统出现单点故障.即使在网络分区期间,系统也可能无法进行.Multi-Paxos是一种优化,允许单个节点(领导者)跳过一些准备阶段.认为领导者已经死亡的其他节点可能会尝试代表她继续实例,但仍必须使用完整的Basic-Paxos协议.
拒绝接受消息违反了Paxos算法.除非承诺不接受,否则接受方应接受所有价值.(忽略是允许的但不推荐;这只是因为允许丢弃的消息.)
这也是一个优雅的解决方案.问题在于领导者的整数(问题中的N + 1).

以下是一些假设:

你有一个方案,圆形ID在所有节点上都是不相交的(无论如何都需要Paxos).
您可以通过某种方式确定哪个节点是每个Paxos实例的Leader(Multi-Paxos所需).领导者能够从一个Paxos实例更改为下一个Paxos实例.
旁白:兼职议会建议这是由领导者赢得之前的Paxos实例(第3.1节)并指出只要她还活着或者最富有(第3.3.1节),她就可以保持领袖.我有一个明确的ELECT_NEW_LEADER:<node>值,通过Paxos提出.
该负责人只跳过在准备阶段的初期每个实例轮; 并在后续轮次中使用完整的基本Paxos.

有了这些假设,解决方案就非常简单.领导者只是为它的初始接受阶段选择了一个非常低的圆形id.只要它低于所有节点的圆形ID,这个id(我称之为INITIAL_ROUND_ID)就可以是任何东西.根据您的id选择方案,-1,0或Integer.MIN_VALUE将起作用.

它的工作原理是因为另一个节点(我称之为斯图尔特)必须通过完整的Paxos协议来提出任何建议,并且他的圆形ID总是大于INITIAL_ROUND_ID.有两种情况需要考虑:领导者的接受消息是否到达斯图尔特准备消息所做的任何节点.

当Leader的Accept阶段没有到达任何节点时,Stewart将在任何Promise中都没有返回任何值,并且可以像普通的Basic-Pax一样继续进行.

而且,当领导的接受阶段已经达到了一个节点,斯图尔特会回来的承诺,它用来继续算法,就像在基本-Paxos的一个值.

在任何一种情况下,因为Stewart的round id大于INITIAL_ROUND_ID,所以节点从Leader接收的任何慢的Accept消息将始终导致Nack.

Acceptor或Stewart都没有特殊的逻辑.Leader上的最小特殊逻辑(即选择一个非常低的INITIAL_ROUND_ID).

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

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