拜占庭将军问题
我们已知的共识算法，Paxos、Raft解决的都是非拜占庭问题，也就是可以容忍节点故障，消息丢失、延时、乱序等，但节点不能有恶意节点。但如何在有恶意节点存在的情况下达成共识呢？BFT共识算法就是解决这一问题的。即不但能容忍节点故障，还能容忍一定的恶意节点或者说拜占庭节点的存在。我们下面就学习一下BFT算法中的PBFT（Practical Byzantine Fault Tolerance）。BFT算法有非常多的变种，这里只学习PBFT，其他的可以举一反三。
PBFTPBFT核心由3个协议组成：一致性协议、检查点协议、视图更换协议。系统正常运行在一致性协议和检查点协议下，只有当主节点出错或者运行缓慢的情况下才会启动视图更换协议，以维持系统继续响应客户端的请求。下面详解这3个子协议。在讲一致性协议之前，我们屏蔽算法细节先看一下正常情况下大致是怎么工作的，大致流程如下：
客户端发送请求给主节点（如果请求发送给了从节点，从节点会将该请求转发给主节点或者将主节点的信息告知客户端，让客户端发送给主节点）。
主节点将请求广播给从节点。
主从节点经过2轮投票后执行客户端的请求并响应客户端。（协议细节见下面的一致性协议）
客户端收集到来着\(f+1\)个不同节点的相同的响应后，确认请求执行成功。（因为最多有\(f\)个恶意节点，\(f+1\)个相同即能保证正确性）。
一致性协议一致性协议的目标是使来自客户端的请求在每个服务器上都按照一个确定的顺序执行。 在协议中，一般有一个服务器被称作主节点，负责将客户端的请求排序；其余的服务器称作从节点，按照主节点提供的顺序执行请求。所有的服务器都在相同的配置信息下工作，这个配置信息称作视图view，每更换一次主节点，视图view就会随之变化。协议主要分pre-prepare、prepare、commit三阶段，如下图所示：
REQUEST:
首先是客户端发起请求， 请求<REQUEST,o,t,c>中时间戳t主要用来保证exactly-once语义，也就是说对同一客户端请求不能有执行2次的情况，具体实现时也不一定非是时间戳，也可以是逻辑时钟或者其他，只要能唯一标识这个请求就可以了。
PRE-PREPARE:
【1】 收到客户端的请求消息后，先判断当前正在处理的消息数量是否超出限制，如果超出限制，则先缓存起来，后面再打包一起处理。否则的话（当然，没超过也可以缓存处理），对请求分配序列号n，并附加视图号v等信息生成PRE-PREPARE消息<<PRE-PREPARE,v,n,d>,m>，广播给其他节点。简而言之就是对请求分配序号并告知所有节点。
【2】 收到PRE-PREPARE的消息后进行如下处理：
消息合法性检查，消息签名是否正确，消息摘要是否正确。
视图检查，检查是否是同一个视图号v。
水线检查，判断n是否在h和H之间。（h一般是系统稳定检查点，H是上限，会随着h的不断提高而提高）
如果都通过的话，就广播PREPARE消息<PREPARE,v,n,d,i>给其他节点，表示自己收到并认可[n,v]这个请求，进入prepare阶段。如果没有通过，则忽略该消息。
这里想一个问题，从节点能不能收到PRE-PREPARE消息就执行请求呢？答案显然是不能的，因为不能确认本节点与其他节点收到的是相同的请求消息，此时不能确定主节点是不是正常节点，如果主节点是恶意节点呢？比如，发送给从节点1的消息是m，而发送给从节点2的消息是m'，如果直接执行就会出现从节点的不一致。因为不能确认本节点与其他节点收到的是相同的请求消息，所以要通过从节点与从节点交互的方式互相告知收到了请求消息，好让后面阶段对比一下，是否一致。
PREPARE:
收到PREPARE消息<PREPARE,v,n,d,i>后，进行如下处理：
消息合法性检查，消息签名是否正确，消息摘要是否正确。
视图检查，检查是否是同一个视图号v。
水线检查，判断n是否在h和H之间。
如果上面都通过，就将PREPARE消息加入到日志中，并继续收集PREPARE消息，如果收到正确的\(2f\)张（包括自己）PREPARE消息，这里如何验证是否正确呢？主要是收到的PREPARE要与PRE-PREPARE中的v、n、d等信息要匹配，就进入COMMIT阶段，广播COMMIT消息<COMMIT,v,n,D(m),i>。
这一阶段一般也可以称为第一轮投票，目的是什么呢？论文中是这么说的：The pre-prepare and prepare phases of the algorithm guarantee that non-faulty replicas agree on a total order for the requests within a view. 浓缩为两个字就是定序，确定在同一视图下足额的正常的节点都对来自客户端的请求有相同的定序。再说的直白点，就是解决上面提到的，无法确认本节点与其他节点收到的消息是否一致的问题。通过检查相同视图号v及同一序号n下的消息摘要d是否一致来判断同一视图配置下的同一个序号请求的消息是否一致。同时也确保了有足够数量的节点收到了一致的消息请求。