众所周知，分布式系统可以实现海量数据处理能力和可扩展计算能力。区块链系统作为一种分布式系统，多个节点之间如果想要对某个状态达成一致结果，则需要依靠共识。

上周举行的TRIAS WORKSHOP，胡志琳博士系统地介绍了共识算法及其容错，小编将视频内容整理成文，以供大家学习：

由于文章较长，将分成上下两篇呈现。本篇文章为上篇，涉及三个部分;

1.  分布式系统的基本问题，以及相关的模型；

2.  分布式系统理论，这部分主要介绍了FLP不可能定理、CAP定理、BASE定理；

3.  分布式系统共识算法，这部分主要介绍了“拜占庭共识算法”。

以下是分享原文：

---

谢谢大家今天抽时间一起来听这个分享。

今天的分享内容就是把分布式系统、共识算法基本理论、基本问题，还有相应的性能比较，和大家分享一下。

一、分布式系统的基本问题

现在就开始从第一部分讲起——分布式系统。

图1

简单的讲，分布式系统就是一组通过网络通信的节点，然后它们是可以协调一致地完成共同的任务。

从图1右边部分可以看到，之前的中心式拓扑结构是一个在中间的中心服务器，节点呈星型分布在它(中心服务器）的周围。

而在分布式系统里面，比如区块链，每个节点都是平权的，都有同样的权利，不存在中心服务器和终端的差别。

这里面有一些主要的问题，例如每个节点是否能够正常运行？如果不能正常运行的话，那就可能崩溃；

节点和节点之间主要是通过网络通讯的，而网络可能会发生延迟、不稳定、中断等情况；

第三种情况是现在最难解决的问题，即有一些恶意节点对整个网络发起攻击，比如说我们常说的“双花攻击”。

图2

解决上述这些问题之前，首先要把它模型化、抽象化，在这里主要就是形式化的模型；从网络的角度来讲，分布式系统模型可以分为两类：同步模型和异步模型；

它们的差别是什么呢？如图2的表格，首先是每个节点自身的时钟漂移，对同步模型来讲，每个时间漂移虽说每个节点的时钟不一样，但是时钟的差异实际上是有上限的，但对异步模型来讲，这个是没有上限的。

网络传输时间也是，对同步模型来说，两个节点之间，可以保证在某一个确定的时间内消息能够准确地到达，而对异步模型来讲，这个延迟的上限是无法确定的。

另外一个是节点的计算速度，在同步模型每个节点的速度，一般来说差不多一样，但对异步模型来讲，节点的计算速度也是不可预料的。

刚才这个表(图2）主要是列出了从网络模型的角度对分布式系统的分类；

从故障模型这个角度来讲，如果只有节点崩溃，或者是网络down了这种情况的话，称之为非拜占庭故障。

如果是有恶意节点的话，就是拜占庭故障。这个拜占庭故障是非常难解的，而且如果要实现在拜占庭问题下达成一致共识的话，算法的复杂度、所消耗的通信性能是要远远超出非拜占庭故障的。

二、分布式系统理论

下面再说一下，这个分布式系统有哪些基本的原理。

这里面主要是有两个不可能原理，一个FLP不可能原理，(FLP这三个字母是发表这个定理的作者姓名的首字母缩写) 讲的问题是说基于前面的异步模型，即使一个最小的模型、即使存在最简单的失效故障模型的时候，也不存在一个可以解决一致性问题的确定性算法。这里面的关键点在于，最简单的模型以及不存在一个确定性的算法。

第二个不可能原理，就是CAP原理。尤其在传统的或者经典的分布式系统里，大家都非常熟悉这个定理。比如说一个系统里面不可能同时保证强一致性、可用性和分区容忍性。如果是在实际情况中往往会根据工程特点，通过弱化其中的某个特性来保证其它两个特性。

第三个是BASE理论。它是对CAP原理的延伸，像CAP理论有强一致性；BASE理论的话，BA是一个基本可用性，S是软状态，E就是最终一致性。

比如说比特币，它的共识实际上就是最终一致性。比如说在某一时刻并不能保证现在的块一定是有效确认的块，每一个块在出块后，需要隔一定的时间来确认，这个时间越长，那么这个块作为有效块的可能性越大，这个就是最终一致性。

通过这三个特性，稍微牺牲掉一些对一致性的约束，就能够得到一些在实际性中满足要求的分布式系统。

三、分布式系统共识算法

有了前面一些基本的问题、从这些问题里抽象出的模型，还有从理论上来保证哪些问题是不可能解决的、哪些问题是可以做到的，以及怎么才能够达到某些性能要求。

结合这些问题以及前面基础来看，如何解决这个分布式系统里面的共识问题，那就需要共识算法了。

基本来讲，共识算法目前主要分为这三类：

第一类，Paxos用来解决非拜占庭分布式异步网络共识问题；

第二类，BFT用来解决拜占庭传统分布式异步网络共识问题；

第三类, POW则是用来解决拜占庭区块链分布式异步网络共识问题；

前面两类在传统的分布式里用的比较多，能够保证在一个网络里面正常工作，正常工作的网络中的节点一般比较少。

如果我们想要做一个公链，从技术发展的过程来看，POW是第一个能够支持上万个节点甚至更大规模节点的共识算法。

后面会讲到这几个算法之间的联系、区别，还有为什么说POW能够支持上万个节点，而前面两个算法却支持不了，只能支持比较少的节点。

更多内容，请关注我们的下篇文章~