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

本篇內容介紹了“白話講解，拜占庭將軍問題”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

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

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

根據這一結論進一步推導可以得出一個更通用的結論，如果存在 m 個叛徒將軍，那么當將軍總數小于或等于 3m 時（n <= 3m，m代表叛徒將軍個數)，叛徒便無法被發現，整個系統的一致性也就無法達成。

3.3 叛徒是否可被抓？

從上面的結論，可以看出，忠誠將軍的人數是叛徒人數 2 倍的時候，依然不能找出叛徒，那么再多一個忠誠的將軍呢？

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

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

現在，將問題再進一步簡化，暫不需要考慮整個投票的過程，只需要考慮一個將軍向其他三個將軍各發送了一條命令，忠誠將軍能否對這個命令達成一致的情況，為了區分發送命令的將將軍和接收消息的將軍，我們將發送命令的將軍稱為發令將軍（M），將接收命令的將軍稱為副官（S）。

考慮下面兩個問題：

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

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

這時候就出現了兩種情況：

• 發令將軍是叛徒 ；

• 副官里有叛徒。

Case1：發令將軍是叛徒

假設D是叛徒，向A和B發送了進攻，向C發送了撤退。現在，我們切入到A的視角。

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

B說是進攻，C說是撤退。

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

• D給不同人發送了不一致的消息；

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

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

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

那么A和B至少在D發送的是進攻這一消息上，達成了一致，兩者選擇都是進攻。

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

Case2：副官里有叛徒

假設C是叛徒，D給三個副官都發送了進攻，那么叛徒C應該怎樣同步D的消息，才能分裂忠誠的發令將軍和忠誠副官間的關系呢？

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

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

由此可見，在多了一個忠臣的情況下，叛徒需要處處小心，才能避免被發現。與此同時，忠臣們即便在存在混亂信息的情況下，行動上也依舊達成了一致。根據推理，我們可以推導出一個結論：當忠臣的個數為 2m + 1 時，他們可以容忍 m 個叛徒產生的破壞。