Paxos

Paxos 和 Raft，具有简单容错能力，对系统崩溃或网络延迟等故障容错，需要同步信息传输环境，适用于严格受控的私链环境。可解决CFT（crash Fault）

BFT情况下，机器还可能‘’撒谎‘’

解决非拜占庭问题的分布式一致性算法（Paxos，Raft）

DLS 和 PBFT，可对拜占庭故障容错，在异步信息传输环境中需要做某种形式的同步假设（超时），适用于新加入节点需要验证的联盟链。

## Paxos

Paxos：强一致性协议

Gossip协议：节点管理.流言协议

paxos算法主要解决的问题就是如何保证分布式系统中各个节点都能执行一个相同的操作序列。在2f+1个节点的集群中，允许有f个节点不可用

paxos是在多个成员之间对某个值(提议)达成一致的一致性协议。这个值可以是任何东西。比如多个成员之间进行选主，那么这个值就是主的身份

paxos分为prepare和accept两个阶段。协议中有两个主要的角色，proposer和acceptor。

value被majority accept之前，每个acceptor可以accept多个不同的值。但是，一旦一个value被majority accept(即value达成一致)，那么这个value就不会变了。因为prepare阶段会将该value给找出来，随后accept阶段会使用这个value，后续的所有的提案都会选择这个value。

需要注意的是，每个阶段都是收到majority的响应后即开始处理。并且由于机器会宕机，acceptor需要对acceptedProposalID, acceptedValue和minProposal进行持久化。

从流程中可以看出prepare有两个作用:

大的proposal id会block未完成的小的proposal id达成一致的过程，所以为了减少无效的prepare请求，每次都选择比自己以往见过的proposal id更大的id。

一旦某个value达成一致，那么后续的prepare都会找到这个value作为accept阶段的值

可以看出，一次paxos达成一致至少需要两次网络交互

Paxos并不适合于拜占庭容错系统

[更多内容](https://blockchaindev.org/archives/10-from-Paxos-to-PBFT.html)

[更详细](https://www.hollischuang.com/archives/693)

###系统难点

1、管理多个proposer并发执行

2、容忍var变量的不可变性

3、容忍任意Proposer的故障

4、容忍半数以下的acceptor的故障

解决方案一：互斥访问权，可以解决难点1和难点2，但是无法解决难点3和难点4

解决方案二：抢占式访问权

proposer向acceptor发出的每次请求都要带一个编号（epoch），且编号间要存在全序关系。一旦acceptor接收到proposer的请求中包含一个更大的epoch的时候，马上让旧的epoch失效，不再接受他们提交的取值。然后给新的epoch发放访问权，让他可以设置var变量的值。

为了保证var变量取值的不变性，不同epoch的proposer之前遵守后者认同前者的原则：

>在确保旧的epoch已经失效后，并且旧的epoch没有设置var变量的值，新的epoch会提交自己的值。

当旧的epoch已经设置过var变量的取值，那么新的epoch应该认同旧的epoch设置过的值，并不在提交新的值。