PBFT

共识算法的集群中有很多节点，它们都可以处理客户发来的请求，但是客户发送请求的顺序对于最终的结果存在很大的影响。因此，为了统一这个结果的顺序，PBFT采取选举一个leader的做法。而这个Leader是随机产生的。
基于拜占庭将军问题，一致性的确保主要分为这三个阶段：预准备（pre-prepare）、准备(prepare)和确认(commit)。流程如下图所示：
其中C为发送请求端，0123为服务端，3为宕机的服务端，具体步骤如下：

1. Request：客户Client发送请求给0，即leader；
2. Pre-Prepare：服务端0收到C的请求后进行广播，扩散至123‘’
3. Prepare：123,收到后记录并再次广播，1->023，2->013，3因为宕机无法广播
4. Commit：0123节点在Prepare阶段，各个节点自行进行日志执行，若收到超过一定数量的相同结果，则进入Commit阶段，广播Commit请求
   5.Reply：0123节点在Commit阶段，若收到超过一定数量的相同请求，则对C进行反馈

Raft

Raft的背景是非拜占庭条件下，即没有恶意节点。
Raft也会产生Leader，这里leader是由竞选产生的。

竞选需要发送请求投票请求，当大多数节点给候选人投票时，候选人当选为leader。每一个leader有term任期的概念。

raft里，当某一个节点察觉不到leader 的存在时，就会自动变成candidate候选人，发起竞选。

raft里存在平票的情况，因此raft引入randommized timer让每一个follower在感受不到leader的心跳之后，成为candidate的时间进行随机差异化。

即有些几点会等的更久，越早竞选的节点越容易成为leader，因此平票的概率便小了很多。

Paxos

paxos是以提案制进行工作的公式算法。当客户发送一个请求时，接受到请求的节点将Propose发送给其他节点，并附上一个number,随后Acceptor也就是其他节点，对number进行判断，合法之后接受请求。

Proposer之后再将具体的propose发送给Acceptor，Acceptor完成后告知Proposer。

因此Paxos相比于raft，存在两轮交互的过程。

刚刚提到Acceptor的合法判断，当同时存在多个Proposer发送请求的时候，Acceptor会根据Proposer发送的number来判断，听从谁的意见。这里的number在实际运用中可以理解为费用。

总结

最后附上一张对比图，首先这三种公式算法里面的role是不同的，不仅体现在角色名字上，还体现在功能上。RAFT和PBFT存在leader选举的情况，而Paxos可以理解为不存在，也可以理解为Number大的为Leader，但这个Leader只处理一次请求。

在处理请求上，RAFT直接由leader进行处理，follower无条件接受。Paxos则需求比较同时期不同请求number的大小；而PBFT则需要大多数收到2/3节点的相同结果；

由于PBFT是在非拜占庭条件下的共识算法，因此需要2f+1个节点回应才能确定最终节点。这里容纳的恶意节点个数为1/3。

参考文献

[1]: Ongaro D, Ousterhout J. In search of an understandable consensus algorithm[C]//2014 {USENIX} Annual Technical Conference ({USENIX}{ATC} 14). 2014: 305-319.
[2]: Lamport L. Paxos made simple[J]. ACM Sigact News, 2001, 32(4): 18-25.