2

我正在阅读Paxos 变得简单的论文，但被困在 P2 b的证明部分。

规则 P2 b的内容：

如果选择值为 v 的提案，则任何提案者发布的每个编号较高的提案都具有值 v。

这是 Leslie Lamport 的证明部分：

为了发现如何满足 P2 b，让我们考虑如何证明它成立。我们假设某个编号为 m 且值为 v 的提案被选中，并表明任何编号为 n > m 的提案也具有值 v。我们将通过对 n 使用归纳来简化证明，因此我们可以证明编号为 n 的提案在附加假设下具有值 v ，即每个提案都以 m 中的数字发布。. (n - 1) 的值为 v ，其中 i 。. j 表示从 i 到 j 的数字集。要选择编号为 m 的提案，必须有一些由大多数接受者组成的集合 C，使得 C 中的每个接受者都接受它。将此与归纳假设相结合，选择 m 的假设意味着：

C 中的每个接受者都接受了一个编号为 m ..(n - 1) 的提案，并且任何接受者接受的每个编号为 m ..(n - 1) 的提案都具有值 v

所以归纳过程是：

  • 基本情况：选择了值为v的提案m
  • 归纳步骤：任何编号为m ..(n-1) 的提案都具有值v

为什么它意味着：

C 中的每个接受者都接受了一个编号为 m ..(n − 1) 的提案

我只是无法弥合差距，为什么C中的每个接受者都需要接受编号为m..(n-1)的提案？

P1保证接受者必须接受收到的第一个提案， P2 a保证只有具有所选值的编号较高的提案才能被接受者接受，但我只是不明白隐含声明的重点。

4

3 回答 3

4

这是整个正确性证明的图解说明。

  1. 假设已经学习了两个提案的值，编号为 P 和 Q，其中 P < Q：

第1步

  1. 此外，假设 P 的学习值为 X，Q 的学习值为 Y，其中 X ≠ Y：

第2步

  1. 这意味着为 P 和 Q 提出的值分别是 X 和 Y。每个提案最多只能有一个值：

第 3 步

  1. 现在考虑 P 和 Q 之间提出的所有其他建议：

第4步

  1. 令 R 为第一个值为 ≠X 的提案。希望很清楚 P < R ≤ Q：

第 5 步

  1. 换句话说，编号 ≥ P 且 < R 的提案都具有值 X：

第 6 步

  1. 让 S 成为在 P 发送阶段 2b 消息的节点集。（在您的问题中，S 称为 C，但我已经绘制了这些图片，所以我坚持使用 S）。因为大多数重叠，这组节点必须与在 R 发送阶段 1b 消息的节点组重叠：

第 7 步

  1. 考虑重叠的节点之一。它必须先在 P 发送它的阶段 2b 消息，然后再在 R 发送它的阶段 1b 消息，因为这就是阶段 1b 消息的用途。

第 8 步

  1. 它可能也为编号 >P 的提案发送了阶段 2b 消息，但不能为编号为 ≥R 的提案发送消息，因为这是阶段 1b 消息的规则。但是所有 ≥ P 且 < R 的提案都具有 X 值，因此它发送了阶段 2b 消息的编号最高的提案肯定具有 X 值：

第 9 步

  1. 现在考虑为提案 R 发送阶段 1b 消息的所有其他节点。其中一些可能没有接受以前的提案；有些人可能接受了编号 < P 的提案，但他们都接受了编号 < R 的提案，并且其中至少有一个接受了 ≥ P 的提案，因此其中任何一个接受的编号最高的提案的值为 X：

第 10 步

这里存在矛盾：根据阶段 2a 消息的规则，这意味着在 R 提出的值毕竟必须是 X。

这在你看来可能与 Paxos Made Simple 论文中的证明大不相同，因为它似乎是矛盾的，并且没有明确的归纳。事实上，第 5 步中“假设有一个反例，然后考虑最小的反例”的技术实际上只是变相的归纳，我的经验是，这是一种更易于呈现的方式。如果你喜欢这样的事情，将这一步转化为明确的归纳是一个有趣的练习。

您的问题中提到的集合 C 是发送阶段 2b 消息以在 P 处接受提案的接受者集合。这不一定与在 R 发送阶段 1b 消息的集合相同，但这些集合确实相交，即的重要因素。

于 2017-07-02T11:35:24.147 回答
2

考虑到那篇论文中的语言，很容易被细节挂断。我建议尝试理解 Paxos。它更加冗长，但它在没有设置符号或上标的情况下介绍了算法的实际使用方式和原因以及周围的问题。

于 2017-06-04T04:52:48.533 回答
0

C 中的每个接受者都接受了一个编号为 m ..(n − 1) 的提案，因为选择了值为 v 的提案 m，所以必须有一些由大多数接受者组成的集合 C，使得 C 中的每个接受者都接受了它，并且 m ..(n − 1) 包含 m

于 2019-04-18T01:11:07.220 回答