algorithm - Lamport 的 Paxos 中的矛盾使简单的论文

Question

Phase 2. (a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.

如论文中所述，

A proposer issues a proposal by sending, to some set of acceptors, a request that the proposal be accepted. (This need not be the same set of acceptors that responded to the initial requests.)"

但据我了解，如果我们将阶段 2.(a) 更改为:

If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to an arbitrary set of majority acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.

算法会失败，下面是一个例子。考虑总共有 3 个受体 ABC。我们将使用 X(n:v,m) 来表示接受者 X 的状态:提案 n:v 是 X 接受的编号最大的提案，其中 n 是提案编号，v 是提案的值(value)，m 是X 曾经响应过的最大准备请求的数量。

1. P1 向 AB 发送“准备 1”
2. AB 都响应 P1 promise 不接受任何编号小于 1 的请求。现在状态是:A(-:-,1) B(-:-,1) C(-:-,-)
3. P1 收到响应，然后卡住并运行得很慢
4. P2 向 AB 发送“准备 100”
5. AB 都响应 P2 promise 不接受任何编号小于 100 的请求。现在状态是:A(-:-,100) B(-:-,100) C(-:-,-)
6. P2 收到响应，选择一个值 b 并发送 'accept 100:b' 给 BC
7. BC接收并接受accept请求，状态为:A(-:-,100) B(100:b,100) C(100:b,-)。请注意，提案 100:b 已被选中。
8. P1 恢复，选择值 a 并发送 'accept 1:a' 给 BC
9. B 不接受，但 C 接受了，因为 C 从来没有 promise 过任何事情。状态为:A(-:-,100) B(100:b,100) C(1:a,-)。选择的提议被放弃，Paxos 失败。

我在这里错过了什么吗？谢谢。

Answer 1

您在第 7 步中遗漏了某些内容。当 C 处理 accept 100:b 时，它会将其状态设置为 C(100:b,100)。 通过接受一个值，节点也 promise 不接受之前的值。

---

更新。我整个月都在思考这个问题，因为我知道上面的答案并不完全正确。

此外，我查看了几个专有和开源的 paxos 实现，它们都有 OP 提交的错误!

所以这是正确的答案，完全从Paxos Made Simple来看:

If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals. (emphasis mine)

换句话说，提议者只能向接受者发送Accept消息，它已经从收到了该选票编号的Promises。

那么，这与 Lamport 的论文矛盾吗？现在，我说是。

---

如果您查看 Lamport 的 paxos 证明，他将 accept 视为 promise，正如我最初的回答所暗示的那样。但这在 Paxos Made Simple 中并未指出。事实上，Lamport 似乎煞费苦心地指出 accept 不是 promise。

问题是当您将两种变体的较弱部分组合在一起时；正如 OP 和几个实现所做的那样。然后你会遇到这个灾难性的错误。