分布式算法和协议-思维导图

拜占庭问题

拜占庭将军问题是一个协议问题，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。如果叛徒达到了这些目的之一，则任何攻击行动的结果都是注定要失败的，只有完全达成一致的努力才能获得胜利

在比特币算法之前， 世界上并没有一个非常完美的方法来解决“拜占庭将军问题” [5] 。

究其根底，“拜占庭将军问题”最终想解决的是互联网交易、合作过程中的四个问题： [5]

（1）信息发送的身份追溯 [5] ；

（2）信息的私密性 [5] ；

（3）不可伪造的签名 [5] ；

（4）发送信息的规则 [5] 。

“拜占庭将军问题”其实就是网络世界的模型化 [5] 。

分布式算法只考虑故障容错，不考虑信息容错，考虑信息容错的只有区块链等相关算法。

算法比较

这里的ZAB为何是最终一致性而不是强一致性？参考

• 写是强一致性，单领导者模型，写需要majority保证，脑裂情况下也可以写强一致
• 读两种接口，1：读单个机器的，2：只读主的。但脑裂时多个主还是不能强一致性。
• etcd做了读的优化，读时也需要majority(多数同意)，需要大伙同意认为它是主，但牺牲了效率。

这里的一致性是从读写方面，写一致性，都写成功，读一致性，从提供的读接口任意时刻咋读都一样。和事务一致性不太一样。

分布式互斥方法(集中，民主协商，轮值ceo(令牌))

分布式选举算法：bully, raft, zab

分布式事务: 2pc(xa), 3pc, 分布式消息

分布式锁(db, redis, zk)

分布式强一致性(paxos, raft),弱一致性(quorum nwr,gossip)

Quorum NWR 的三要素

N 表示副本数，又叫做复制因子（Replication Factor）。也就是说，N 表示集群中同一份数据有多少个副本，就像下图的样子：

W，又称写一致性级别（Write Consistency Level），表示成功完成 W 个副本更新，才完成写操作：

R，又称读一致性级别（Read Consistency Level），表示读取一个数据对象时需要读 R 个副本。你可以这么理解，读取指定数据时，要读 R 副本，然后返回 R 个副本中最新的那份数据