白話講解，拜占庭將軍問題

本篇內(nèi)容介紹了“白話講解，拜占庭將軍問題”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

作為服務(wù)端開發(fā)的同學(xué)，你可能聽說過Paxos、Raft這類分布式一致性算法，也在工作中使用過ZooKeeper、etcd等工具來解決一致性問題。但你可能不知道，這些算法和工具解決的并不是一致性中最難的問題，要討論這個(gè)最難的問題，這就要追溯到 Leslie Lamport 1982 年發(fā)表的著名論文 《拜占庭將軍問題》（The Byzantine Generals Problem ）上了。

綜上所述，我們可以得出一個(gè)結(jié)論：在拜占庭三個(gè)將軍中出現(xiàn)一個(gè)叛徒，并且叛徒可以任意偽造消息的情況下，只要叛徒頭腦清醒，他就始終無法被發(fā)現(xiàn)，甚至還能造成整個(gè)系統(tǒng)的信任危機(jī)。

根據(jù)這一結(jié)論進(jìn)一步推導(dǎo)可以得出一個(gè)更通用的結(jié)論，如果存在 m 個(gè)叛徒將軍，那么當(dāng)將軍總數(shù)小于或等于 3m 時(shí)（n <= 3m，m代表叛徒將軍個(gè)數(shù))，叛徒便無法被發(fā)現(xiàn)，整個(gè)系統(tǒng)的一致性也就無法達(dá)成。

3.3 叛徒是否可被抓？

從上面的結(jié)論，可以看出，忠誠(chéng)將軍的人數(shù)是叛徒人數(shù) 2 倍的時(shí)候，依然不能找出叛徒，那么再多一個(gè)忠誠(chéng)的將軍呢？

為了簡(jiǎn)化問題，接下來假設(shè)有 4 個(gè)拜占庭將軍，分別是A、B、C、D，其中有一個(gè)是叛徒。我們依然秉承找出叛徒的關(guān)鍵，即判斷哪個(gè)將軍發(fā)送了不一致的消息。

也就是說，接下來就是和其他接收到消息的將軍進(jìn)行信息的同步判斷：是否收到的消息不一致。

現(xiàn)在，將問題再進(jìn)一步簡(jiǎn)化，暫不需要考慮整個(gè)投票的過程，只需要考慮一個(gè)將軍向其他三個(gè)將軍各發(fā)送了一條命令，忠誠(chéng)將軍能否對(duì)這個(gè)命令達(dá)成一致的情況，為了區(qū)分發(fā)送命令的將將軍和接收消息的將軍，我們將發(fā)送命令的將軍稱為發(fā)令將軍（M），將接收命令的將軍稱為副官（S）。

考慮下面兩個(gè)問題：

• 那么剩下的三個(gè)副官能不能通過相互間的信息同步找到叛徒？

• 或者所有忠臣間達(dá)成一致，不讓叛徒的分裂想法得逞呢？

這時(shí)候就出現(xiàn)了兩種情況：

• 發(fā)令將軍是叛徒 ；

• 副官里有叛徒。

Case1：發(fā)令將軍是叛徒

假設(shè)D是叛徒，向A和B發(fā)送了進(jìn)攻，向C發(fā)送了撤退?，F(xiàn)在，我們切入到A的視角。

A問B和C：“我從D那里收到的消息是進(jìn)攻，你從D那里收到的是什么呢？”

B說是進(jìn)攻，C說是撤退。

此時(shí)，從A的視角來看，C和D對(duì)同一條消息的說法是不一致的，那么他們兩個(gè)人中肯定有一個(gè)是叛徒，但是A無法判斷的是：

• D給不同人發(fā)送了不一致的消息；

• 還是C偽造了D的消息。

好在，由于A知道最多只有一個(gè)叛徒存在。

那么根據(jù)反證法，如果B也是叛徒，就有兩個(gè)叛徒存在，那么B肯定不是叛徒。

那么A和B至少在D發(fā)送的是進(jìn)攻這一消息上，達(dá)成了一致，兩者選擇都是進(jìn)攻。

B也是同樣的情況，現(xiàn)在A和B彼此建立了信任，而同樣是忠誠(chéng)副官的C，最終則和真正的叛徒D被一同懷疑。

Case2：副官里有叛徒

假設(shè)C是叛徒，D給三個(gè)副官都發(fā)送了進(jìn)攻，那么叛徒C應(yīng)該怎樣同步D的消息，才能分裂忠誠(chéng)的發(fā)令將軍和忠誠(chéng)副官間的關(guān)系呢？

如果將D的消息原樣轉(zhuǎn)發(fā)出去，那么這一想法實(shí)施后也就無法再去當(dāng)叛徒了。如果給A與B均發(fā)送和D相反的撤退消息，那么就回到了前文所講的第一種情況，A和B認(rèn)為D發(fā)送的是進(jìn)攻，發(fā)送消息的D也認(rèn)為自己發(fā)送的消息是進(jìn)攻，忠臣們行動(dòng)上又一次達(dá)成了一致。

然而，為了給系統(tǒng)增加更多的混亂，叛徒C決定再次發(fā)送不一致的消息，告訴B自己從D收到的是進(jìn)攻，告訴A自己從D收到的是撤退。這種情況下，B看到所有人都認(rèn)為D是進(jìn)攻，會(huì)傻傻地認(rèn)為大家是個(gè)團(tuán)結(jié)一致的集體，沒有叛徒。而A會(huì)發(fā)現(xiàn)C和D中出現(xiàn)了一個(gè)叛徒，不過A也再次可以確認(rèn)B是自己人。此時(shí)，A決定再和B同步一輪消息，看看C是不是說了兩個(gè)不一致的消息，這種情況下，叛徒C就完全暴露了。

由此可見，在多了一個(gè)忠臣的情況下，叛徒需要處處小心，才能避免被發(fā)現(xiàn)。與此同時(shí)，忠臣們即便在存在混亂信息的情況下，行動(dòng)上也依舊達(dá)成了一致。根據(jù)推理，我們可以推導(dǎo)出一個(gè)結(jié)論：當(dāng)忠臣的個(gè)數(shù)為 2m + 1 時(shí)，他們可以容忍 m 個(gè)叛徒產(chǎn)生的破壞。