algorithm - 在这种情况下，Paxos 代理的正确行为是什么？

Question

我正在研究 Paxos，我对算法在这个人为设计的示例中的行为方式感到困惑。我希望下图能解释这个场景。

几点:

• 每个代理充当提议者/接受者/学习者
• 准备消息的格式为(instance, proposal_num)
• 建议消息的形式为 (instance, proposal_num, proposal_val)
• Server1 和 Server2 同时决定开始提案过程
• 一开始消息M1、M2和M3同时出现

这里看起来虽然协议(protocol)是“正确的”，即只选择了一个值 S2，但 Server1 和 Server2 认为它被选中是因为不同的提案编号。

Paxos 算法是否仅在 Decide(...) 消息发送给学习者时终止？我一定是误解了 Paxos Made Simple 但我认为选择是在提议者达到其 Propose(...) 消息的法定人数时做出的。

如果仅在 Decide(...) 消息发送给代理后才做出选择，Server2 是否应该终止发送 Decide(1, 5, S2) 当它恢复时因为它看到了稍后的 Prepare(1, 7)?

Answer 1

只需重新定义项(让我们也去掉 1，因为我们只检查一次 Paxos 迭代):

1) Propose(n) == propose(n)，来自当前身份为n的提议者的消息

2) AcceptPrepare(n,v) == ack(n,v)，消息发送给proposer n。如果此节点尚未接受任何值，则 v 为空，o.w. v 等于它接受的值

3) CreateDecide(n,v) == accept!(x,v)，要求节点接受来自身份为 x 的提议者的这个值。如果节点已经确认了一条 prepare(n) 消息，其中 n > x

，节点将拒绝该消息

一旦 prepare(n) 达到了法定人数——也就是说，大多数人已经确认了消息——然后身份为 n 的提议者发出一个命令 accept!(n,v)。如果一个 prepare(n+x), x > 0, 是由身份为 n+x 的提议者发出的——并且它被大多数人确认——在 ack(n,v) 消息和接受之间!( n,v)，那么多数人 promise 不接受时间戳 < n+x, x > 0 提出的值(也就是节点将拒绝接受!(n,v))

一旦大多数人收到他们没有 promise 忽略的 accept!(n,v) 消息，就会做出选择。

因此，当 server2 重新上线并发送 accept!(5,S2) 时，它将被忽略，因为 5 < 7。