用三国杀讲分布式算法，舒适了吧？

前言

• 担心算法过于复杂，所以花的时间很少。
• 网上的资料能用大白话将分布式算法讲清楚的比较少。
• 学习分布式算法没有一条清晰的路线。

学习路线

四大基础理论：

1. 拜占庭将军问题
2. CAP 理论
3. ACID 理论
4. BASE 理论

八大分布式协议和算法：

1. Paxos 算法
2. Raft 算法
3. 一致性 Hash 算法
4. Gossip 协议算法
5. Quorum NWR 算法
6. FBFT 算法
7. POW 算法
8. ZAB 协议

拜占庭将军问题

2.1 三国杀身份牌

主公

主公身份牌

忠臣

忠臣身份牌

反贼

内奸

内奸身份牌

2.2 还原拜占庭问题

2.3 一方选择撤退

• 刘备决定进攻，通过信使告诉曹操和孙坚进攻。
• 曹操决定撤退，通过信使告诉刘备和孙坚撤退。
• 孙坚决定进攻，通过信使告诉曹操和刘备进攻。

一方选择撤退

2.4 内奸登场-撤退

• 刘备决定进攻，通过信使告诉曹操和孙坚进攻。
• 曹操决定撤退，通过信使告诉曹操和孙坚撤退。
• 孙坚决定撤退，通过信使告诉曹操和刘备撤退。

内奸登场-撤退

2.5 内奸使诈-一进一退

• 刘备决定进攻，通过信使告诉曹操和孙坚进攻。
• 曹操决定撤退，通过信使告诉曹操和孙坚撤退。
• 孙坚作为内奸使诈，通过信使告诉刘备进攻，告诉曹操撤退。

内奸使诈-一进一退

拜占庭问题解法

解法一原理

1. 先发送作战信息的将军我们把他称为指挥官（袁绍），另外的将军我们称作副官（刘备，曹操，孙坚）。
2. 指挥官将他的作战信息发送给所有的副官。
3. 每一位副官将从指挥官处收到的作战信息，作为自己的作战指令；假如没有收到指挥官的作战信息，将把默认的撤退作为作战指令。

第一轮

1. 第一轮指挥官（袁绍）已经发送指令了，现在就需要刘备、曹操、孙坚依次作为指挥官给其他两位副将发送作战信息。
2. 然后这三位副将按照少数服从多数的原则，执行收到的作战指令。

孙坚使诈 - 两撤退

孙坚使诈 - 两撤退

孙坚使诈 - 一进一退

孙坚使诈 - 一进一退

3.2 孙坚作为指挥官

第一轮

1. 曹操向刘备和袁绍发送进攻指令。
2. 刘备向曹操和袁绍发送进攻指令。
3. 袁绍向曹操和刘备发送撤退指令。

第二轮

3.3 小结

如果叛将人数为 m，将军数 n >= 3m + 1，那么就可以解决拜占庭将军问题。

前提条件：叛将数 m 一致，需要进行 m + 1 轮的作战协商。

拜占庭解法二——签名

• 签名无法伪造，对签名消息的内容进行任何更改都会被发现。
• 任何人都能验证将军签名的真伪。

总结

• 将军对应计算机节点。
• 忠臣的将军对应正常运行的计算机节点。
• 叛变的将军对应出现故障并会发送误导信息的计算机节点。
• 信使被杀对应通讯故障、信息丢失。
• 信使被间谍替换对应为通讯被恶意攻击、伪造信息或劫持通讯。