Lamport的Paxos中的矛盾使得简单的纸张

作者: 1号
发布时间: 2024-01-23 05:31:00 (6月前)
转自：

7 条回复

0#
回复此人
氷寒 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 你错过了第7步中的内容。当C进程时 <code> accept 100:b </code> 它将其状态设置为 <code> C(100:b,100) </code> 。的 通过接受一个值，节点也承诺不接受早期的值。 </强> <HR /> 的 更新。 </强> 我整个月都在考虑这个，因为我知道上面的答案并不完全正确。 我通过几个专有的和开源的paxos实现了解了它们的 所有人都有OP提交的错误 </强> ！ 所以这是正确答案，的 完全从中看 Paxos变得简单 </强> ： <BLOCKQUOTE> 如果提议者从大多数接受者收到对其准备请求（编号为n）的响应，则它会向每个接收者发送一个接受请求。 的 那些接受者 </强> 对于编号为n且值为v的提案，其中v是响应中编号最高的提案的值，如果响应未报告提议，则为任何值。（强调我的） </BLOCKQUOTE> 换一种说法，的 提议者只能发送 <code> Accept </code> 收到的接收者的消息 <code> Promises </code> 从 </强> 该选票号码。 那么，这是Lamport论文中的一个矛盾吗？现在，我说是的。 <HR /> 如果你看看Lamport的paxos样张，他会对待一个 <code> accept </code> 作为一个 <code> promise </code> 就像我原来的答案所说的那样。但是没有指出这一点 Paxos变得简单 。事实上，Lamport似乎非常痛苦地指出了这一点 <code> accept </code> 不是 <code> promise </code> 。 问题是当你将两种变体的较弱部分结合起来时;正如OP所做的那样，有几个实现。然后你遇到了这个灾难性的bug。 </DIV>

编辑
1#
回复此人
AsuRa | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> C不能接受该提案，因为它没有通过第1阶段。对于接受者接受谷值而言，接受者必须通过协议的两个阶段。 </DIV>

编辑
2#
回复此人
12345 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 我同意Ben Braun的答案的大部分内容。 C接受（1，a）是好的，它不会改变所选择的值。假设C接受（1，a），我们从学习者的角度来看待接受历史。 （100，b）被B和C接受 （1，a）被C接受 选择（100，b），因为它被大多数接受者接受。 此时，如果学习者获得完整的接受历史记录，则协议不需要继续，除非学习者失败或者学习者的消息丢失。这是我不同意Ben Braun的回答的地方。 但是，如果发布新提案，接受方应保持接受的提案的编号最高。 更新：我同意Dave Turner的说法，实际上没有理由接受编号较低的提案。提案号与逻辑时钟类似，忽略旧消息是安全的。 </DIV>

编辑
3#
回复此人
哦哦了 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <BLOCKQUOTE> <BLOCKQUOTE> 如果通过接受一个值节点也承诺不接受早期值，算法是正确的，但在论文中Lamport没有提到这个要求，对吧？ </BLOCKQUOTE> </BLOCKQUOTE> 不需要上述条件。假设接受者承诺的最高投票是X.假设传入的接受消息具有选票号Y.如果Y＆lt; 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.在这种情况下，只有在接受者没有接受值时，接受者才能接受该值。 </DIV>

编辑
4#
回复此人
爱我真好 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> NECROBUMP。即使两种变体中较弱的部分，也没有不一致性。让我们看看问题中示例中的第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的语言是，接受者会回答“如果有的话，最接近n的提案，如果有的话” 接受的答案将“最高编号”与“最新接受”混淆，因为该示例表明接受者可以接受递减编号顺序的值。为了完全符合Lamport的协议，C必须记住它响应（100，'b'），即使它所做的“最新”接受是（1，'a'）。 （话虽如此，如果许多实现没有正确执行此操作，我也不会感到惊讶，因此容易受到此问题的影响。） </DIV>

编辑
5#
回复此人
如果 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 拉姆达 您的逻辑是合理的，但仅仅是因为您对Paxos算法的描述存在缺陷。这应该是预期的，因为Paxos在数学上已被证明是正确的，你指出的问题是经典的争用案例之一。我对古典Paxos文献的一个批评是，在我看来，这些论文并没有说明这个算法的基本正确性要求是提案数量这一事实。的 不能被不同的同行重复使用 </强> 。每次提出提案时的 必须 </强> 是唯一的或算法的正确性保证被抛出窗外。如果允许重复使用，则会指出您指出的确切情况。如果你读 非常 仔细地说，你会发现经典论文中提到了这一点，但它并没有在应有的程度附近受到压力。应该使用粗体，下划线和恼人的文本。 为了说明这一点，在示例中将提议ID（也称为整数）的定义更改为（'poposal number'，'proposer unique-id'）的元组，而不仅仅是整数，其中排序定义为 <code> a>b if a.proposal_number > b.proposal_number or a.proposer_unique_id > b.proposer_unique_id </code> 。你会看到你描述的问题消失了，算法完全正确。你的例子 精确 场景描述了“非案例”部分 <a href="https://understandingpaxos.wordpress.com/" rel="nofollow"> 了解Paxos </A> 。我可能会补充一个部分，我纯粹是因为我发现自己对你所指出的情景非常困惑。很容易错过古典文献中的提案ID唯一性要求。 迈克尔在回答Paxos问题时通常是正确的，但在这种情况下，我认为他犯了一个小错误，再次归结于这一个主要的误解 - 不会发生 - 更好地强调 - 在原作中-papers-问题。提议者不需要仅向那些使用Promise消息响应的对等体发送Accept消息。将Accept消息发送给所有对等体时，算法是正确的，无论它们是否响应Promise消息，的 只要提议ID保证对每个对等方都是唯一的 </强> 。尽管“Paxos Made Simple”论文的文字非常混乱...... Paxos真的很简单。的 但 </强> 它确实依赖于对前期要求的充分理解，而Unique Proposal Ids绝对是其中之一。 Rakis </DIV>

编辑

登录后才能参与评论