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

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

成都創(chuàng)新互聯(lián)公司主營喀喇沁網(wǎng)站建設的網(wǎng)絡公司,主營網(wǎng)站建設方案,重慶APP開發(fā)公司,喀喇沁h5成都小程序開發(fā)搭建,喀喇沁網(wǎng)站營銷推廣歡迎喀喇沁等地區(qū)企業(yè)咨詢

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

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

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

3.3 叛徒是否可被抓？

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

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

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

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

考慮下面兩個問題：

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

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

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

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

• 副官里有叛徒。

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

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

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

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

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

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

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

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

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

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

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

Case2：副官里有叛徒

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

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

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

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

當前文章：白話講解，拜占庭將軍問題
文章鏈接：http://bm7419.com/article48/jcsphp.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供虛擬主機、網(wǎng)站收錄、關鍵詞優(yōu)化、外貿(mào)網(wǎng)站建設、企業(yè)建站、ChatGPT

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)