Lamport 的 Paxos 中的矛盾使简单的论文
Contradiction in Lamport's Paxos made simple paper
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 的状态：proposal n:v 是 X 接受的最大编号的提案，其中 n 是提案编号，v 是提案的值， m 是 X 响应过的最大准备请求数。
- P1 发送 'prepare 1' 给 AB
- AB都响应P1承诺不接受任何编号小于1的请求。现在状态是：A(-:-,1) B(-:-,1) C(-:-, -)
- P1收到响应，然后卡住，运行很慢
- P2发送'prepare 100'给AB
- 两个AB都响应P2承诺不接受任何编号小于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从来没有承诺过什么。状态为：A(-:-,100) B(100:b,100) C(1:a,-)。选择的proposal被abandon，Paxos失败
我错过了什么吗？谢谢
您在第 7 步中遗漏了某些内容。当 C 处理 accept 100:b 时，它会将其状态设置为 C(100:b,100)。 通过接受一个值，节点也承诺不接受更早的值。
更新。我整个月都在想这个问题，因为我知道上面的答案并不完全正确。
此外，我查看了几个专有和开源的 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 和几个实现所做的那样。然后你 运行 陷入这个灾难性的错误。
死灵肿块。即使两个变体的较弱部分，也没有不一致之处。我们看题中例子中的第9步：
"The state is A(-:-,100) B(100:b,100) C(1:a,-). The chosen proposal is abandon, Paxos fails"
但是，此时我们只有一个不确定的值，因为没有多数人接受的值（我们最终必须选择 'b'，因为 b 在步骤 6 中被多数人接受。）
为了继续协议，我们需要新的选票，最终将接受一些更新的选票。该选票的值必须为 'b'、
证明：C 将对任何准备请求做出响应（100，'b'），因为它接受的最高编号的选票是（100，'b'），即使它 last 接受了投票 (1, 'a')。 B 也会响应 (100, 'b')。因此，除了 'b'.
以外的任何值都不可能获得多数票
Lamport 的语言是接受者将以 "The proposal with the highest number less than n that it has accepted, if any"
回应
接受的答案将 "highest numbered" 与 "latest accepted," 混淆，因为该示例表明接受者可以按递减编号顺序接受值。为了完全符合 Lamport 的协议，C 有必要记住它响应了 (100, 'b') 即使它做出的 "latest" 接受是 (1, 'a' ).
（话虽这么说，如果许多实现没有正确执行此操作并因此容易受到此问题的影响，我不会感到惊讶。）
将接受请求广播给所有个接受者肯定没有问题。您不需要将其限制为仅回复原始准备请求的那些。您在 Lamport 博士的文章中发现了罕见的错误措辞。
但是，您的反例中存在错误。首先，符号定义如下：
X(n:v,m) to denote the status of acceptor X: proposal n:v is the largest numbered proposal accepted by X
但是在第 7 步中节点 C 具有状态 C(100:b,-)，然后在第 9 步中它更改为状态 C(1:a,-)。这不是一个有效的转换：在接受 1:a 之后它应该保持在 C(100:b,-) 状态，因为 100:b 仍然是 C 接受的 最大编号的提案。
请注意，它在 100:b 之后接受 1:a 是完全没问题的，主要是因为网络是异步的，所以所有消息都可以延迟或重新排序而不会破坏任何东西，所以世界其他地方可以无论如何先告诉哪个提案被接受了。
C 无法接受提案，因为它还没有经过第 1 阶段。IOW 要让接受者接受一个值，接受者必须经历协议的两个阶段。
if by accepting a value the node is also promising to not accept earlier values, the algorithm is correct, but in the paper Lamport didn't mention this requirement, right?
不需要以上条件。假设接受者承诺的最高选票是 X。假设传入的接受消息的选票编号为 Y。如果 Y < X，我们知道 Y 必须被拒绝。如果 Y > X，这意味着接受者没有收到 Y 的准备请求。这意味着，我们收到了无效的 paxos 消息。在这种情况下，应该丢弃 Y 的接受消息。
唯一的例外是当 Y == 0 时。在这种情况下，发出选票编号为 0 的准备没有意义，因为选票编号低于 0 是无效的。因此，ballot 0 可以跳过第 1 阶段，提议者可以直接进入第 2 阶段。在这种情况下，即当 Y == 0 时，接受者只有在没有接受值的情况下才能接受该值。这与您在上面提出的建议相同，但仅在 Paxos 的优化版本中需要，其中 Y == 0 可以跳过第 1 阶段。
IOWs，接受者唯一接受值的时间是 Y == X。唯一的例外是 Y == 0。在这种情况下，接受者只有在没有接受值时才能接受值价值。
我同意 Ben Braun 的大部分回答。
C可以接受(1,a)，不会改变选择的值。假设 C 接受了 (1, a)，我们从学习者的角度来看一下接受历史。
(100, b) 被 B 和 C 接受
(1, a) 被 C
接受
选择 (100, b) 是因为它被大多数接受者接受。
此时，如果学习者获得完整的接受历史记录，则协议不需要继续，除非学习者失败或发送给学习者的消息丢失。这是我不同意 Ben Braun 的回答的地方。
但接受者应保留已接受的编号最高的提案，以备新提案发布时使用。
更新：我也同意 Dave Turner 的观点，实际上没有理由接受编号较低的提案。提案编号就像逻辑时钟，忽略旧消息是安全的。
论文中确实有歧义，这就是为什么应该使用 TLA+ 规范，而不是论文来实现算法。
当接受一个值时，接受者必须再次更新它的状态，即最近承诺的选票。从 Paxos TLA+ specification 中可以清楚地看出这一点，查看接受器更新 maxBal 的阶段 2b，并与执行相同操作的阶段 1b 进行比较。
Leslie Lamport 处理了这个问题 in his recent lecture，他解释说这样做是为了让接受者集不同于承诺投票的节点集。
Paxos Made Simple 中模棱两可的句子是“这不需要是响应初始请求的同一组接受器”。
它的实际含义是“嗨，让我在这里给你一个提示。本文描述的算法可以优化以消除准备阶段和接受阶段的要求阶段必须有相同的接受者集合”。请注意，Paxos Made Simple 中描述的算法与 The Part-Time Parliament 中描述的算法略有不同。
然而，有些人误解了这句话：“本文中描述的算法不需要准备阶段和接受阶段必须有相同的接受者集合。
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 的状态：proposal n:v 是 X 接受的最大编号的提案，其中 n 是提案编号，v 是提案的值， m 是 X 响应过的最大准备请求数。
- P1 发送 'prepare 1' 给 AB
- AB都响应P1承诺不接受任何编号小于1的请求。现在状态是：A(-:-,1) B(-:-,1) C(-:-, -)
- P1收到响应，然后卡住，运行很慢
- P2发送'prepare 100'给AB
- 两个AB都响应P2承诺不接受任何编号小于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从来没有承诺过什么。状态为：A(-:-,100) B(100:b,100) C(1:a,-)。选择的proposal被abandon，Paxos失败
我错过了什么吗？谢谢
您在第 7 步中遗漏了某些内容。当 C 处理 accept 100:b 时，它会将其状态设置为 C(100:b,100)。 通过接受一个值，节点也承诺不接受更早的值。
更新。我整个月都在想这个问题，因为我知道上面的答案并不完全正确。
此外，我查看了几个专有和开源的 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 和几个实现所做的那样。然后你 运行 陷入这个灾难性的错误。
死灵肿块。即使两个变体的较弱部分，也没有不一致之处。我们看题中例子中的第9步：
"The state is A(-:-,100) B(100:b,100) C(1:a,-). The chosen proposal is abandon, Paxos fails"
但是，此时我们只有一个不确定的值，因为没有多数人接受的值（我们最终必须选择 'b'，因为 b 在步骤 6 中被多数人接受。）
为了继续协议，我们需要新的选票，最终将接受一些更新的选票。该选票的值必须为 'b'、
证明：C 将对任何准备请求做出响应（100，'b'），因为它接受的最高编号的选票是（100，'b'），即使它 last 接受了投票 (1, 'a')。 B 也会响应 (100, 'b')。因此，除了 'b'.
以外的任何值都不可能获得多数票Lamport 的语言是接受者将以 "The proposal with the highest number less than n that it has accepted, if any"
回应接受的答案将 "highest numbered" 与 "latest accepted," 混淆，因为该示例表明接受者可以按递减编号顺序接受值。为了完全符合 Lamport 的协议，C 有必要记住它响应了 (100, 'b') 即使它做出的 "latest" 接受是 (1, 'a' ).
（话虽这么说，如果许多实现没有正确执行此操作并因此容易受到此问题的影响，我不会感到惊讶。）
将接受请求广播给所有个接受者肯定没有问题。您不需要将其限制为仅回复原始准备请求的那些。您在 Lamport 博士的文章中发现了罕见的错误措辞。
但是，您的反例中存在错误。首先，符号定义如下：
X(n:v,m)to denote the status of acceptor X: proposaln:vis the largest numbered proposal accepted by X
但是在第 7 步中节点 C 具有状态 C(100:b,-)，然后在第 9 步中它更改为状态 C(1:a,-)。这不是一个有效的转换：在接受 1:a 之后它应该保持在 C(100:b,-) 状态，因为 100:b 仍然是 C 接受的 最大编号的提案。
请注意，它在 100:b 之后接受 1:a 是完全没问题的，主要是因为网络是异步的，所以所有消息都可以延迟或重新排序而不会破坏任何东西，所以世界其他地方可以无论如何先告诉哪个提案被接受了。
C 无法接受提案，因为它还没有经过第 1 阶段。IOW 要让接受者接受一个值，接受者必须经历协议的两个阶段。
if by accepting a value the node is also promising to not accept earlier values, the algorithm is correct, but in the paper Lamport didn't mention this requirement, right?
不需要以上条件。假设接受者承诺的最高选票是 X。假设传入的接受消息的选票编号为 Y。如果 Y < X，我们知道 Y 必须被拒绝。如果 Y > X，这意味着接受者没有收到 Y 的准备请求。这意味着，我们收到了无效的 paxos 消息。在这种情况下，应该丢弃 Y 的接受消息。
唯一的例外是当 Y == 0 时。在这种情况下，发出选票编号为 0 的准备没有意义，因为选票编号低于 0 是无效的。因此，ballot 0 可以跳过第 1 阶段，提议者可以直接进入第 2 阶段。在这种情况下，即当 Y == 0 时，接受者只有在没有接受值的情况下才能接受该值。这与您在上面提出的建议相同，但仅在 Paxos 的优化版本中需要，其中 Y == 0 可以跳过第 1 阶段。
IOWs，接受者唯一接受值的时间是 Y == X。唯一的例外是 Y == 0。在这种情况下，接受者只有在没有接受值时才能接受值价值。
我同意 Ben Braun 的大部分回答。
C可以接受(1,a)，不会改变选择的值。假设 C 接受了 (1, a)，我们从学习者的角度来看一下接受历史。
(100, b) 被 B 和 C 接受
(1, a) 被 C
(100, b) 是因为它被大多数接受者接受。
此时，如果学习者获得完整的接受历史记录，则协议不需要继续，除非学习者失败或发送给学习者的消息丢失。这是我不同意 Ben Braun 的回答的地方。
但接受者应保留已接受的编号最高的提案，以备新提案发布时使用。
更新：我也同意 Dave Turner 的观点，实际上没有理由接受编号较低的提案。提案编号就像逻辑时钟，忽略旧消息是安全的。
论文中确实有歧义，这就是为什么应该使用 TLA+ 规范，而不是论文来实现算法。
当接受一个值时，接受者必须再次更新它的状态，即最近承诺的选票。从 Paxos TLA+ specification 中可以清楚地看出这一点，查看接受器更新 maxBal 的阶段 2b，并与执行相同操作的阶段 1b 进行比较。
Leslie Lamport 处理了这个问题 in his recent lecture，他解释说这样做是为了让接受者集不同于承诺投票的节点集。
Paxos Made Simple 中模棱两可的句子是“这不需要是响应初始请求的同一组接受器”。
它的实际含义是“嗨，让我在这里给你一个提示。本文描述的算法可以优化以消除准备阶段和接受阶段的要求阶段必须有相同的接受者集合”。请注意，Paxos Made Simple 中描述的算法与 The Part-Time Parliament 中描述的算法略有不同。
然而，有些人误解了这句话：“本文中描述的算法不需要准备阶段和接受阶段必须有相同的接受者集合。