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

Question

我正在研究Paxos,我对算法在这个人为的例子中应该如何表现感到困惑.我希望下面的图解释了这个场景.

几点:

• 每个代理都充当提议者/接受者/学习者
• 准备消息有形式 (instance, proposal_num)
• 建议消息有形式 (instance, proposal_num, proposal_val)
• Server1和Server2都决定同时启动提案流程
• 在开始时,消息M1,M2和M3同时发生

在这里似乎虽然协议是"正确的",即只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) == suggest(n)，来自当前身份为n的提议者的消息

2) AcceptPrepare(n,v) == ack(n,v)，消息发送给提议者n。如果该节点尚未接受任何值，则 v 为空，其中 v 等于它已接受的值

3）CreateDecide（n，v）==accept！（x，v），要求节点接受来自身份为x的提议者的该值。如果节点已确认准备（n）消息（其中 n > x），则节点将拒绝该消息

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

一旦大多数人收到他们未承诺忽略的接受！（n，v）消息，就会做出选择。

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