这怕是我看过的最好的关于 “ 拜占庭将军问题 ” 的文章
雖然在之前的博客中，我也有寫過類似的，拜占庭將軍問題。但是，個人認(rèn)為這是我看過介紹的最好的。推薦給你們！
拜占庭將軍問題(The Byzantine Generals Problem)提供了對分布式共識問題的一種情景化描述，由Leslie Lamport等人在1982年首次發(fā)表。論文《The Byzantine Generals Problem 》同時提供了兩種解決拜占庭將軍問題的算法：
?
-
口信消息型解決方案(A solution with oral message);
-
簽名消息型解決方案(A solution with signed message).
?
論文：
https://www-inst.eecs.berkeley.edu/~cs162/sp16/static/readings/Original_Byzantine.pdf
?
本文之后將詳細(xì)講述這兩種算法。事實上，拜占庭將軍問題是分布式系統(tǒng)領(lǐng)域最復(fù)雜的容錯模型，?它描述了如何在存在惡意行為(如消息篡改或偽造)的情況下使分布式系統(tǒng)達(dá)成一致。是我們理解分布式一致性協(xié)議和算法的重要基礎(chǔ)。
?
?
拜占庭將軍問題描述
?
拜占庭將軍問題描述了這樣一個場景：
?
圖1. 拜占庭將軍問題
?
拜占庭帝國(Byzantine Empire)軍隊的幾個師駐扎在敵城外，每個師都由各自的將軍指揮。將軍們只能通過信使相互溝通。在觀察敵情之后，他們必須制定一個共同的行動計劃，如進(jìn)攻(Attack)或者撤退(Retreat)，且只有當(dāng)半數(shù)以上的將軍共同發(fā)起進(jìn)攻時才能取得勝利。然而, 其中一些將軍可能是叛徒，試圖阻止忠誠的將軍達(dá)成一致的行動計劃。?更糟糕的是，負(fù)責(zé)消息傳遞的信使也可能是叛徒，他們可能篡改或偽造消息，也可能使得消息丟失。
?
為了更加深入的理解拜占庭將軍問題，我們以三將軍問題為例進(jìn)行說明。當(dāng)三個將軍都忠誠時，可以通過投票確定一致的行動方案，圖2展示了一種場景，?即General A，B通過觀察敵軍軍情并結(jié)合自身情況判斷可以發(fā)起攻擊，而General C通過觀察敵軍軍情并結(jié)合自身情況判斷應(yīng)當(dāng)撤退。?最終三個將軍經(jīng)過投票表決得到結(jié)果為進(jìn)攻：撤退=2:1，?所以將一同發(fā)起進(jìn)攻取得勝利。對于三個將軍，每個將軍都能執(zhí)行兩種決策(進(jìn)攻或撤退)的情況下, 共存在6中不同的場景，圖2是其中一種，對于其他5中場景可簡單地推得，通過投票三個將軍都將達(dá)成一致的行動計劃。
?
圖2. 三個將軍均為忠誠的場景
?
當(dāng)三個將軍中存在一個叛徒時，將可能擾亂正常的作戰(zhàn)計劃。圖3展示了General C為叛徒的一種場景，他給General A和General B發(fā)送了不同的消息，在這種場景下General A通過投票得到進(jìn)攻：撤退=1:2，最終將作出撤退的行動計劃；General B通過投票得到進(jìn)攻：撤退=2:1，最終將作出進(jìn)攻的行動計劃。結(jié)果只有General B發(fā)起了進(jìn)攻并戰(zhàn)敗。
?
圖3. 二忠一叛的場景
?
事實上，對于三個將軍中存在一個叛徒的場景，想要總能達(dá)到一致的行動方案是不可能的。詳細(xì)的證明可參看Leslie Lamport的論文。此外，論文中給出了一個更加普適的結(jié)論：如果存在m個叛將，那么至少需要3m+1個將軍，才能最終達(dá)到一致的行動方案。
?
?
解決方案
?
Leslie Lamport在論文中給出了兩種拜占庭將軍問題的解決方案，即口信消息型解決方案(A solution with oral message)和簽名消息型解決方案(A solution with signed message)。
?
1、口信消息型解決方案
?
首先, 對于口信消息(Oral message)的定義如下：
?
-
A1. 任何已經(jīng)發(fā)送的消息都將被正確傳達(dá);
-
A2. 消息的接收者知道是誰發(fā)送了消息;
-
A3. 消息的缺席可以被檢測。
?
基于口信消息的定義，我們可以知，?口信消息不能被篡改但是可以被偽造。基于對圖3場景的推導(dǎo)，我們知道存在一個叛將時，必須再增加3個忠將才能達(dá)到最終的行動一致。為加深理解，我們將利用3個忠將1個叛將的場景對口信消息型解決方案進(jìn)行推導(dǎo)。在口信消息型解決方案中，首先發(fā)送消息的將軍稱為指揮官，其余將軍稱為副官。對于3忠1叛的場景需要進(jìn)行兩輪作戰(zhàn)信息協(xié)商，如果沒有收到作戰(zhàn)信息那么默認(rèn)撤退。圖4是指揮官為忠將的場景，在第一輪作戰(zhàn)信息協(xié)商中，指揮官向3位副官發(fā)送了進(jìn)攻的消息；在第二輪中，三位副官再次進(jìn)行作戰(zhàn)信息協(xié)商，由于General A、B為忠將，因此他們根據(jù)指揮官的消息向另外兩位副官發(fā)送了進(jìn)攻的消息，而General C為叛將，為了擾亂作戰(zhàn)計劃，他向另外兩位副官發(fā)送了撤退的消息。最終Commanding General, General A和B達(dá)成了一致的進(jìn)攻計劃，可以取得勝利。
?
圖4. 指揮官為忠將的場景
?
圖5是指揮官為叛將的場景，在第一輪作戰(zhàn)信息協(xié)商中，指揮官向General A、B發(fā)送了撤退的消息，但是為了擾亂General C的決定向其發(fā)送了進(jìn)攻的消息。在第二輪中，由于所有副官均為忠將，因此都將來自指揮官的消息正確地發(fā)送給其余兩位副官。最終所有忠將都能達(dá)成一致撤退的計劃。
?
圖5. 指揮官為叛將的場景
?
如上所述，對于口信消息型拜占庭將軍問題，如果叛將人數(shù)為m，將軍人數(shù)不少于3m+1，那么最終能達(dá)成一致的行動計劃。值的注意的是，在這個算法中，叛將人數(shù)m是已知的，且叛將人數(shù)m決定了遞歸的次數(shù)，即叛將數(shù)m決定了進(jìn)行作戰(zhàn)信息協(xié)商的輪數(shù)，如果存在m個叛將，則需要進(jìn)行m+1輪作戰(zhàn)信息協(xié)商。這也是上述存在1個叛將時需要進(jìn)行兩輪作戰(zhàn)信息協(xié)商的原因。
?
2、簽名消息型解決方案
?
同樣，對簽名消息的定義是在口信消息定義的基礎(chǔ)上增加了如下兩條：
?
-
A4. 忠誠將軍的簽名無法偽造，而且對他簽名消息的內(nèi)容進(jìn)行任何更改都會被發(fā)現(xiàn)；
-
A5. 任何人都能驗證將軍簽名的真?zhèn)巍?/p>
?
基于簽名消息的定義，我們可以知道，簽名消息無法被偽造或者篡改。為了深入理解簽名消息型解決方案，我們同樣以3三將軍問題為例進(jìn)行推導(dǎo)。?圖6是忠將率先發(fā)起作戰(zhàn)協(xié)商的場景，General A率先向General B、C發(fā)送了進(jìn)攻消息，一旦叛將General C篡改了來自General A的消息，那么General B將將發(fā)現(xiàn)作戰(zhàn)信息被General C篡改，General B將執(zhí)行General A發(fā)送的消息。
?
圖6. 忠將率先發(fā)起作戰(zhàn)協(xié)商
?
圖7是叛將率先發(fā)起作戰(zhàn)協(xié)商的場景，叛將General C率先發(fā)送了誤導(dǎo)的作戰(zhàn)信息，那么General A、B將發(fā)現(xiàn)General C發(fā)送的作戰(zhàn)信息不一致，因此判定其為叛將。可對其進(jìn)行處理后再進(jìn)行作戰(zhàn)信息協(xié)商。
?
圖7. 叛將率先發(fā)起作戰(zhàn)協(xié)商
?
簽名消息型解決方案可以處理任何數(shù)量叛將的場景。
?
?
總 結(jié)
?
在分布式系統(tǒng)領(lǐng)域, 拜占庭將軍問題中的角色與計算機(jī)世界的對應(yīng)關(guān)系如下:
?
-
將軍, 對應(yīng)計算機(jī)節(jié)點；
-
忠誠的將軍, 對應(yīng)運(yùn)行良好的計算機(jī)節(jié)點；
-
叛變的將軍, 被非法控制的計算機(jī)節(jié)點；
-
信使被殺, 通信故障使得消息丟失；
-
信使被間諜替換, 通信被攻擊, 攻擊者篡改或偽造信息。
?
如上文所述，拜占庭將軍問題提供了對分布式共識問題的一種情景化描述，是分布式系統(tǒng)領(lǐng)域最復(fù)雜的模型。此外, 它也為我們理解和分類現(xiàn)有的眾多分布式一致性協(xié)議和算法提供了框架。現(xiàn)有的分布式一致性協(xié)議和算法主要可分為兩類：
?
一類是故障容錯算法(Crash Fault Tolerance, CFT)，?即非拜占庭容錯算法，解決的是分布式系統(tǒng)中存在故障，但不存在惡意攻擊的場景下的共識問題。也就是說，在該場景下可能存在消息丟失，消息重復(fù)，但不存在消息被篡改或偽造的場景。一般用于局域網(wǎng)場景下的分布式系統(tǒng)，如分布式數(shù)據(jù)庫。屬于此類的常見算法有Paxos算法、Raft算法,、ZAB協(xié)議等。
?
一類是拜占庭容錯算法，可以解決分布式系統(tǒng)中既存在故障，又存在惡意攻擊場景下的共識問題。一般用于互聯(lián)網(wǎng)場景下的分布式系統(tǒng)，如在數(shù)字貨幣的區(qū)塊鏈技術(shù)中。屬于此類的常見算法有PBFT算法、PoW算法。
?
?
看完本文，你對這兩種解決方案有什么看法？歡迎在評論區(qū)跟我們討論！?
總結(jié)
以上是生活随笔為你收集整理的这怕是我看过的最好的关于 “ 拜占庭将军问题 ” 的文章的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 你所不知道的getResource（）在
- 下一篇： 拥有一亿会员的爱奇艺如何搭建大数据实时分