学习分布式系统，Leslie Lamport 绝对是一个绕不开的大师（大爷）。当前分布式系统系中的大部分理论基本上都是这个大爷在上世纪7、80年代奠定的。而这个大爷也因为在分布式系统方面的贡献，获得ACM颁发的2013年度图灵奖。本系列的第一篇文章则选择谈一下其最早的理论：拜占庭将军问题 (The Byzantine Generals Problem)。个人觉得Lamport的很多论文还是非常的有个性的，不过也正是因为这种个性，其早年的一些论文并不太受学术界的待见，即使是后面大名鼎鼎的paxos，也因为TOCS的审稿人无法理解Lamport的这种幽默风格，并且Lamport拒绝修改，拖了好几年最终才勉强改了改才投到TOCS上面。大家有兴趣可以自己看下Lamport这篇论文的原文[1]，看你能不能理解Lamport的幽默吧。下面我根据Lamport的论文简单的阐述一下我对拜占庭将军问题的理解。
1. 什么是拜占庭将军问题
这篇论文选择以战争故事为题材，来阐述分布式系统中的一些难题。故事的背景是：拜占庭帝国军队的几个师驻扎在敌城外准备攻城, 每个军队都由各自的将军指挥，将军们只能通过信使相互沟通。在观察敌情之后, 他们必须制定一个共同的行动计划, 如进攻(Attack)或者撤退(Retreat), 且只有当半数以上的将军共同发起进攻时才能取得胜利。但是非常不幸的是, 其中一些将军可能是叛徒, 试图发出一些错误的行动计划来阻止忠诚的将军达成一致的行动计划。而更不幸的是, 负责消息传递的信使也可能是叛徒, 他们可能篡改或伪造消息, 也可能被敌人抓住。
当然这是一篇计算机领域的论文而不是战争故事。因此在分布式系统领域, 上述拜占庭将军问题中的角色与计算机世界的对应关系如下:
-
将军, 对应计算机节点（进程）;
-
忠诚的将军, 对应运行良好的计算机节点;
-
叛变的将军, 被非法控制的计算机节点;
-
信使被抓, 通信故障使得消息丢失;
-
信使被间谍替换, 通信被攻击, 攻击者篡改或伪造信息。
而在分布式系统中的拜占庭将军问题其实就是：如果计算机节点只能依靠通信相互交流，在既不知道那些是恶意节点，又不能保证通信的正确性的情况下如何来达到共识。
2. 拜占庭将军问题的解决办法
Lamport在论文中根据不同的约束条件给出了两种拜占庭将军问题的解决方案：口信消息型解决方案(A solution with oral message)和签名消息型解决方案(A solution with signed message).
2.1 口信消息型解决方案
口信消息型解决方案, 对于口信消息(Oral message)的进行了如下约束:
-
A1. 任何已经发送的消息都将被正确传达;
-
A2. 消息的接收者知道是谁发送了消息;
-
A3. 消息的缺席可以被检测。
在这三条约束条件下，口头协议的算法描述非常简单：1. 假如其中的一个将军1发出消息，那么将军2到将军 N 都会收到节点1发出的消息。2. 每个将军收到消息之后节点会将消息转发给其他将军。3. 最后每个将军都有一个相同的消息账本。Lamport一番论证得出的结论是：如果将军之间采用口头协议进行通信，若叛徒数少于总将军数的1/3，则拜占庭将军可以达成共识。也就是说，若叛徒数为m，当将军总数n至少为3m+1时，才能解决拜占庭将军问题。详细的论证可以在论文中找到，或者参考[2]。
2.2 签名消息型解决方案
其实我们可以注意到最后每个将军都有一个相同的消息账本，如果能识别叛徒是谁的话是不是可以把对忠诚将军的数量要求降的更低一点呢？因此Lamport在口信消息型解决方案的约束上又增加了两条约束，而这就是签名消息型解决方案。
书面协议相对于口头协议来讲则添加了更多的隐含条件：
-
A4. 忠诚将军的签名无法伪造，而且对他签名消息的内容进行任何更改都会被发现;
-
A5. 任何人都能验证将军签名的真伪。
相对于口信消息型解决方案，签名消息型解决方案的所有消息都可以追根溯源。这使得只要忠诚将军的数量超过一半，所有拜占庭将军就可以达成共识。同样详细的论证可以在论文中找到，或者参考[2]。由于是漫谈不做过多证明。
3. 小结
Lamport本身是数学系出身，这篇论文也非常的理论。不过非常幸运的是Lamport用他幽默的方式把一个非常枯燥的问题用讲故事的方式介绍给读者。这也使得后来分布式系统中，以能否解决拜占庭问题为标准把共识算法分为了两类。
3.1 非拜占庭容错算法
通常不能在拜占庭情况下达成一致的的算法则被称之为非拜占庭容错算法如：Paxos，Raft。这类算法的目的在于解决分布式系统中的容错问题。能保证系统在某些节点宕机以后继续正常运行，但不能防止恶意节点的攻击。也就是说, 非拜占庭容错算法只能用于可能存在消息丢失, 消息重复, 但不存在消息被篡改或伪造或者恶意攻击的场景如：分布式存储中的异地备份。
3.2 拜占庭容错算法
而能在拜占庭情况下达成一致的的算法则被称之为拜占庭容错算法如：POW，PBFT。这类算法的目的在于解决分布式系统中的即需要容错又需要防止恶意攻击的问题。其实在比特币出来之前很少有人去讨论拜占庭容错问题，学术界也没多少论文，工业界也大都是在非拜占庭情况下去进行系统设计的。但是区块链技术很明显又让这个问题重新引起了人们的重视。因此下一篇文章《漫谈分布式系统系列之：从非拜占庭共识到拜占庭共识 》中我会简单谈一下Paxos以及POW两个经典共识算法。
4. Reference
[1] The Byzantine Generals Problem
[2] 拜占庭将军问题深入探讨
[3] 拜占庭将军问题