Paxos的理解
Paxos understanding
我已阅读论文Paxos made simple。
经过深思熟虑，我得出这样的结论：
The Paxos protocol always guarantees the majority of servers accept the same value at the same turn of the proposal and so that finally, we can derive the consensus from the majority of servers.
例如table1表示有3台服务器(S1,S2,S3),N1,N2...表示proposal,proposals有很多空缺但是每一个提案，我们可以推导出大多数服务器共识。
N1: S1(A) & S2(A) & S3(A) => A
N2: S1(B) & S2(null) & S3(B) => B
N3: S1(null) & S2(C) & S3(C) => C
N4: S1(D) & S2(D) & S3(null) => D
所以我们得到共识，如图table 2。
我的理解对吗？
Table 1:
N1
N2
N3
N4
S1
A
B
D
S2
A
C
D
S3
A
B
C
Table 2:
N1
N2
N3
N4
A
B
C
D
从你所说的来看，我认为你正在了解是否通过查看越来越多的提案中接受的价值观来获得对一系列价值观的共识。按照这个，日志是从提案编号（（N1，A），（N2，B），（N3，C），（N4，B））中获得的。我认为是这种情况，因为你提到了提案序列中的差距。
如果是这样的话，我想可能会有些混乱。
在Paxos中，有两件事需要担心：
提案（或投票，尝试选择一个值）
日志值（由接受者商定然后由状态机执行的值）
对于日志，每个值都要有容错协议。只有当所有先前的值也都已执行时，才能执行一个值，因此如果您希望执行所有值，则日志中必须没有间隙。这是一个活性问题，与安全无关。您可以安全地了解日志中的所有值并将它们视为“已提交”。如果它是一台执行客户发出的命令的机器，你可以告诉客户他们对命令的请求将会发生，但你不能告诉他们执行他们的命令的结果，因为其他你不知道的命令会先于它执行.
日志使用基本的Paxos协议，提供对单值的容错协议。这是提交值的想法有用的地方。 Paxos Made Simple 中概述的基本 Paxos 协议只允许就单个值达成一致，并且它使用完全有序的提案序列（选票）来就该单个值达成一致。
这里最主要的是，在决定一个值位于日志中的单个索引时，可以有多个提议。
在此之后，Paxos 中接受者承诺或接受的提案序列可能存在间隙，但这没关系，并且是算法操作的一部分。 Paxos 算法确保如果在一个提案中就某个值达成一致，则所有编号较高的提案都将看到相同的提议值并因此达成一致。请注意，这与问题的表 1 和表 2 中的示例不同。在那个例子中，如果大多数服务器（接受者）已经接受了提议 N1 中的 A，那么所有后来的提议也将接受值 N1。
这种就多个提议达成一致的能力对于容错来说是必要的，特别是对于活性而言。想象一下，如果一个提议 N1 被大多数接受者接受，然后除了一个接受者之外的所有接受者都崩溃了，然后才能发出任何接受 N1 的通知。已经商定了一个值，但没有人知道。现在，为了从中恢复过来，另一个提议者应该发布一个更高编号的提议。我们称此提案为 Nh。
提出建议有两个阶段：承诺和接受。在第一阶段，提议者必须获得大多数（或法定人数）接受者对提议 Nh 的承诺。这样做的目的是确定一个值是否（可能）在编号较低的提案中达成一致。在这种情况下，我们将了解到一个接受者已经接受了编号较低的提议 Nl 中的一个值。 （其他响应的接受者将报告他们没有接受任何东西。）尽管只有一个接受者报告他们接受了 Nl 中的一个值，提议者必须（出于协议安全原因）假设它可能被选中。然后，在第二阶段，提议者将向接受者发出提议 Nh 的接受请求，并将包括较早提议 Nl 的值。如果至少大多数（法定人数）接受者接受了这一点，那么该提案就会被选中，并且一切顺利，学习者将学习该值到日志中为单个索引提交的值。否则，发布决定日志索引值的提案的过程将再次继续。
最后，要提出的最后一点是，也没有要求提案必须获得多数接受，这一点很重要，因为在提案发布时可能没有大多数接受者是无缺陷的。为了激发这一点，请考虑在提案期间是否有适当的或太多的接受者失败。
想象一下，如果在 Paxos 算法的一个实例中有接受者，其中一个接受提议 Na 中的一个值。然后，在 Na 被多数人接受之前，Na 的提议者失败了，并且在网络上传输的任何消息都丢失了。在这种情况下，提议者需要能够提出新的提议并看到所选择的值。在这种情况下，另一个提议者将开始一个编号更高的提议 Nb。它将像以前一样经历承诺阶段，并在与两个没有接受任何东西的接受者交谈后确定不可能选择任何价值。现在 Nb 的提议者可以提出任何价值，并看到它被大多数人接受并达成一致。在这里提出任何价值都是安全的，因为如果 Na 的提议者重新上线，他们的价值将不会被大多数人接受，因为大多数接受者已经承诺并接受了更高编号的提议。
迈克尔 :)
我已阅读论文Paxos made simple。
经过深思熟虑，我得出这样的结论：
The Paxos protocol always guarantees the majority of servers accept the same value at the same turn of the proposal and so that finally, we can derive the consensus from the majority of servers.
例如table1表示有3台服务器(S1,S2,S3),N1,N2...表示proposal,proposals有很多空缺但是每一个提案，我们可以推导出大多数服务器共识。
N1: S1(A) & S2(A) & S3(A) => A
N2: S1(B) & S2(null) & S3(B) => B
N3: S1(null) & S2(C) & S3(C) => C
N4: S1(D) & S2(D) & S3(null) => D
所以我们得到共识，如图table 2。
我的理解对吗？
Table 1:
| N1 | N2 | N3 | N4 | |
|---|---|---|---|---|
| S1 | A | B | D | |
| S2 | A | C | D | |
| S3 | A | B | C |
Table 2:
| N1 | N2 | N3 | N4 |
|---|---|---|---|
| A | B | C | D |
从你所说的来看，我认为你正在了解是否通过查看越来越多的提案中接受的价值观来获得对一系列价值观的共识。按照这个，日志是从提案编号（（N1，A），（N2，B），（N3，C），（N4，B））中获得的。我认为是这种情况，因为你提到了提案序列中的差距。
如果是这样的话，我想可能会有些混乱。
在Paxos中，有两件事需要担心：
提案（或投票，尝试选择一个值）
日志值（由接受者商定然后由状态机执行的值）
对于日志，每个值都要有容错协议。只有当所有先前的值也都已执行时，才能执行一个值，因此如果您希望执行所有值，则日志中必须没有间隙。这是一个活性问题，与安全无关。您可以安全地了解日志中的所有值并将它们视为“已提交”。如果它是一台执行客户发出的命令的机器，你可以告诉客户他们对命令的请求将会发生，但你不能告诉他们执行他们的命令的结果，因为其他你不知道的命令会先于它执行.
日志使用基本的Paxos协议，提供对单值的容错协议。这是提交值的想法有用的地方。 Paxos Made Simple 中概述的基本 Paxos 协议只允许就单个值达成一致，并且它使用完全有序的提案序列（选票）来就该单个值达成一致。
这里最主要的是，在决定一个值位于日志中的单个索引时，可以有多个提议。
在此之后，Paxos 中接受者承诺或接受的提案序列可能存在间隙，但这没关系，并且是算法操作的一部分。 Paxos 算法确保如果在一个提案中就某个值达成一致，则所有编号较高的提案都将看到相同的提议值并因此达成一致。请注意，这与问题的表 1 和表 2 中的示例不同。在那个例子中，如果大多数服务器（接受者）已经接受了提议 N1 中的 A，那么所有后来的提议也将接受值 N1。
这种就多个提议达成一致的能力对于容错来说是必要的，特别是对于活性而言。想象一下，如果一个提议 N1 被大多数接受者接受，然后除了一个接受者之外的所有接受者都崩溃了，然后才能发出任何接受 N1 的通知。已经商定了一个值，但没有人知道。现在，为了从中恢复过来，另一个提议者应该发布一个更高编号的提议。我们称此提案为 Nh。
提出建议有两个阶段：承诺和接受。在第一阶段，提议者必须获得大多数（或法定人数）接受者对提议 Nh 的承诺。这样做的目的是确定一个值是否（可能）在编号较低的提案中达成一致。在这种情况下，我们将了解到一个接受者已经接受了编号较低的提议 Nl 中的一个值。 （其他响应的接受者将报告他们没有接受任何东西。）尽管只有一个接受者报告他们接受了 Nl 中的一个值，提议者必须（出于协议安全原因）假设它可能被选中。然后，在第二阶段，提议者将向接受者发出提议 Nh 的接受请求，并将包括较早提议 Nl 的值。如果至少大多数（法定人数）接受者接受了这一点，那么该提案就会被选中，并且一切顺利，学习者将学习该值到日志中为单个索引提交的值。否则，发布决定日志索引值的提案的过程将再次继续。
最后，要提出的最后一点是，也没有要求提案必须获得多数接受，这一点很重要，因为在提案发布时可能没有大多数接受者是无缺陷的。为了激发这一点，请考虑在提案期间是否有适当的或太多的接受者失败。
想象一下，如果在 Paxos 算法的一个实例中有接受者，其中一个接受提议 Na 中的一个值。然后，在 Na 被多数人接受之前，Na 的提议者失败了，并且在网络上传输的任何消息都丢失了。在这种情况下，提议者需要能够提出新的提议并看到所选择的值。在这种情况下，另一个提议者将开始一个编号更高的提议 Nb。它将像以前一样经历承诺阶段，并在与两个没有接受任何东西的接受者交谈后确定不可能选择任何价值。现在 Nb 的提议者可以提出任何价值，并看到它被大多数人接受并达成一致。在这里提出任何价值都是安全的，因为如果 Na 的提议者重新上线，他们的价值将不会被大多数人接受，因为大多数接受者已经承诺并接受了更高编号的提议。
迈克尔 :)