茶年 · 中文维基百科

拜占庭将军问题

Wikipedia · 2026-01-01 维基百科 👁 2 阅读

拜占庭将军问题（），是由莱斯利·兰波特在其同名论文中提出的分布式对等网络通信容错問題。

在分佈式計算中，不同的計算機通过通讯交换信息达成共识而按照同一套协作策略行动。但有時候，系统中的成员计算机可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，使得网络中不同的成员关于全体协作的策略得出不同结论，从而破坏系统一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。

问题描述
莱斯利·兰波特在其论文

  • 另一個解決方案需要有無法消去的簽名。在現今許多高度資安要求的關鍵系統裡，數位簽章就經常被用來實作拜占庭容错，找出有問題的將軍。然而，在生命攸關系統裡，使用錯誤偵測碼就可以大幅降低問題的發生。無論系統是否存在拜占庭将军問題。所以需要做密碼運算的數位簽章也不一定適合這類系統。、MMFCS

與 SIFT。

實用拜占庭容錯
1999年，卡斯托（Miguel Castro）與利斯科夫（Barbara Liskov）提出了實用拜占庭容錯（PBFT）演算法。該演算法能提供高效能的運算，使得系統可以每秒處理成千的請求，比起舊式系統快了一些。

而在PBFT之後，許多用於拜占庭容錯（BFT）的通訊協議也被提出來改善其通訊的強健性與效率。比如Q/U、HQ、Zyzzyva與ABsTRACTs
...，用來提升效率。而Aardvark與RBFT是用來加強強健性。另外，Adapt則使用原有的BFT協議做調適，以強化其效率與強健性。BFT協議更可以藉由加入可任務的單元，以減少發出副本的次數。比如：A2M-PBFT-EA與MinBFT。

计算机系统
在分布式对等网络中需要按照共同一致策略协作的成员计算机即为问题中的将军，而各成员计算机赖以进行通讯的网络链路即为信使。拜占庭将军问题描述的就是某些成员计算机或网络链路出现错误、甚至被蓄意破坏者控制的情况。

實務應用
在對等式數位貨幣系統比特幣裡，比特幣網路的運作是平行的（parallel）。各節點與終端都運算著區塊鏈來達成工作量證明（PoW）。工作量證明的連結是解決比特幣系統中拜占庭問題的關鍵，避免有問題的節點（即前文提到的「反叛的將軍」）破壞數位貨幣系統裡交易帳的正確性，是對整個系統的運行狀態有著重要的意義。

在一些飛行器（如波音777）的系統中
也有使用拜占庭容錯。而且由於是即時系統，容錯的功能也要能儘快回覆，比如即使系統中有錯誤發生，容錯系統也只能做出一微秒以內的延遲。

一些太空梭的飛行系統甚至將容錯功能放到整個系統的設計之中。

拜占庭容錯機制是將收到的訊息（或是收到的訊息的簽章）轉交到其他的接收者。這類機制都假設它們轉交的訊息都可能含有拜占庭問題。在高度安全要求的系統中，這些假設甚至要求證明錯誤能在一個合理的等級下被排除。當然，要證明這點，首先遇到的問題就是如何有效的找出所有可能的、應能被容錯的錯誤。這時候會試著在系統中加入錯誤插入器。

参考资料
外部連結

#計算理論 #公钥密码学 #容错计算机系统 #分布式计算问题

评论 (0)

  • 还没有评论，来抢沙发吧。