在Paxos中，接受器可以接受其他值吗？ [英] In Paxos, can an Acceptor accept a different value after it has already accepted one?

问题描述

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

接收：Prepare（N）

回复：Promise（N，空）

接收：接受！（N，V1）

回复：已接受（N，V1）

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

reply：？

在这种情况下，根据协议，受体的反应应该是什么？

我相信这种情况可能会在Multi-Paxos中发生，如果第二次接受，则接受还是接受（N + 1，V2）？提议者上线并且认为他是（并且一直是）领导者，因此他无需准备就发送他的接受。或者，如果他的准备只是没有到达接受者。如果这种情况可能不会发生，您能解释一下原因吗？

解决方案

我不同意其他两个答案。

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




2. 接受消息违反了Paxos算法。 接受者应该接受所有值，除非它答应不接受它。（允许忽略，但不建议；这是因为允许丢弃的消息。）




3. 对此也有一个很好的解决方案。问题出在领导者的回合数字上（问题中为N + 1）。

以下是一些假设： / p>

• 您有一种方案，使得所有节点上的回合ID都是不相交的（无论如何Paxos都需要）。


• 您可以确定每个Paxos实例的领导者是哪个节点（Multi-Paxos必需）。 Leader可以从一个Paxos实例更改为另一个。
  
  放在一边： 兼职议会 建议，这是由领导者赢得了先前的Paxos实例（第3.1节）而完成的，并指出，只要她还活着或者是最富有的（第3.3.1节）。我有一个明确的ELECT_NEW_LEADER：< node>


• 领导者仅在每个实例的 initial 回合中跳过准备阶段；并在随后的回合中使用完整的基本Paxos。

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

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

当领导者的接受阶段尚未达到时到达任何节点，斯图尔特将不会在任何Promise中取回任何价值，并且可以像常规Basic-Paxos一样继续进行。

接受阶段已经到达一个节点，Stewart将获得一个promise中的值，就像在Basic-Paxos中一样，它用于继续执行该算法。

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

接受器或斯图尔特上没有特殊逻辑。以及对Leader的最小特殊逻辑（即选择一个非常低的INITIAL_ROUND_ID）。

---

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

• 接收：Prepare（N）


• 回复：Promise（N，null）


• 接收：接受！（N，V1）


• 回复：Accepted（N，V1）


• 接收：接受！（ N-1 ，V2）


• 回复： Nack（N，V1 ）

但就目前情况而言，他的回答打破了Paxos算法；

• 接收：Prepare（N）


• 回复：Promise（N， null）


• 接收：接受！（N，V1）


• 回复：接受（N，V1）


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


• 回复：接受！（N + 1，V2）

In Multi-Paxos algorithm, consider this message flow from the viewpoint of an acceptor:

receive: Prepare(N)

reply: Promise(N, null)

receive: Accept!(N, V1)

reply: Accepted(N, V1)

receive: Accept!(N+1, V2)

reply: ?

What should the acceptor's reaction be in this case, according to the protocol? Should it reply with Accepted(N+1, V2), or should it ignore the second Accept!?

I believe this case may happen in Multi-Paxos when a second proposer comes online and believes he is (and always was) leader, therefore he sends his Accept without Preparing. Or if his Prepare simply did not reach the acceptor. If this case may not happen, can you explain why?

解决方案

I disagree with both other answers.

1. Multi-Paxos does not say that the Leader is the only proposer; this would cause the system to have a single point of failure. Even during network partitions the system may not be able to progress. Multi-Paxos is an optimization allowing a single node (the Leader) to skip some prepare phases. Other nodes, thinking the leader is dead, may attempt to continue the instance on her behalf, but must still use the full Basic-Paxos protocol.

2. Nacking the accept message violates the Paxos algorithm. An acceptor should accept all values unless it has promised to not accept it. (Ignoring is allowed but not recommended; it's just because dropped messages are allowed.)

3. There is also an elegant solution to this. The problem is with the Leader's round number (N+1 in the question).

Here are some assumptions:

• You have a scheme such that round ids are disjoint across all nodes (required by Paxos anyway).
• You have a way of determining which node is the Leader per Paxos instance (required by Multi-Paxos). The Leader is able to change from one Paxos instance to the next.
  Aside: The Part-time Parliament suggests this is done by the Leader winning a prior Paxos instance (Section 3.1) and points out she can stay Leader as long as she's alive or the richest (Section 3.3.1). I have an explicit ELECT_NEW_LEADER:<node> value that is proposed via Paxos.
• The Leader only skips the Prepare phase on the initial round per instance; and uses full Basic Paxos on subsequent rounds.

With these assumptions, solution is very simple. The Leader merely picks a really low round id for it's initial Accept phase. This id (which I'll call it INITIAL_ROUND_ID) can be anything as long as it is lower than all the nodes' round ids. Depending on your id-choosing scheme, either -1, 0, or Integer.MIN_VALUE will work.

It works because another node (I'll call him the Stewart) has to go through the full Paxos protocol to propose anything and his round id is always greater than INITIAL_ROUND_ID. There are two cases to consider: whether or not the Leader's Accept messages reached any of the nodes the Stewart's Prepare message did.

When the Leader's Accept phase has not reaches any nodes, the Stewart will get back no value in any Promise, and can proceed just like in regular Basic-Paxos.

And, when the Leader's Accept phase has reached a node, the Stewart will get back a value in a promise, which it uses to continue the algorithm, just like in Basic-Paxos.

In either case, because the Stewart's round id is greater than INITIAL_ROUND_ID, any slow Accept messages a node receives from the Leader will always result in a Nack.

There is no special logic on either the Acceptor or the Stewart. And minimal special logic on the Leader (Viz. pick a really low INITIAL_ROUND_ID).

---

Notice, if we change the OP's question by one character then the OP's self answer is correct: Nack.

• receive: Prepare(N)
• reply: Promise(N, null)
• receive: Accept!(N, V1)
• reply: Accepted(N, V1)
• receive: Accept!(N-1, V2)
• reply: Nack(N, V1)

But as it stands, his answer breaks the Paxos Algorithm; it should be Accept!

• receive: Prepare(N)
• reply: Promise(N, null)
• receive: Accept!(N, V1)
• reply: Accepted(N, V1)
• receive: Accept!(N+1, V2)
• reply: Accept!(N+1, V2)

这篇关于在Paxos中，接受器可以接受其他值吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！