关键字：拜占庭、分布式一致性、不可信网络
预估阅读时长：20分钟
相比之前阅读的论文，拜占庭将军问题花费了我更长的时间，在阅读的过程中我在思考：为什么我会读的这么慢？相信肯定有小伙伴在阅读论文的时候跟我一样一样的，也就只有两点看不懂，这个也看不懂，那个也看不懂.....
针对这个问题我仔细想了一下原因：因为我之前并没有这种不可信环境下的分布式一致性的经验，平时的工作也接触不到这类问题，也就是说：我压根就没有理解论文要解决什么问题。我觉得这点很关键，一脸懵逼的为了读论文而读，越看不懂越着急，急眼了为了安慰自己还非得硬着头皮往下看，结果还是一脸懵逼。
所以我认为阅读论文有一个关键点：首先一定要弄清楚作者所解决的问题到底是什么，为什么会存在这个问题？了解清楚问题之后，再思考一下如果这个问题让你来解决，你会怎么办？带着清晰的疑问去阅读论文的话会好一点。
何为拜占庭将军问题
好，下面我们步入正题：什么是拜占庭将军问题？
拜占庭将军问题也是由分布式理论大佬Leslie Lamport提出的（再次膜拜一下老人家，这人有点顶），目的是为了解决不可信环境下的分布式一致性问题。相信不了解这个问题的人心里已经开始骂了：刚才还说要明确问题，这你跟没说一样。
easy，且听我慢慢道来...
话说在世界的另一个地方存在一个叫做拜占庭的城市，有n个军队分散的驻扎在城市四周，每个军队都有一个最高指挥官-->将军，他们驻扎在这里的原因不是旅游，而是他们要进攻这个城市，由于该城市防守严密，必须大部分军队同时进攻才能攻占下来。每个军队都会首先观察敌情然后做出自己的判断，军队之间会通过信使来将自己的决定（进攻 or 撤退）通知到别的军队，但是总有一些将军会叛变，叛军会给别的军队发送不同的决定，比如他们向军队1发送进攻，但是向军队2却发送撤退的命令，这样可能会造成忠诚的将军执行了不同的命令。
上面的描述应该比较清晰了吧，但是！！！不够清晰，没有量化，比如：
1. 将军们依据何种原则决定进攻or撤退，并且保证达成一致的方案？
2. 叛变的将军是如何让不同的将军做出不同的决定的？
3. 如果确保进攻成功，叛军个数不能超过多少？
搞清楚了这些才算是理解了拜占庭将军真正需要解决的问题。
首先思考一下第一个问题：忠诚的将军如何达成一致？我们先假设一个叛军都没有，大家都是忠诚的，在观察地形、天气、星象之后，每个人都有自己的判断，有的将军觉得月黑风高，今日动手甚佳，有的将军认为天黑路滑还是早点歇息养精蓄锐的好，他们互相通知之后，发现大家意见不一，肿么办？当然是严格执行党的方针（玩个梗：去中心化牛逼，dao无敌，defi是未来...还是跟着党好），坚决贯彻四个服从原则之一：少数服从多数。每个将军都知道其他将军的决定，当大部分将军都决定进攻的话，即便最开始做出撤退决定的将军也需要执行进攻命令，通过这种方式将军达成一致意见。
这里潜在也表明了一个前置条件：叛军的个数不能超过半数，否则永远无法保证忠诚的将军能够达成一致。而论文的结论是将军总数为3m+1个的话，叛军的个数不能超过m个，对叛军的个数更加严苛。
但是如果存在叛军的话，上述方式有可能无法达成一致。比如总共9个军队，8个都是忠诚，1个是背叛的，忠诚的将军里面4个选择进攻，4个选择撤退，那个背叛的将军就很贼了，他给决定进攻的将军发送进攻的决定，给撤退的将军发送撤退的决定，造成的结果就是：进攻的将军发现有5个将军决定进攻，他们认为其他将军也会少数服从多数而进攻，于是他们便进攻了，同理决定撤退的将军都撤退了，一半撤退，一半去送，结果可想而知很凄惨。
小朋友们，如果你们遇到这种问题的话会怎么解决，自己先思考五分钟...
N个将军中哪怕只有一个背叛者都有可能给别的军队带来毁灭性的打击，如何避免这种悲剧发生，这便是“拜占庭将军”所需要解决的问题。突然间是不是很期待：哇这个问题好难啊，Leslie Lamport大神又是如何解决的呢，好想知道呢！是不是大家都背叛了，Leslie Lamport大神依然有办法解决呢？首先强调一点，论文明确说明：假设将军个数为3m+1的话，背叛的将军个数不能超过m个，否则谁都解决不了这个问题，想想也可以理解，假如所有将军都叛变了，哪还有什么真理，哪还有什么正义...
以上是对上述3个问题的描述，理解这些描述才算看懂了问题，下面开始简化问题。
简化并转换问题
总结一下，我们的目标是：忠诚的将军不会受到少数叛军的干扰，永远都会做出相同的决策。已知问题原因：忠诚的将军是因为叛军的存在而接收到了不同的信息集导致做出了不同的决策。假如我们有一种办法能够保证：忠诚的将军永远都能获取相同的信息集，那么就可以解决这个问题。（这也是论文提出的第一个条件A）
这时可能有人问了，就算通过某种手段使得忠诚的将军拿到了相同的信息集，假设信息集中有7个决定：3个忠诚将军的进攻决定，3个忠诚将军的撤退决定，1个背叛者的决定（可能是进攻也可能是撤退），这时6个忠诚的将军进攻与否都取决于这个背叛者，这太扯了。但是针对这个问题论文特意强调了：这种情况下无论进攻或者撤退，都算不上一个错误的决定，所以这种情况忽略。我们的目标只是要保证：忠诚的将军所做的决定是统一的即可。
那么问题就又回到刚才说的：如何保证忠诚的将军永远都能获取相同的信息集（论文中的条件1），如果能解决这个问题，也就解决了拜占庭将军问题。
背叛的将军会发送不同的信息给不同的将军，所以要保证忠诚的将军都能获取相同的数据集，那需要把获取信息的方式做一下修改：将军们不再直接采纳其余的将军发送过来的决定，而是采取另一种算法来获取，该算法要保证忠诚的将军收到的数据集是一致的。具体采用什么样的算法是我们下一步需要讨论的。
上述的加粗条件可以进一步转换成：针对第i个将军的决策v(i)，忠诚的将军永远收到相同的v(i)。注意：这里将军i有可能是忠诚的，也有可能是背叛的，但是不管怎样，必须要保证忠诚的将军采纳的v(i)是相同的。所以算法需要解决的一个关键问题：即使背叛者i发送了不同的决策，忠诚的将军依然能够识别并且确定一个唯一的v(i)。
所以算法最终可以简化成：不论将军i是忠诚的还是背叛的，保证忠诚的将军收到的v(i)都是一样的。
注意：到这里论文已经把问题简化成单个将军如何发送决策的问题，这个简化很关键，简化后只需要关注：单个将军发送决策后，其余的将军如何接收并采纳。
解决方案
再次强调一遍，下面我们始终关注的是：单个将军i发送决策vi，其余的忠诚的将军如何保证他们看到同一个vi。从之前关注（v1...vn）集合，我们简化成只关注某个vi。只要保证了忠诚将军采纳的每个vi（i可以是0-n）都是一致的，也就意味着他们的信息集是一致的。
再次描述问题：
假设将军总数为n，将军i此时需要将自己的决策发送给剩余n-1个将军，并且保证这n个将军中的所有的忠诚的将军采纳的vi值是一样的。
我们也将发送指令的将军称为commander，其余接收的将军称为lieutenant。
1.当commander为忠诚时，他会将一个唯一的vi（比如进攻）发送给其余的将军，忠诚的将军自然就采纳了同样的vi。所以本文重点关注commander为叛军时的情况，commander为忠诚的情况读者自行推导。
2.当commander为叛军时，他可能就开始乱发消息了，此时为了保证忠诚的将军采用相同的vi，论文提出了一个方法：不直接采纳commander发送过来的信息vi，而是收到vi后，同时询问别的将军：你们从commander那收到的都是啥信儿呀？
然后这个将军把所有将军收到的commander决策做一下汇总，看看是进攻的票数多，还是撤退的票数多，遵从少数服从多数原则，确定一个唯一的vi。
当然上面的说法不是很严谨，而且缺失了前置条件，论文规定：
假如将军总数为n，叛军总数为m，必须满足 n>=3m+1，才能保证上面的方法能正常工作。
为了解释这个问题，论文采用了反证法，我们直接贴出论文中的图例来说明：
这里commander是叛军，其余的两个lieutenant是忠诚的，lieutenant1收到commander给的attack命令，但是询问lieutenant2后，发现commander给lieutenant2发送的是retreat命令，这时lieutenant1就有点懵逼了，只有两票，到底是进攻还是撤退，无法判断。（论文说了这个反证只是一个特别粗浅、不太严谨的证明，但是结论是正确的，如果对该证明有兴趣，可以自动阅读论文）
当将军个数增加为4，commander是叛军，此时满足n>=3m+1，上述的方法就可行了，如图：
从图中可以看到lieutenant通过询问别的lieutenant，最终会得到一个一致的指令集（commander分发出去的指令），本例中集合大小为3，能够保证可以从指令集得出一个统一的结论。本例中的指令集attack占多数，所以lieutenant都会统一将attack作为commander的指令。
注：commander是叛军，我们的目标是要保证忠诚的将军采纳同样的决策，具体是进攻还是撤退其实无所谓。
从集合中得出一个确定的值可以采用不同的方式，比如（1，2，3，4，5）这种集合，我们可以取中位数3，（attack，attack，attack，attack，retreat）这种的枚举集合我们可以取attack，我们将决策的方法称为Major函数，Major函数可以根据具体的业务来设计，本例中因为只有进攻、撤退两个枚举类型，Major函数即采取多数原则取attack.
我的理解：既然叛军会乱发消息，以单个将军的角度来看确实看到的消息不一样，但是如果将叛军发送的所有消息看做一个整体，那不就是一个一致的数据集了嘛，然后通过“major函数”从数据集中确定一个唯一的值，这便是解决问题的思路。
上述是将军个数最小（4个）情况下的demo，下面我们思考一下：如果是7个将军，里面存在2个叛军，上面的方式是不是依然可行？
7个将军
图中可以看出，lieutenant1可以选出来一个major()=1，但是lieutenant5无法确定一个major，1和0的个数是一样的。当存在两个叛军的时候，lieutenant们私下只转发一次的方式就行不通了。lieutenant1和5都是忠诚的将军，但是他们所看到的指令集是不一样的，这个跟我们刚才一直强调的原则所违背。
所以描述4个将军时的解决方案是一个阉割版的，真正的解决方法是一个递归的算法。
算法定义
首先假设总共n个将军，存在m个叛军，定义一个OM(m)算法：
step 1. commander将他的指令发送给其余的lieutenant
step 2. 对于每个将军i，将军i分别将commander发送过来的指令作为vi，然后将军i将自己作为commander，将vi发送给剩余的n-2个lieutenant（除了自己和之前的commander），再次执行OM(m-1)算法。
step 3. 对于每个将军i，都会从将军j处获取vj（j != i），将军j的vj同样也是通过OM(m-1)算法得出的，最后将军i将获得的集合（v1.....vn-1）执行major函数得到一个最终的值。
因为这是一个递归的函数，需要定义一下边界条件，当m=0时，OM(0)的步骤；
step 1. commander将他的指令发送给其余的lieutenant
step 2. lieutenant直接采纳从commander处获取的指令
如果到这里读者看累的话，那也可以不用再看了，这个算法本身就比较抽象，从描述里面可以看出存在m个叛军时，算法需要进行(n-1)(n-2)...(n-m-1)次消息传递，所以算法的证明采用了数学归纳法，而且这个算法的效率明显很低，复杂度随着将军和叛军个数的增加呈指数级增长。
笔者没有研究过拜占庭算法的其他变种，但是据我猜想其他变种应该是针对某些方面做了针对性的优化，算法的本质是不会变的，如果不从事相关工作的话，只是想了解这个算法大致的流程，到这里应该就够了，大家只要知道这个算法性能很差就行了。再见朋友们...
选择性阅读
下面我们翻译一下算法的证明，有兴趣的同学可以看看，为了证明OM(m)算法的正确性，我们先证明一个前置定理：
定理1：对于任意的m和k，假如将军总数大于n>2k+m，叛军总数不超过k，算法OM(m)能够保证commander为忠诚时，其余忠诚的lieutenant遵从他的指令。
定理1证明：这里的条件是commander是忠诚的，显而易见OM(0)肯定满足条件，现在我们假设m-1是正确的，然后推导出m也是正确的即可（数学归纳法）。
假设将军总数为n-1时算法OM(m-1)成立，在OM(m-1)中每个忠诚将军都会收到别的忠诚的将军正确的信息vj， 而且从n-1 > 2k+(m-1) > 2k可以看出，OM(m-1)算法保证了n-1个将军中超过半数将军是忠诚的并且收到正确的决策，所以在OM(n)中当commander为忠诚时，n个将军里面超过半数也是忠诚的，并且能够通过major函数采取统一的决策，可以保证定理1正确（怕不怕，其实我自己都没看懂）。
只是证明定理1是不够的，还需要证明：
定理2：对于任意m，如果将军总数超过3m，叛军总数不超过m，算法OM(m)满足忠诚的lieutenant都能遵从相同的指令。
证明：如果没有叛军m=0的时候，很明显可以看到定理2满足，也就是说m=0时成立。另外我们再假设commander是忠诚的，并且让k=m，此时就是定理1的一个特例，也满足条件。
那我们只需要关注commander是叛军时的情况，我们先假设m-1时成立，验证m是否成立。
定理2规定最多有m个叛军，并且commander是其中的一个，所以最多有m-1个lieutenant是叛军，又因为lieutenant总数超过3m-1个，同时3m-1 > 3(m-1)。
假如OM(m-1)成立的话，总数为3(m-1)个将军中超过半数lieutenant忠诚且决策统一，OM(m)中我们假定commander是新增的那个叛军，所以其余的3m-1个将军中必定可以保证超过半数将军忠诚，同样也可以看出OM(m)也成立（讲道理我看的也有点懵，多思考一会估计也能想明白，数学归纳法就是比较抽象）。
这就前后呼应了，将军总数n>=3m+1，叛军不超过m时，拜占庭将军问题才有解，解决的方式就是通过递归执行OM()算法。
总结
选读部分我自己理解的也不是特别深刻，只是隐约的感觉OM(m-1)成立的话，保证了半数将军忠诚且信息一致，从而证明了OM(m)也成立，感兴趣的读者还是推荐阅读论文，自己思考证明过程可能更靠谱，本文只是一个引子，给想了解拜占庭将军问题，却不知如何下手的朋友带个路。
上述篇幅只涉及到了论文中的A SOLUTION WITH ORAL MESSAGES这一种情况，论文后面还有扩展了两种情况：
1. A SOLUTION WITH SIGNED MESSAGES----消息带签名的拜占庭问题解决方案
2. MISSING COMMUNICATION PATHS----部分节点无法直接通信时的解决方案
这些情况在现实中都是有实实在在的场景的，有兴趣的读者可自行阅读（因为笔者自己没看，所以就没写^ ^），欢迎大家讨论交流。
vx：q329853099
网友评论