拜占庭將軍問題（Byzantine Generals Problem），是由萊斯利·蘭波特在其同名論文[1]中提出的分布式對等網絡通信容錯問題。
在分佈式計算中，不同的計算機通過通訊交換信息達成共識而按照同一套協作策略行動。但有時候，系統中的成員計算機可能出錯而發送錯誤的信息，用於傳遞信息的通訊網絡也可能導致信息損壞，使得網絡中不同的成員關於全體協作的策略得出不同結論[2]，從而破壞系統一致性[3]。拜占庭將軍問題被認為是容錯性問題中最難的問題類型之一。
問題描述
一組拜占庭將軍分別各率領一支軍隊共同圍困一座城市。為了簡化問題，將各支軍隊的行動策略限定為進攻或撤離兩種。因為部分軍隊進攻部分軍隊撤離可能會造成災難性後果，因此各位將軍必須通過投票來達成一致策略，即所有軍隊一起進攻或所有軍隊一起撤離。因為各位將軍分處城市不同方向，他們只能通過信使互相聯繫。在投票過程中每位將軍都將自己投票給進攻還是撤退的信息通過信使分別通知其他所有將軍，這樣一來每位將軍根據自己的投票和其他所有將軍送來的信息就可以知道共同的投票結果而決定行動策略。
系統的問題在於，可能將軍中出現叛徒，他們不僅可能向較為糟糕的策略投票，還可能選擇性地發送投票信息。假設有9位將軍投票，其中1名叛徒。8名忠誠的將軍中出現了4人投進攻，4人投撤離的情況。這時候叛徒可能故意給4名投進攻的將領送信表示投票進攻，而給4名投撤離的將領送信表示投撤離。這樣一來在4名投進攻的將領看來，投票結果是5人投進攻，從而發起進攻；而在4名投撤離的將軍看來則是5人投撤離。這樣各支軍隊的一致協同就遭到了破壞。
由於將軍之間需要通過信使通訊，叛變將軍可能通過偽造信件來以其他將軍的身份發送假投票。而即使在保證所有將軍忠誠的情況下，也不能排除信使被敵人截殺，甚至被敵人間諜替換等情況。因此很難通過保證人員可靠性及通訊可靠性來解決問題。
假使那些忠誠（或是沒有出錯）的將軍仍然能通過多數決定來決定他們的戰略，便稱達到了拜占庭容錯。在此，票都會有一個預設值，若訊息（票）沒有被收到，則使用此預設值來投票。
上述的故事對映到計算機系統裡，將軍便成了計算機，而信差就是通訊系統。雖然上述的問題涉及了電子化的決策支援與資訊安全，卻沒辦法單純的用密碼學與數位簽章來解決。因為電路錯誤仍可能影響整個加密過程，這不是密碼學與數位簽章演算法在解決的問題。因此計算機就有可能將錯誤的結果送出去，亦可能導致錯誤的決策。
早期的解決方案
在1982年的論文[1]中提過幾個解決方案。方案中把問題往下拆解，認為在「拜占庭將軍」的問題可以在「軍官與士官的問題」裡解決，以降低將軍問題的發生。而所謂的「軍官與士官的問題」，就是探討軍官與他的士官是否能忠實實行命令。
- 其中一個解決方案認為即使出現了偽造或錯誤的訊息。只要有問題的將軍的數量不到三分之一，仍可以達到「拜占庭容錯」。原因是把同樣的標準下放到「軍官與士官的問題」時，在背叛的軍士官不足三分之一的情況下，有問題的軍士官可以很容易的被糾出來。比如有軍官A，士官B與士官C。當A要求B進攻，卻要求C撤退時。就算B與C交換所收到的命令，B與C仍不能確定是否A有問題，因為B或C可能將竄改了的訊息傳給對方。以函式來表示，將軍的總數為n，n裡面背叛者的數量為t，則只要n > 3t就可以容錯。[4]
- 另一個解決方案需要有無法消去的簽名。在現今許多高度資安要求的關鍵系統裡，數位簽章就經常被用來實作拜占庭容錯，找出有問題的將軍。然而，在生命攸關系統裡，使用錯誤偵測碼就可以大幅降低問題的發生。無論系統是否存在拜占庭將軍問題。所以需要做密碼運算的數位簽章也不一定適合這類系統。[5][2][3]
- 假如上述兩個解決方案裡，將軍們無法直接通訊時，該論文亦有進一步的解決方案。
實用拜占庭容錯
1999年，卡斯托（Miguel Castro）與利斯科夫（Barbara Liskov）提出了實用拜占庭容錯（PBFT）演算法[9]。該演算法能提供高效能的運算，使得系統可以每秒處理成千的請求，比起舊式系統快了一些。
而在PBFT之後，許多用於拜占庭容錯（BFT）的通訊協議也被提出來改善其通訊的強健性與效率。比如Q/U[10]、HQ[11]、Zyzzyva[12]與ABsTRACTs[13] ...，用來提升效率。而Aardvark[14]與RBFT[15]是用來加強強健性。另外，Adapt[16]則使用原有的BFT協議做調適，以強化其效率與強健性。BFT協議更可以藉由加入可任務的單元，以減少發出副本的次數。比如：A2M-PBFT-EA[17]與MinBFT。[18]
計算機系統
在分布式對等網絡中需要按照共同一致策略協作的成員計算機即為問題中的將軍，而各成員計算機賴以進行通訊的網絡鏈路即為信使。拜占庭將軍問題描述的就是某些成員計算機或網絡鏈路出現錯誤、甚至被蓄意破壞者控制的情況。
實務應用
在對等式數位貨幣系統比特幣裡，比特幣網路的運作是平行的（parallel）。各節點與終端都運算著區塊鏈來達成工作量證明（PoW）。工作量證明的連結是解決比特幣系統中拜占庭問題的關鍵，避免有問題的節點（即前文提到的「反叛的將軍」）破壞數位貨幣系統裡交易帳的正確性，是對整個系統的運行狀態有著重要的意義。
在一些飛行器（如波音777）的系統中[19] [20][21]也有使用拜占庭容錯。而且由於是即時系統，容錯的功能也要能儘快回覆，比如即使系統中有錯誤發生，容錯系統也只能做出一微秒以內的延遲。
一些太空梭的飛行系統[22]甚至將容錯功能放到整個系統的設計之中。
拜占庭容錯機制是將收到的訊息（或是收到的訊息的簽章）轉交到其他的接收者。這類機制都假設它們轉交的訊息都可能含有拜占庭問題。在高度安全要求的系統中，這些假設甚至要求證明錯誤能在一個合理的等級下被排除。當然，要證明這點，首先遇到的問題就是如何有效的找出所有可能的、應能被容錯的錯誤[23]。這時候會試著在系統中加入錯誤插入器[24][25]。
參考資料
外部連結
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
