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

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 年曾发表论文《部分同步存在的共识》，文中阐述了关于拜占庭容错共识的一个重大进展：在“部分同步系统”中达成共识。

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

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

本文解释了部分同步假设的两个版本:

• 假设信息传输所需的时间上限是存在的，但是是未知的。目标是达成共识，先不考虑实际的上限。
• 假设信息传输所需的时间上限是已知的，但是它只能保证在某个未知的时间(也称为“全球标准化时间”，GST)启动。目标是设计一个能够达成共识的系统，无论这个未知的时间在什么时候。

（编辑：衢州站长网）

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