分布式系统的一致性算法是一个从上世纪70年代就开始研究的经典问题。在这个问题上，有一篇是《Impossibility of Distributed Consensuswith One Faulty Process》，论文中提出了可以说是最重要的分布式系统定理：FLP不可能性。

任何分布式算法或定理，都尤其对系统场景的假设，这称为系统模型。

FLP基于下面几点假设：

  • 异步通信 与同步通信的最大区别是没有时钟、不能时间同步、不能使用超时、不能探测失败、消息可任意延迟、消息可乱序
  • 通信健壮 只要进程非失败，消息虽会被无限延迟，但最终会被送达；并且消息仅会被送达一次（无重复）
  • fail-stop模型 进程失败如同宕机，不再处理任何消息。相对Byzantine模型，不会产生错误消息
  • 失败进程数量 最多一个进程失败

在现实中，我们都使用TCP协议（保证了消息健壮、不重复、不乱序），每个节点都有NTP时钟同步（可以使用超时），纯的异步场景相对比较少。但随着智能终端的发展，每个手机会为省电而关机，也会因为不在服务区而离线，这样的适用场景还是存在。

我们再衡量一个分布式算法是否正确时有三个标准：

  • Termination（终止性） 非失败进程最终可以做出选择
  • Agreement（一致性） 所有的进程必须做出相同的决议
  • Validity（合法性） 进程的决议值，必须是其他进程提交的请求值

终止性，描述了算法必须在有限时间内结束，不能无限循环下去；一致性描述了我们期望的相同决议；合法性是为了排除进程初始值对自身的干扰。

FLP不可能性定理： 在异步通信场景，即使只有一个进程失败，也没有任何算法能保证非失败进程达到一致性！

因为同步通信中的一致性被证明是可以达到的，因此在之前一直有人尝试各种算法解决以异步环境的一致性问题，有个FLP的结果，这样的尝试终于有了答案。

在FLP定理中，我们假设了异步网络是可靠的, 即消息有延迟，但是所有的消息都会被且仅会被投递一次, 这是一个很强的假设, 现实中，很少有网络能达到这样的可靠性。 而且FLP也不要求所有非故障节点都达成一致, 只要有一个节点进入确定状态就算达成一致了, 并且需要达成的结果取值范围是{0, 1}, 加上前面提到的最多只有一个节点发生故障, 然而即便是这样的接近理想的情况，FLP定理还是指出了，不存在一个一致性算法能够保证节点达成共识，更不用说真实世界中存在的网络分区以及拜占庭节点了.

FLP定理限定了我们对分布式系统共识算法求解的上限，既然不存在完美解，那么退而求其次，是否能够放松要求，在这个不完美的世界获得一个够用的一致性呢？

在区块链中，共识则是在组成网络的分布式节点中达成。某个记账节点提议了一个区块应该包含哪些交易数据，然后把该区块广播给其他的参与节点，其他节点要就是否使用这个区块达成一致。

而异步共识，就是在这样的一个分布式系统中，一个消息发出后，发送方无法预期什么时候能够收到回应。带着这样的前提，系统的参与方如何就一个问题的取值达成一致。

比特币这样的公有链，是一个匿名系统，任何人都可以加入到网络中，竞争记账权。也就是说，系统中对加入的节点没有要求，也没有任何验证，如果是采用一个节点一票的方式，很容易遭受所谓女巫攻击(Sybil Attack)：攻击者批量制造大量的节点加入系统，通过绝对多数的投票权发起攻击，对于一个节点而言，无从辨别其他节点是普通节点还是拜占庭节点，也可能其他节点就是普通节点，只是在一些有利益影响的事情上表现出拜占庭行为。所以基于IP或者CPU的投票制度在公有链上不能发挥应用的作用，因为这些不是稀缺资源，尤其是存在“僵尸网络”的情况下。

FLP定理堵死了我们在传统计算机算法体系下提出解决方案的可能性。

既然传统思路走不同，突破只能来自体系之外。首先我们假定节点背后的人都是经济理性人，不会做成本高于收益的事情。如果我们能够设计一种博弈机制，让遵守约定的行为的收益高于违反约定的收益，那么基于经济理性人假设，节点就不会表现破坏行为。

共识机制的设计必须遵循以下原则：

  • 经济激励
  • 博弈机制

详细介绍请详见共识算法，区块链的引擎

附录 - 区块链常用共识算法：

1. PoW

工作量证明算法，BTC为代表，猜上一个块提出的hash值是哪一个随机数的hash值，简单粗暴解决共识问题，但是浪费算力资源。

2. PoS

权益证明算法，对比各自钱包中持有币的币龄总和币天，解决了算力浪费的问题，但是也同样存在问题，主要是没有专业化，拥有权益的参与者未必希望参与记账，或者保证金投注，主要代表有PPC。

3. DPos

权益授权证明，比特股BitShares采用的区块链公识算法，从有权参与记账的节点中选取一个代理节点，进行验证和记账，记账速度更快，但是依赖于代币，有很多商业应用不需要代币存在。

4. Casper

投注共识，也是Pos的一种，以太坊下一代共识算法。

5. Ripple Consensus

瑞波共识机制，更像一个俱乐部，新接纳成员需要5%的成员投票通过，是一个中心。

6. PBFT

实用拜占庭容错算法，在分布式计算机上，不同的计算机透过交换信息达成共识，经历预报->准备->确认->提交几个阶段。

7. dBFT

委托拜占庭容错算法，小蚁币的共识机制，增加了动态进入退出共识节点，按持有权益比例的投票机制，通过投票决定共识参与节点记账，每个区块具有最终性，不会分叉。 缺点是当有1/3以上的记账人停止工作后，或者联合作恶，系统将会无法工作。

8. PoR

资源证明算法，通过节点的CPU、硬盘、内存、宽带等资源为依据，取得记账权。缺点是怎样保证节点上传的资源数据是真实的？

9. Quorum Voting

仲裁投票

10. PoB

铸币证明，

11. Paxos

基于选举领导者的共识机制

12. Raft

选举者需要说服其他节点选举自己

13. PoET

消逝时间量证明，需要Intel的CPU硬件支持。

14. Ben-Or’s

随机算法。

15. Proof of Hdd Capacity

硬盘容量证明，BurstCoin共识算法。

16. Proof of Stack Time

权益时间证明，veriCoin共识算法。

17. Aspnes and Herlihy

随机共识算法，本质是一种随机漫步算法。

18. PoP(Proof of Presence)

出席证明，奖励存储了块数据的节点钱包。