Paxos vs Raft 领导选举
paxos vs raft for leader election
看了paxos和raft paper，有以下困惑：
paxos paper只描述了单条log entry的共识，相当于raft算法的leader选举部分。在raft的leader选举中，paxos的方法相对于简单的随机超时方法有什么优势？
原始的 Paxos 论文没有使用稳定的领导者是一个常见的误解。在第 6 页的 Paxos Made Simple 标题为“实施”的部分中，Lamport 写道：
The algorithm chooses a leader, which plays the roles of the
distinguished proposer and the distinguished learner.
这是使用准备和承诺的阶段 1 消息传递简单实现的。
然后在第 9 页和第 10 页的“实现状态机”部分下，我们有：
In normal operation, a single server is elected to be the leader,
which acts as the distinguished proposer (the only one that tries to
issue proposals) in all instances of the consensus algorithm.
这里是在最一般的意义上使用术语 'state machine'，涵盖明显的情况，例如我们复制应用于存储的操作日志的键值存储或数据库服务器。
人们对此感到困惑，因为 Lamport 证明 Paxos 的方式是现在的教学方式。 Lamport 通过将其分解为可以推理的数学模型，证明了 class 应用程序 Paxos 的正确性。他在原始论文 The Part-Time Parliament:
中称此为“Single-Decree 会议”
Paxon religious leaders asked mathematicians to formulate a protocol
for choosing the Synod’s decree. The protocol’s requirements and
assumptions were essentially the same as those of the later Parliament
except that instead of containing a sequence of decrees, a ledger
would have at most one decree. The resulting Synod protocol is
described here; the Parliamentary protocol is described in Section 3.
如果您发现该陈述令人困惑，请不要担心这是一个糟糕的笑话；字面上地。用我自己的话翻译为：
“In order to prove the correctness of the consensus algorithm for
choosing a stream of commands we can first demonstrate the correctness
of a mathematical model which chooses a single command. The
mathematical model for selecting a single command can then be extended
to the practical algorithm for selecting a stream of commands (Section
3) as long as the invariants of the single command mathematical model
are not violated.” – simbo1905
为了证明我的解释是正确的，我们可以看一下标题为“Multi-Decree 议会”的第 3 节，其中说：
Instead of passing just one decree, the Paxon Parliament had to pass a
series of numbered decrees. As in the Synod protocol, a president was
elected. Anyone who wanted a decree passed would inform the president,
who would assign a number to the decree and attempt to pass it.
Logically, the parliamentary protocol used a separate instance of the
complete Synod protocol for each decree number. However, a single
president was selected for all these instances, and he performed the
first two steps of the protocol just once.
为了解决这一问题，最初的“Part-Time Parliment”论文介绍了 Paxos，因为它的 multi-degree 算法使计算机科学家很感兴趣；议会协议。那篇文章和澄清文件“Paxos Made Simple”都将 Paxos 定义为具有杰出的领导者，为命令流分配序列号。此外，尊贵的领导者只有在担任领导职务时才发送“准备”消息；在那之后，在 steady-state 中，尊贵的领导者仅流式传输“接受”消息。他还在论文的其他地方说要折叠角色并让所有服务器 运行 算法的所有三个角色。
你问“在 raft 的领导者选举中，Paxos 的方法相对于简单的随机超时方法有什么优势？”我不确定你指的是什么方法？使用 Paxos，您可以随机化超时并发出 Prepare 消息。 Paxos Made Simple 论文指出，只要您遵循 Paxos 协议以“确保安全”，您就可以自由使用超时或其他更快的机制：
The famous result of Fischer, Lynch, and Pat- terson 1 implies that
a reliable algorithm for electing a proposer must use either
randomness or real time—for example, by using timeouts. However,
safety is ensured regardless of the success or failure of the
election.
随机超时很容易编码，也很容易理解。然而，在最坏的情况下，它们可能会导致恢复的长时间延迟。你不喜欢你可以使用你自己的领导人选举机制。例如 this one.
看完问题和@simbo1905 的回答后，我觉得我必须投入我的 2 美分，因为我认为问题没有得到回答。
What's the advantage of paxos's approach over the simple random timeout approach in raft's leader election?
tl;dr：Paxos 是最优的，但 Raft 具有更强的实用 活性保证。
有关更多信息，请继续阅读。
正如 Lamport 在 Paxos Made Simple 第 3 节中所述，
It can be shown that phase 2 of the Paxos consensus algorithm has the minimum possible cost of any algorithm for reaching agreement in the presence of faults [2]. Hence, the Paxos algorithm is essentially optimal.
所以Paxos以一种在没有错误的情况下效率最高的方式来实现共识。
另一方面在同一节中他还指出
If multiple servers think they are leaders, then they can all propose values in the same instance of the consensus algorithm, which could prevent any value from being chosen. However, safety is preserved—two different servers will never disagree on the value chosen as the ith state machine command. Election of a single leader is needed only to ensure progress.
这意味着 实际上 Paxos 可以看到违反其活性保证的行为。
Raft 是 Paxos
8-O
...更具体地说，它是具有不同命名的多法令版本。
看了paxos和raft paper，有以下困惑： paxos paper只描述了单条log entry的共识，相当于raft算法的leader选举部分。在raft的leader选举中，paxos的方法相对于简单的随机超时方法有什么优势？
原始的 Paxos 论文没有使用稳定的领导者是一个常见的误解。在第 6 页的 Paxos Made Simple 标题为“实施”的部分中，Lamport 写道：
The algorithm chooses a leader, which plays the roles of the distinguished proposer and the distinguished learner.
这是使用准备和承诺的阶段 1 消息传递简单实现的。
然后在第 9 页和第 10 页的“实现状态机”部分下，我们有：
In normal operation, a single server is elected to be the leader, which acts as the distinguished proposer (the only one that tries to issue proposals) in all instances of the consensus algorithm.
这里是在最一般的意义上使用术语 'state machine'，涵盖明显的情况，例如我们复制应用于存储的操作日志的键值存储或数据库服务器。
人们对此感到困惑，因为 Lamport 证明 Paxos 的方式是现在的教学方式。 Lamport 通过将其分解为可以推理的数学模型，证明了 class 应用程序 Paxos 的正确性。他在原始论文 The Part-Time Parliament:
中称此为“Single-Decree 会议”Paxon religious leaders asked mathematicians to formulate a protocol for choosing the Synod’s decree. The protocol’s requirements and assumptions were essentially the same as those of the later Parliament except that instead of containing a sequence of decrees, a ledger would have at most one decree. The resulting Synod protocol is described here; the Parliamentary protocol is described in Section 3.
如果您发现该陈述令人困惑，请不要担心这是一个糟糕的笑话；字面上地。用我自己的话翻译为：
“In order to prove the correctness of the consensus algorithm for choosing a stream of commands we can first demonstrate the correctness of a mathematical model which chooses a single command. The mathematical model for selecting a single command can then be extended to the practical algorithm for selecting a stream of commands (Section 3) as long as the invariants of the single command mathematical model are not violated.” – simbo1905
为了证明我的解释是正确的，我们可以看一下标题为“Multi-Decree 议会”的第 3 节，其中说：
Instead of passing just one decree, the Paxon Parliament had to pass a series of numbered decrees. As in the Synod protocol, a president was elected. Anyone who wanted a decree passed would inform the president, who would assign a number to the decree and attempt to pass it. Logically, the parliamentary protocol used a separate instance of the complete Synod protocol for each decree number. However, a single president was selected for all these instances, and he performed the first two steps of the protocol just once.
为了解决这一问题，最初的“Part-Time Parliment”论文介绍了 Paxos，因为它的 multi-degree 算法使计算机科学家很感兴趣；议会协议。那篇文章和澄清文件“Paxos Made Simple”都将 Paxos 定义为具有杰出的领导者，为命令流分配序列号。此外，尊贵的领导者只有在担任领导职务时才发送“准备”消息；在那之后，在 steady-state 中，尊贵的领导者仅流式传输“接受”消息。他还在论文的其他地方说要折叠角色并让所有服务器 运行 算法的所有三个角色。
你问“在 raft 的领导者选举中，Paxos 的方法相对于简单的随机超时方法有什么优势？”我不确定你指的是什么方法？使用 Paxos，您可以随机化超时并发出 Prepare 消息。 Paxos Made Simple 论文指出，只要您遵循 Paxos 协议以“确保安全”，您就可以自由使用超时或其他更快的机制：
The famous result of Fischer, Lynch, and Pat- terson 1 implies that a reliable algorithm for electing a proposer must use either randomness or real time—for example, by using timeouts. However, safety is ensured regardless of the success or failure of the election.
随机超时很容易编码，也很容易理解。然而，在最坏的情况下，它们可能会导致恢复的长时间延迟。你不喜欢你可以使用你自己的领导人选举机制。例如 this one.
看完问题和@simbo1905 的回答后，我觉得我必须投入我的 2 美分，因为我认为问题没有得到回答。
What's the advantage of paxos's approach over the simple random timeout approach in raft's leader election?
tl;dr：Paxos 是最优的，但 Raft 具有更强的实用 活性保证。
有关更多信息，请继续阅读。
正如 Lamport 在 Paxos Made Simple 第 3 节中所述，
It can be shown that phase 2 of the Paxos consensus algorithm has the minimum possible cost of any algorithm for reaching agreement in the presence of faults [2]. Hence, the Paxos algorithm is essentially optimal.
所以Paxos以一种在没有错误的情况下效率最高的方式来实现共识。
另一方面在同一节中他还指出
If multiple servers think they are leaders, then they can all propose values in the same instance of the consensus algorithm, which could prevent any value from being chosen. However, safety is preserved—two different servers will never disagree on the value chosen as the ith state machine command. Election of a single leader is needed only to ensure progress.
这意味着 实际上 Paxos 可以看到违反其活性保证的行为。
Raft 是 Paxos
8-O
...更具体地说，它是具有不同命名的多法令版本。