区块链快速入门（三）——CFT（非拜占庭容错）共识算法

大家好，欢迎来到IT知识分享网。

一、CFT简介

二、Paxos算法

1、Paxos算法产生背景

2、Paxos算法简介

3、Paxos算法原理

4、提案ID的生成算法

 ir(0<=ir<n)

，Proposal编号的任何值s都应该大于它已知的最大值，并且满足：

s %n = ir    =>     s = m*n + ir

5、Paxos算法的活锁

6、Paxos算法异常处理

7、Paxos算法应用

三、三军问题

1、三军问题简介

2、两参谋先后提议场景

A、参谋1发起提议，派通信兵带信给3个将军，内容为（编号1）；
B、3个将军收到参谋1的提议，由于之前还没有保存任何编号，因此把（编号1）保存下来，避免遗忘；同时让通信兵带信回去，内容为（ok）；
C、参谋1收到至少2个将军的回复，再次派通信兵带信给3个将军，内容为（编号1，进攻时间1）；
D、3个将军收到参谋1的时间，把（编号1，进攻时间1）保存下来，避免遗忘；同时让通信兵带信回去，内容为（Accepted）；
E、参谋1收到至少2个将军的（Accepted）内容，确认进攻时间已经被大家接收；
F、参谋2发起提议，派通信兵带信给3个将军，内容为（编号2）；
G、3个将军收到参谋2的提议，由于（编号2）比（编号1）大，因此把（编号2）保存下来，避免遗忘；又由于之前已经接受参谋1的提议，因此让通信兵带信回去，内容为（编号1，进攻时间1）；
H、参谋2收到至少2个将军的回复，由于回复中带来了已接受的参谋1的提议内容，参谋2因此不再提出新的进攻时间，接受参谋1提出的时间；

3、两参谋交叉提议场景

1） 参谋1发起提议，派通信兵带信给3个将军，内容为（编号1）；
2） 3个将军的情况如下
A、将军1和将军2收到参谋1的提议，将军1和将军2把（编号1）记录下来，如果有其他参谋提出更小的编号，将被拒绝；同时让通信兵带信回去，内容为（ok）；
B、负责通知将军3的通信兵被抓，因此将军3没收到参谋1的提议；
3） 参谋2在同一时间也发起了提议，派通信兵带信给3个将军，内容为（编号2）；
4） 3个将军的情况如下
A、将军2和将军3收到参谋2的提议，将军2和将军3把（编号2）记录下来，如果有其他参谋提出更小的编号，将被拒绝；同时让通信兵带信回去，内容为（ok）；
B、负责通知将军1的通信兵被抓，因此将军1没收到参谋2的提议；
5） 参谋1收到至少2个将军的回复，再次派通信兵带信给有答复的2个将军，内容为（编号1，进攻时间1）；
6） 2个将军的情况如下
A、将军1收到了（编号1，进攻时间1），和自己保存的编号相同，因此把（编号1，进攻时间1）保存下来；同时让通信兵带信回去，内容为（Accepted）；
B、将军2收到了（编号1，进攻时间1），由于（编号1）小于已经保存的（编号2），因此让通信兵带信回去，内容为（Rejected，编号2）；
7） 参谋2收到至少2个将军的回复，再次派通信兵带信给有答复的2个将军，内容为（编号2，进攻时间2）；
8） 将军2和将军3收到了（编号2，进攻时间2），和自己保存的编号相同，因此把（编号2，进攻时间2）保存下来，同时让通信兵带信回去，内容为（Accepted）；
9） 参谋2收到至少2个将军的（Accepted）内容，确认进攻时间已经被多数派接受；
10） 参谋1只收到了1个将军的（Accepted）内容，同时收到一个（Rejected，编号2）；参谋1重新发起提议，派通信兵带信给3个将军，内容为（编号3）；
11） 3个将军的情况如下
A、将军1收到参谋1的提议，由于（编号3）大于之前保存的（编号1），因此把（编号3）保存下来；由于将军1已经接受参谋1前一次的提议，因此让通信兵带信回去，内容为（编号1，进攻时间1）；
B、将军2收到参谋1的提议，由于（编号3）大于之前保存的（编号2），因此把（编号3）保存下来；由于将军2已经接受参谋2的提议，因此让通信兵带信回去，内容为（编号2，进攻时间2）；
C、 负责通知将军3的通信兵被抓，因此将军3没收到参谋1的提议；
12） 参谋1收到了至少2个将军的回复，比较两个回复的编号大小，选择大编号对应的进攻时间作为最新的提议；参谋1再次派通信兵带信给有答复的2个将军，内容为（编号3，进攻时间2）；
13） 将军1和将军2收到了（编号3，进攻时间2），和自己保存的编号相同，因此保存（编号3，进攻时间2），同时让通信兵带信回去，内容为（Accepted）；
14） 参谋1收到了至少2个将军的（accepted）内容，确认进攻时间已经被多数派接受；

四、Multi-Paxos算法

1、Multi-Paxos算法简介

2、PaxosLease

五、Raft算法

1、Raft算法简介

2、Raft算法角色

3、Term（任期）

4、Raft算法的流程

5、Raft算法的应用