關(guān)鍵字：拜占庭牲迫、分布式一致性豌汇、不可信網(wǎng)絡(luò)

預(yù)估閱讀時長：20分鐘

相比之前閱讀的論文验游，拜占庭將軍問題花費了我更長的時間充岛，在閱讀的過程中我在思考：為什么我會讀的這么慢？相信肯定有小伙伴在閱讀論文的時候跟我一樣一樣的耕蝉，也就只有兩點看不懂崔梗，這個也看不懂，那個也看不懂.....

針對這個問題我仔細(xì)想了一下原因：因為我之前并沒有這種不可信環(huán)境下的分布式一致性的經(jīng)驗垒在，平時的工作也接觸不到這類問題炒俱，也就是說：我壓根就沒有理解論文要解決什么問題俊抵。我覺得這點很關(guān)鍵寸士，一臉懵逼的為了讀論文而讀，越看不懂越著急陨享，急眼了為了安慰自己還非得硬著頭皮往下看推盛，結(jié)果還是一臉懵逼峦阁。

所以我認(rèn)為閱讀論文有一個關(guān)鍵點：首先一定要弄清楚作者所解決的問題到底是什么，為什么會存在這個問題耘成？了解清楚問題之后，再思考一下如果這個問題讓你來解決嘹朗，你會怎么辦？帶著清晰的疑問去閱讀論文的話會好一點诵肛。

何為拜占庭將軍問題

好屹培，下面我們步入正題：什么是拜占庭將軍問題？

拜占庭將軍問題也是由分布式理論大佬Leslie Lamport提出的（再次膜拜一下老人家怔檩，這人有點頂）褪秀，目的是為了解決不可信環(huán)境下的分布式一致性問題。相信不了解這個問題的人心里已經(jīng)開始罵了：剛才還說要明確問題薛训，這你跟沒說一樣媒吗。

easy，且聽我慢慢道來...

話說在世界的另一個地方存在一個叫做拜占庭的城市乙埃，有n個軍隊分散的駐扎在城市四周介袜，每個軍隊都有一個最高指揮官-->將軍自阱，他們駐扎在這里的原因不是旅游，而是他們要進(jìn)攻這個城市米酬，由于該城市防守嚴(yán)密沛豌，必須大部分軍隊同時進(jìn)攻才能攻占下來。每個軍隊都會首先觀察敵情然后做出自己的判斷跳芳，軍隊之間會通過信使來將自己的決定（進(jìn)攻 or 撤退）通知到別的軍隊芍锦，但是總有一些將軍會叛變，叛軍會給別的軍隊發(fā)送不同的決定飞盆，比如他們向軍隊1發(fā)送進(jìn)攻娄琉，但是向軍隊2卻發(fā)送撤退的命令，這樣可能會造成忠誠的將軍執(zhí)行了不同的命令吓歇。

上面的描述應(yīng)該比較清晰了吧孽水，但是！３强础女气！不夠清晰，沒有量化测柠，比如：

1. 將軍們依據(jù)何種原則決定進(jìn)攻or撤退炼鞠，并且保證達(dá)成一致的方案缘滥？

2. 叛變的將軍是如何讓不同的將軍做出不同的決定的？

3. 如果確保進(jìn)攻成功谒主，叛軍個數(shù)不能超過多少朝扼？

搞清楚了這些才算是理解了拜占庭將軍真正需要解決的問題。

首先思考一下第一個問題：忠誠的將軍如何達(dá)成一致霎肯？我們先假設(shè)一個叛軍都沒有擎颖，大家都是忠誠的，在觀察地形姿现、天氣肠仪、星象之后肖抱，每個人都有自己的判斷备典，有的將軍覺得月黑風(fēng)高，今日動手甚佳意述，有的將軍認(rèn)為天黑路滑還是早點歇息養(yǎng)精蓄銳的好提佣，他們互相通知之后，發(fā)現(xiàn)大家意見不一荤崇，腫么辦拌屏？當(dāng)然是嚴(yán)格執(zhí)行黨的方針（玩?zhèn)€梗：去中心化牛逼，dao無敵术荤，defi是未來...還是跟著黨好）倚喂，堅決貫徹四個服從原則之一：少數(shù)服從多數(shù)。每個將軍都知道其他將軍的決定瓣戚，當(dāng)大部分將軍都決定進(jìn)攻的話端圈，即便最開始做出撤退決定的將軍也需要執(zhí)行進(jìn)攻命令，通過這種方式將軍達(dá)成一致意見子库。

這里潛在也表明了一個前置條件：叛軍的個數(shù)不能超過半數(shù)舱权，否則永遠(yuǎn)無法保證忠誠的將軍能夠達(dá)成一致。而論文的結(jié)論是將軍總數(shù)為3m+1個的話仑嗅，叛軍的個數(shù)不能超過m個宴倍，對叛軍的個數(shù)更加嚴(yán)苛。

但是如果存在叛軍的話仓技，上述方式有可能無法達(dá)成一致鸵贬。比如總共9個軍隊，8個都是忠誠脖捻，1個是背叛的恭理，忠誠的將軍里面4個選擇進(jìn)攻，4個選擇撤退郭变，那個背叛的將軍就很賊了颜价，他給決定進(jìn)攻的將軍發(fā)送進(jìn)攻的決定涯保，給撤退的將軍發(fā)送撤退的決定，造成的結(jié)果就是：進(jìn)攻的將軍發(fā)現(xiàn)有5個將軍決定進(jìn)攻周伦，他們認(rèn)為其他將軍也會少數(shù)服從多數(shù)而進(jìn)攻夕春，于是他們便進(jìn)攻了，同理決定撤退的將軍都撤退了专挪，一半撤退及志，一半去送，結(jié)果可想而知很凄慘寨腔。

小朋友們速侈，如果你們遇到這種問題的話會怎么解決，自己先思考五分鐘...

N個將軍中哪怕只有一個背叛者都有可能給別的軍隊帶來毀滅性的打擊迫卢，如何避免這種悲劇發(fā)生倚搬，這便是“拜占庭將軍”所需要解決的問題。突然間是不是很期待：哇這個問題好難啊乾蛤，Leslie Lamport大神又是如何解決的呢每界，好想知道呢！是不是大家都背叛了家卖，Leslie Lamport大神依然有辦法解決呢眨层？首先強(qiáng)調(diào)一點，論文明確說明：假設(shè)將軍個數(shù)為3m+1的話上荡，背叛的將軍個數(shù)不能超過m個趴樱，否則誰都解決不了這個問題，想想也可以理解酪捡，假如所有將軍都叛變了叁征，哪還有什么真理，哪還有什么正義...

以上是對上述3個問題的描述沛善，理解這些描述才算看懂了問題航揉，下面開始簡化問題。

簡化并轉(zhuǎn)換問題

總結(jié)一下金刁，我們的目標(biāo)是：忠誠的將軍不會受到少數(shù)叛軍的干擾帅涂，永遠(yuǎn)都會做出相同的決策。已知問題原因：忠誠的將軍是因為叛軍的存在而接收到了不同的信息集導(dǎo)致做出了不同的決策尤蛮。假如我們有一種辦法能夠保證：忠誠的將軍永遠(yuǎn)都能獲取相同的信息集媳友，那么就可以解決這個問題。（這也是論文提出的第一個條件A）

這時可能有人問了产捞，就算通過某種手段使得忠誠的將軍拿到了相同的信息集醇锚，假設(shè)信息集中有7個決定：3個忠誠將軍的進(jìn)攻決定，3個忠誠將軍的撤退決定，1個背叛者的決定（可能是進(jìn)攻也可能是撤退）焊唬，這時6個忠誠的將軍進(jìn)攻與否都取決于這個背叛者恋昼，這太扯了。但是針對這個問題論文特意強(qiáng)調(diào)了：這種情況下無論進(jìn)攻或者撤退赶促，都算不上一個錯誤的決定液肌，所以這種情況忽略。我們的目標(biāo)只是要保證：忠誠的將軍所做的決定是統(tǒng)一的即可鸥滨。

那么問題就又回到剛才說的：如何保證忠誠的將軍永遠(yuǎn)都能獲取相同的信息集（論文中的條件1）嗦哆，如果能解決這個問題，也就解決了拜占庭將軍問題婿滓。

背叛的將軍會發(fā)送不同的信息給不同的將軍老速，所以要保證忠誠的將軍都能獲取相同的數(shù)據(jù)集，那需要把獲取信息的方式做一下修改：將軍們不再直接采納其余的將軍發(fā)送過來的決定凸主，而是采取另一種算法來獲取橘券，該算法要保證忠誠的將軍收到的數(shù)據(jù)集是一致的。具體采用什么樣的算法是我們下一步需要討論的秕铛。

上述的加粗條件可以進(jìn)一步轉(zhuǎn)換成：針對第i個將軍的決策v(i)约郁，忠誠的將軍永遠(yuǎn)收到相同的v(i)缩挑。注意：這里將軍i有可能是忠誠的但两，也有可能是背叛的，但是不管怎樣供置，必須要保證忠誠的將軍采納的v(i)是相同的谨湘。所以算法需要解決的一個關(guān)鍵問題：即使背叛者i發(fā)送了不同的決策，忠誠的將軍依然能夠識別并且確定一個唯一的v(i)芥丧。

所以算法最終可以簡化成：不論將軍i是忠誠的還是背叛的紧阔，保證忠誠的將軍收到的v(i)都是一樣的。

注意：到這里論文已經(jīng)把問題簡化成單個將軍如何發(fā)送決策的問題续担，這個簡化很關(guān)鍵擅耽，簡化后只需要關(guān)注：單個將軍發(fā)送決策后，其余的將軍如何接收并采納物遇。

解決方案

再次強(qiáng)調(diào)一遍乖仇，下面我們始終關(guān)注的是：單個將軍i發(fā)送決策vi，其余的忠誠的將軍如何保證他們看到同一個vi询兴。從之前關(guān)注（v1...vn）集合乃沙，我們簡化成只關(guān)注某個vi。只要保證了忠誠將軍采納的每個vi（i可以是0-n）都是一致的诗舰，也就意味著他們的信息集是一致的警儒。

再次描述問題：

假設(shè)將軍總數(shù)為n，將軍i此時需要將自己的決策發(fā)送給剩余n-1個將軍眶根，并且保證這n個將軍中的所有的忠誠的將軍采納的vi值是一樣的蜀铲。

我們也將發(fā)送指令的將軍稱為commander边琉，其余接收的將軍稱為lieutenant。

1.當(dāng)commander為忠誠時记劝，他會將一個唯一的vi（比如進(jìn)攻）發(fā)送給其余的將軍艺骂，忠誠的將軍自然就采納了同樣的vi。所以本文重點關(guān)注commander為叛軍時的情況隆夯，commander為忠誠的情況讀者自行推導(dǎo)钳恕。

2.當(dāng)commander為叛軍時，他可能就開始亂發(fā)消息了蹄衷，此時為了保證忠誠的將軍采用相同的vi忧额，論文提出了一個方法：不直接采納commander發(fā)送過來的信息vi，而是收到vi后愧口，同時詢問別的將軍：你們從commander那收到的都是啥信兒呀睦番？

然后這個將軍把所有將軍收到的commander決策做一下匯總，看看是進(jìn)攻的票數(shù)多耍属，還是撤退的票數(shù)多托嚣，遵從少數(shù)服從多數(shù)原則，確定一個唯一的vi厚骗。

當(dāng)然上面的說法不是很嚴(yán)謹(jǐn)示启，而且缺失了前置條件，論文規(guī)定：

假如將軍總數(shù)為n领舰，叛軍總數(shù)為m夫嗓，必須滿足 n>=3m+1冲秽，才能保證上面的方法能正常工作锉桑。

為了解釋這個問題民轴，論文采用了反證法杉武，我們直接貼出論文中的圖例來說明：

這里commander是叛軍轻抱，其余的兩個lieutenant是忠誠的，lieutenant1收到commander給的attack命令士八，但是詢問lieutenant2后婚度，發(fā)現(xiàn)commander給lieutenant2發(fā)送的是retreat命令官卡，這時lieutenant1就有點懵逼了寻咒，只有兩票毛秘，到底是進(jìn)攻還是撤退叫挟，無法判斷抹恳。（論文說了這個反證只是一個特別粗淺适秩、不太嚴(yán)謹(jǐn)?shù)淖C明秽荞，但是結(jié)論是正確的，如果對該證明有興趣钦听，可以自動閱讀論文）

當(dāng)將軍個數(shù)增加為4朴上，commander是叛軍痪宰，此時滿足n>=3m+1衣撬，上述的方法就可行了，如圖：

從圖中可以看到lieutenant通過詢問別的lieutenant乍构，最終會得到一個一致的指令集（commander分發(fā)出去的指令）扛点，本例中集合大小為3，能夠保證可以從指令集得出一個統(tǒng)一的結(jié)論昔善。本例中的指令集attack占多數(shù)畔乙，所以lieutenant都會統(tǒng)一將attack作為commander的指令牲距。

注：commander是叛軍，我們的目標(biāo)是要保證忠誠的將軍采納同樣的決策咖摹，具體是進(jìn)攻還是撤退其實無所謂萤晴。

從集合中得出一個確定的值可以采用不同的方式店读，比如（1，2殖演，3趴久，4彼棍，5）這種集合滥酥，我們可以取中位數(shù)3缆蝉，（attack刊头，attack原杂，attack穿肄，attack咸产，retreat）這種的枚舉集合我們可以取attack，我們將決策的方法稱為Major函數(shù)屑彻，Major函數(shù)可以根據(jù)具體的業(yè)務(wù)來設(shè)計，本例中因為只有進(jìn)攻膳沽、撤退兩個枚舉類型，Major函數(shù)即采取多數(shù)原則取attack.

我的理解：既然叛軍會亂發(fā)消息巡揍，以單個將軍的角度來看確實看到的消息不一樣阱当，但是如果將叛軍發(fā)送的所有消息看做一個整體，那不就是一個一致的數(shù)據(jù)集了嘛油坝，然后通過“major函數(shù)”從數(shù)據(jù)集中確定一個唯一的值澈圈，這便是解決問題的思路。

上述是將軍個數(shù)最蟹掏怠（4個）情況下的demo，下面我們思考一下：如果是7個將軍，里面存在2個叛軍洋闽，上面的方式是不是依然可行诫舅？

7個將軍

圖中可以看出娃闲，lieutenant1可以選出來一個major()=1卷哩，但是lieutenant5無法確定一個major冷溶，1和0的個數(shù)是一樣的。當(dāng)存在兩個叛軍的時候苗胀，lieutenant們私下只轉(zhuǎn)發(fā)一次的方式就行不通了谷丸。lieutenant1和5都是忠誠的將軍刨疼，但是他們所看到的指令集是不一樣的亭畜，這個跟我們剛才一直強(qiáng)調(diào)的原則所違背蜗搔。

所以描述4個將軍時的解決方案是一個閹割版的聘芜，真正的解決方法是一個遞歸的算法。

算法定義

首先假設(shè)總共n個將軍，存在m個叛軍，定義一個OM(m)算法：

step 1. commander將他的指令發(fā)送給其余的lieutenant

step 2. 對于每個將軍i仗哨，將軍i分別將commander發(fā)送過來的指令作為vi斟珊，然后將軍i將自己作為commander旨椒，將vi發(fā)送給剩余的n-2個lieutenant（除了自己和之前的commander）勤庐，再次執(zhí)行OM(m-1)算法。

step 3. 對于每個將軍i愉镰，都會從將軍j處獲取vj（j != i）米罚，將軍j的vj同樣也是通過OM(m-1)算法得出的，最后將軍i將獲得的集合（v1.....vn-1）執(zhí)行major函數(shù)得到一個最終的值丈探。

因為這是一個遞歸的函數(shù)录择，需要定義一下邊界條件，當(dāng)m=0時碗降，OM(0)的步驟隘竭；

step 1.?commander將他的指令發(fā)送給其余的lieutenant

step 2.?lieutenant直接采納從commander處獲取的指令

如果到這里讀者看累的話，那也可以不用再看了遗锣，這個算法本身就比較抽象货裹，從描述里面可以看出存在m個叛軍時，算法需要進(jìn)行(n-1)(n-2)...(n-m-1)次消息傳遞精偿，所以算法的證明采用了數(shù)學(xué)歸納法弧圆，而且這個算法的效率明顯很低，復(fù)雜度隨著將軍和叛軍個數(shù)的增加呈指數(shù)級增長笔咽。

筆者沒有研究過拜占庭算法的其他變種搔预，但是據(jù)我猜想其他變種應(yīng)該是針對某些方面做了針對性的優(yōu)化，算法的本質(zhì)是不會變的叶组，如果不從事相關(guān)工作的話拯田，只是想了解這個算法大致的流程，到這里應(yīng)該就夠了甩十，大家只要知道這個算法性能很差就行了船庇。再見朋友們...

選擇性閱讀

下面我們翻譯一下算法的證明吭产，有興趣的同學(xué)可以看看，為了證明OM(m)算法的正確性鸭轮，我們先證明一個前置定理：

定理1：對于任意的m和k臣淤，假如將軍總數(shù)大于n>2k+m，叛軍總數(shù)不超過k窃爷，算法OM(m)能夠保證commander為忠誠時邑蒋，其余忠誠的lieutenant遵從他的指令。

定理1證明：這里的條件是commander是忠誠的按厘，顯而易見OM(0)肯定滿足條件医吊，現(xiàn)在我們假設(shè)m-1是正確的，然后推導(dǎo)出m也是正確的即可（數(shù)學(xué)歸納法）逮京。

假設(shè)將軍總數(shù)為n-1時算法OM(m-1)成立卿堂，在OM(m-1)中每個忠誠將軍都會收到別的忠誠的將軍正確的信息vj，?而且從n-1 > 2k+(m-1) > 2k可以看出造虏，OM(m-1)算法保證了n-1個將軍中超過半數(shù)將軍是忠誠的并且收到正確的決策御吞，所以在OM(n)中當(dāng)commander為忠誠時，n個將軍里面超過半數(shù)也是忠誠的漓藕，并且能夠通過major函數(shù)采取統(tǒng)一的決策陶珠，可以保證定理1正確（怕不怕，其實我自己都沒看懂）享钞。

只是證明定理1是不夠的揍诽，還需要證明：

定理2：對于任意m，如果將軍總數(shù)超過3m栗竖，叛軍總數(shù)不超過m暑脆，算法OM(m)滿足忠誠的lieutenant都能遵從相同的指令。

證明：如果沒有叛軍m=0的時候狐肢，很明顯可以看到定理2滿足添吗，也就是說m=0時成立。另外我們再假設(shè)commander是忠誠的份名，并且讓k=m碟联，此時就是定理1的一個特例，也滿足條件僵腺。

那我們只需要關(guān)注commander是叛軍時的情況鲤孵，我們先假設(shè)m-1時成立，驗證m是否成立辰如。

定理2規(guī)定最多有m個叛軍普监，并且commander是其中的一個，所以最多有m-1個lieutenant是叛軍，又因為lieutenant總數(shù)超過3m-1個凯正，同時3m-1 > 3(m-1)毙玻。

假如OM(m-1)成立的話，總數(shù)為3(m-1)個將軍中超過半數(shù)lieutenant忠誠且決策統(tǒng)一漆际，OM(m)中我們假定commander是新增的那個叛軍淆珊，所以其余的3m-1個將軍中必定可以保證超過半數(shù)將軍忠誠夺饲，同樣也可以看出OM(m)也成立（講道理我看的也有點懵奸汇，多思考一會估計也能想明白，數(shù)學(xué)歸納法就是比較抽象）往声。

這就前后呼應(yīng)了擂找，將軍總數(shù)n>=3m+1，叛軍不超過m時浩销，拜占庭將軍問題才有解贯涎，解決的方式就是通過遞歸執(zhí)行OM()算法。

總結(jié)

選讀部分我自己理解的也不是特別深刻慢洋，只是隱約的感覺OM(m-1)成立的話塘雳，保證了半數(shù)將軍忠誠且信息一致，從而證明了OM(m)也成立普筹，感興趣的讀者還是推薦閱讀論文败明，自己思考證明過程可能更靠譜，本文只是一個引子太防，給想了解拜占庭將軍問題妻顶，卻不知如何下手的朋友帶個路。

上述篇幅只涉及到了論文中的A SOLUTION WITH ORAL MESSAGES這一種情況蜒车，論文后面還有擴(kuò)展了兩種情況：

1. A SOLUTION WITH SIGNED MESSAGES----消息帶簽名的拜占庭問題解決方案

2.?MISSING COMMUNICATION PATHS----部分節(jié)點無法直接通信時的解決方案

這些情況在現(xiàn)實中都是有實實在在的場景的讳嘱，有興趣的讀者可自行閱讀（因為筆者自己沒看，所以就沒寫^ ^）酿愧，歡迎大家討論交流沥潭。

vx：q329853099