这个女生说：弄懂本文前，你所知道的区块链可能都是错的

阶段3：学习阶段

1. 当决策者通过一个提议时，它会对所有学习者进行响应 (“accept,” n, v)。
2. 学习者收到大多数决策者发出的 (“accept,” n, v)，就会以 v 为最终决定值，并把 (“accept,” n, v) 通知到所有其他的学习者。
3. 学习者收到 (“accept,” n, v)，把 v 作为最终决定值。

https://www.myassignmenthelp.net/paxos-algorithm-assignment-help

讲到这里，相信很多同学应该已经懵逼了，但是先别急，更让人懵逼的可能还在后头。

我们都知道，每个分布式系统都会有发生异常。在这种算法中，如果提议者由于信息丢失等原因出错，那么最终决定可能会被延迟，Paxos 算法在第一阶段中使用了一个新版本号，来避免之前的计算产生的影响。

Paxos 确实有些难以理解，许多操作细节都没有解释透彻。怎样知道提议者出错的时间点?何时重新开始下一轮计算?想确定这些时间点我们是否需要一个同步时钟来设置超时时间?这些问题，都需要我们去思考。

此外，为了在实际应用中更加灵活，Paxos 关键领域的不少规范都是开放式的。诸如领导者选择、故障检测和日志管理等概念都比较模糊或完全没有定义。

这样的设计理念成为 Paxos 最大的不足之一，理解难、实现难，驾驭分布式系统更难。

在 Paxos 中，虽然超时在算法中没有明确提及，但在实际操作中，想要实现终止，等待一个超时后，必须选择一个新的提议者。否则，决策者就不会输出下一个值，整个系统就停止了。

Raft算法

2013 年，Ongaro 和 Ousterhout 发布了一种新的共识算法，用于叫做 Raft 的复制状态机，主要注重协议的实用性和可理解性。

Raft 算法主要有两个过程，一个是领导者选举，另一个是日志复制。系统中的节点被分为三种角色：

• 领导者——负责与用户沟通和日志复制
• 跟随者——被动响应请求，类似于选民
• 候选者——临时角色，某节点想成为领导者，就要发起投票请求，同时自己变成候选者。如果选举成功，则成为领导者，否则退回为跟随者。

这三种角色都不是固定的，可以随着环境条件互相转换，但是在某一个时刻只能担任其中一种。

为了实现共识，候选者需要向跟随者发出信息，请求他们的投票，一旦被系统中大多数认可选定后，就成为领导者，跟随者们就跟随其操作。

假设系统中的节点总数为 n，故障节点为 x，正常节点只需要比故障节点多一个，即 x+1，系统就能达成共识。

因此，Raft 算法支持的最大故障节点数量是(n-1)/2。

Raft 算法的容错机制只支持故障节点，不能支持恶意节点，并且使用共享超时来实现终止。

如果进程崩溃并重新启动，在声明自己的领导者身份之前，至少需要等待一个超时时间，并保证会取得进展。

Paxos 和 Raft 是比较传统的共识算法，它们能够使用同步假设(即超时)在异步环境中一展身手，它们只对崩溃故障容错，面对拜占庭故障无能为力。

崩溃故障是更容易把控的，因为程序无法进行恶意行为。我们可以将进程建模，以 0 或 1 代表正常或崩溃。因此，在崩溃容错系统中，只要大多数进程能够达成共识，就可以构建分布式系统。

而在开放和分散的系统(如公链)中，网络中的节点是不受用户控制的，节点有不同的动机，可以撒谎、配合或随心所欲，一半以上的可靠节点可以约定好互相撒谎，互相之间必然发生冲突。

所以在拜占庭系统中，不是假设简单多数就可以达成共识的。

对于这种行为，Raft 应对乏力。举例来说，如果选出来的领导者是拜占庭节点，并且与其他节点有着紧密的联系，那么系统就危险了。之前讲过，我们建立的系统模型，要么对简单故障容错，要么对拜占庭故障容错。

总之，Raft 和 Paxos 具有简单的容错能力，但对拜占庭故障无能为力。

那么问题来了，拜占庭环境怎么办?!

在解决这个问题之前，我们先来了解一个概念——

拜占庭将军问题(Byzantine Generals Problem)

拜占庭将军问题由 Leslie Lamport、Robert Shostak 和 Marshall Pease 在同名论文中提出，分布式系统依靠交换信息来整体协作，然而其中的节点会作恶，网络会崩坏，因此系统不能达成一致。

拜占庭容错协议就是为了应对节点的恶意行为，论文为解决拜占庭将军问题提供了第一个证明：

• 如果一个系统共有 n 个节点，其中有 x 个是拜占庭节点，该系统如果想达成共识，n 必须满足：n>3x + 1

原因如下：

• 如果出错节点个数为 x，系统如果想正常运转，必须先协调的节点个数为 n - x，(因为 x 个节点可能有问题/复杂，并且没有响应)。

然而不排除这种可能，不响应的x也许并不是出错了,也可能是有响应的只不过由于网络等原因未被察觉。如果我们想要非故障节点的数量多于故障节点，n 必要满足：

• n- x - x > x，

即：n > 3x + 1

然而，该论文所演示的算法仅适用于同步环境，那貌似拜占庭环境、异步环境两者我们只能解决一个了，或者只能等待奇迹的发生。

学者们做了大量的研究工作，力求攻破在拜占庭和异步假设环境中的共识问题。

下面便是见证奇迹的时刻——

我全都想要!!!

接下来，我们将研究两种算法(DLS 和 PBFT)，打破拜占庭+异步的障碍的奇迹，我们在慢慢靠近。

DLS 算法

Dwork、Lynch 和 Stockmeyer(“DLS”算法的由来)在 1988 年曾发表论文《部分同步存在的共识》，文中阐述了关于拜占庭容错共识的一个重大进展：在“部分同步系统”中达成共识。

你可能还记得，在同步系统中，信息从发送到接收所需的时间是有固定上限的，而在异步系统中，该上限不存在。

这里的“部分同步”位于同步系统和异步系统之间。

（编辑：威海站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!