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 曾经响应过的最大准备请求的数量。
- P1 向 AB 发送“准备 1”
- AB 都响应 P1 promise 不接受任何编号小于 1 的请求。现在状态是:A(-:-,1) B(-:-,1) C(-:-,-)
- P1 收到响应,然后卡住并运行得很慢
- P2 向 AB 发送“准备 100”
- AB 都响应 P2 promise 不接受任何编号小于 100 的请求。现在状态是:A(-:-,100) B(-:-,100) C(-:-,-)
- P2 收到响应,选择一个值 b 并发送 'accept 100:b' 给 BC
- BC接收并接受accept请求,状态为:A(-:-,100) B(100:b,100) C(100:b,-)。请注意,提案 100:b 已被选中。
- P1 恢复,选择值 a 并发送 'accept 1:a' 给 BC
- B 不接受,但 C 接受了,因为 C 从来没有 promise 过任何事情。状态为:A(-:-,100) B(100:b,100) C(1:a,-)。选择的提议被放弃,Paxos 失败。
我在这里错过了什么吗?谢谢。
最佳答案
您在第 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 和几个实现所做的那样。然后你会遇到这个灾难性的错误。
关于algorithm - Lamport 的 Paxos 中的矛盾使简单的论文,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29880949/