27

阶段 2. (a) 如果提议者从大多数接受者那里收到对其准备请求（编号为 n）的响应，那么它会向这些接受者中的每一个发送一个接受请求，以获取编号为 n 且值为 v 的提议，其中 v 是响应中编号最高的提案的值，或者如果响应报告没有提案，则为任何值。

如论文所述，

提议者通过向一组接受者发送提议被接受的请求来发布提议。（这不必是响应初始请求的同一组接受者。）“

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

如果提议者从大多数接受者那里收到对其准备请求（编号为 n）的响应，则它会向任意一组多数接受者发送一个接受请求，以获取编号为 n 且值为 v 的提议，其中 v 是响应中编号最高的提案，或者如果响应没有报告提案，则为任何值。

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

  1. P1 向 AB 发送“准备 1”
  2. 两个 AB 都以不接受任何编号小于 1 的请求的承诺响应 P1。现在状态为：A(-:-,1) B(-:-,1) C(-:-,-)
  3. P1 收到响应，然后卡住并运行得很慢
  4. P2 向 AB 发送“准备 100”
  5. 两个 AB 都以不接受任何编号小于 100 的请求的承诺响应 P2。现在状态是：A(-:-,100) B(-:-,100) C(-:-,-)
  6. P2 收到响应，选择一个值 b 并将“接受 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 从未承诺过任何事情。状态为：A(-:-,100) B(100:b,100) C(1:a,-)。选择的提案被放弃，Paxos 失败。

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

4

8 回答 8

17

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

更新。我整个月都在考虑这个问题，因为我知道上面的答案不是绝对正确的。

更重要的是，我查看了几个专有和开源的 paxos 实现，它们都有 OP 提交的错误！

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

如果提议者从大多数接受者那里收到对其准备请求（编号为 n）的响应，那么它会向这些接受者中的每一个发送一个接受请求，以获取编号为 n 且值为 v 的提议，其中 v 是最高-响应中的编号提案，或者如果响应报告没有提案，则为任何值。（强调我的）

换句话说，提议者只能将Accept消息发送给它Promises从该选票号码收到的接受者。

那么，这在兰波特的论文中是否自相矛盾？现在，我说是的。

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

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

于 2015-04-28T20:14:52.590 回答
6

将接受请求广播给所有接受者当然没有问题。您无需将其限制为仅回复原始准备请求的那些。您在 Lamport 博士的文章中发现了一个罕见的用词不当的案例。

但是，您的反例中有一个错误。首先，符号定义如下：

X(n:v,m)表示接受者 X 的状态：提案n:v是 X 接受的编号最大的提案

但是在第 7 步中节点 C 具有 state C(100:b,-)，然后在第 9 步中它变为 state C(1:a,-)。这不是一个有效的转换：接受后1:a它应该保持状态C(100:b,-)，因为100:b它仍然是C 接受的最大编号的提案。

请注意，它接受1:aafter完全没问题100:b，本质上是因为网络是异步的，因此所有消息都可以延迟或重新排序而不会破坏任何内容，因此世界其他地方无论如何都无法判断哪个提案首先被接受。

于 2016-12-13T08:18:28.520 回答
2

死灵弹。即使两个变体的较弱部分，也没有不一致。让我们看一下问题示例中的第 9 步：

“状态是 A(-:-,100) B(100:b,100) C(1:a,-)。选择的提案是放弃，Paxos 失败”

然而，此时我们只有一个不确定的值，因为没有多数接受的值（我们最终必须选择“b”，因为 b 在步骤 6 中被多数接受。）

为了继续该协议，我们需要新的选票，最终会接受一些新的选票。该选票必须具有值'b'，

证明：C 将对任何准备请求做出响应（100，'b'），因为它接受的最高编号的选票是（100，'b'），即使它最后一次接受选票（1，'a'）。B 也将响应 (100, 'b')。因此，不再可能获得除“b”以外的任何值的多数票。

Lamport 的语言是，acceptor 将回应“它已接受的最大数量小于 n 的提案，如果有的话”

接受的答案将“最高编号”与“最新接受”混淆了，因为该示例显示接受器可以接受以递减编号顺序的值。为了完全符合 Lamport 的协议，C 有必要记住它响应了 (100, 'b')，即使它所做的“最新”接受是 (1, 'a')。

（话虽这么说，如果许多实现没有正确地做到这一点，我不会感到惊讶，因此容易受到这个问题的影响。）

于 2016-04-21T03:03:51.080 回答
2

论文中确实存在歧义，这就是为什么应该使用 TLA+ 规范而不是论文来实现算法。

当接受一个值时，接受者必须再次更新其状态，即最近承诺的选票。从Paxos TLA+ 规范中可以清楚地看到这一点，查看接受器更新 maxBal 的阶段 2b，并与执行相同操作的阶段 1b 进行比较。

Leslie Lamport在他最近的演讲中处理了这个问题，他解释说这样做是为了让接受者集与承诺投票的节点集不同。

于 2020-04-07T00:22:00.600 回答
0

如果通过接受一个值，节点也承诺不接受较早的值，那么算法是正确的，但是在 Lamport 的论文中没有提到这个要求，对吧？

上述条件不是必需的。假设接受者承诺的最高选票是 X。假设传入的接受消息的选票编号为 Y。如果 Y < X，我们知道 Y 必须被拒绝。如果 Y > X，这意味着接受者没有收到对 Y 的准备请求。这意味着，我们收到了无效的 paxos 消息。在这种情况下，应删除 Y 的接受消息。

唯一的例外是当 Y == 0 时。在这种情况下，发出带有 0 选票的准备是没有意义的，因为低于 0 的选票是无效的。因此，第 0 轮投票可以跳过第 1 阶段，提议者可以直接进入第 2 阶段。在这种情况下，即当 Y == 0 时，只有当它没有接受值时，接受者才能接受该值。这与您在上面提出的建议相同，但仅在 Paxos 的优化版本中需要，其中 Y == 0 可以跳过阶段 1。

IOWs，接受者唯一接受一个值的时候是 Y == X。唯一的例外是 Y == 0 时。在这种情况下，接受者只有在它没有接受一个值的情况下才能接受这个值。

于 2017-03-13T08:00:36.033 回答
0

我同意 Ben Braun 的大部分回答。

C 可以接受 (1,a)，它不会更改所选值。假设 C 接受 (1, a)，我们从学习者的角度来看接受历史。

(100, b) 被 B 和 C 接受
(1, a) 被 C 接受

选择 (100, b) 是因为它被大多数接受者接受。

此时，如果学习者获得完整的接受历史，则协议不需要继续，除非学习者失败或给学习者的消息丢失。这就是我不同意 Ben Braun 的回答的地方。

但接受者应保留已接受的最高数量的提案，以防发布新的提案。

更新：我也同意戴夫·特纳的观点，实际上没有理由接受编号较低的提案。提案编号就像逻辑时钟，忽略旧消息是安全的。

于 2017-09-15T20:12:56.483 回答
0

C 不能接受该提案，因为它还没有经过第 1 阶段。要让一个 vale 被接受者接受的 IOW，接受者必须通过协议的两个阶段。

于 2017-01-24T14:28:23.540 回答
0

Paxos Made Simple 中的模棱两可的句子是“这不必是响应初始请求的同一组接受者”。

它的实际含义是“你好，我在这里给你一个提示。可以优化本文描述的算法，以消除prepare阶段和accept阶段必须具有相同的acceptors集合的要求”。请注意，Paxos Made Simple 中描述的算法与 The Part-Time Parliament 中描述的算法略有不同。

然而，也有人将那句话误解为：“本文描述的算法并不要求prepare阶段和accept阶段必须有相同的acceptors集合”。

于 2021-11-18T02:02:00.457 回答