拜占庭將軍問題
拜占庭將軍問題（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]。
參考資料
編輯- ^ 1.0 1.1 1.2 Lamport, L.; Shostak, R.; Pease, M. The Byzantine Generals Problem (PDF). ACM Transactions on Programming Languages and Systems. 1982, 4 (3): 382–401. doi:10.1145/357172.357176. （原始內容 (PDF)存檔於7 February 2017）.
- ^ 2.0 2.1 Driscoll, K.; Hall, B.; Paulitsch, M.; Zumsteg, P.; Sivencrona, H. The Real Byzantine Generals: 6.D.4–61–11. 2004. doi:10.1109/DASC.2004.1390734.
- ^ 3.0 3.1 Driscoll, Kevin; Hall, Brendan; Sivencrona, Håkan; Zumsteg, Phil. Byzantine Fault Tolerance, from Theory to Reality 2788: 235–248. 2003. ISSN 0302-9743. doi:10.1007/978-3-540-39878-3_19.
- ^ Feldman, P.; Micali, S. An optimal probabilistic protocol for synchronous Byzantine agreement (PDF). SIAM J. Comput. 1997, 26 (4): 873–933 [2017-11-29]. doi:10.1137/s0097539790187084. （原始內容存檔 (PDF)於2016-03-05）.
- ^ Paulitsch, M.; Morris, J.; Hall, B.; Driscoll, K.; Latronico, E.; Koopman, P. Coverage and the Use of Cyclic Redundancy Codes in Ultra-Dependable Systems: 346–355. 2005. doi:10.1109/DSN.2005.31.
- ^ Hopkins, Albert L.; Lala, Jaynarayan H.; Smith, T. Basil. The Evolution of Fault Tolerant Computing at the Charles Stark Draper Laboratory, 1955–85 1: 121–140. 1987. ISSN 0932-5581. doi:10.1007/978-3-7091-8871-2_6.
- ^ Driscoll, Kevin; Papadopoulos, Gregory; Nelson, Scott; Hartmann, Gary; Ramohalli, Gautham, Multi-Microprocessor Flight Control System (Technical Report), Wright-Patterson Air Force Base, OH 45433, USA: AFWAL/FIGL U.S. Air Force Systems Command, 1984, AFWAL-TR-84-3076
- ^ SIFT: design and analysis of a fault-tolerant computer for aircraft control. Microelectronics Reliability. 1979, 19 (3): 190. ISSN 0026-2714. doi:10.1016/0026-2714(79)90211-7.
- ^ Castro, M.; Liskov, B. Practical Byzantine Fault Tolerance and Proactive Recovery. ACM Transactions on Computer Systems (Association for Computing Machinery). 2002, 20 (4): 398–461. doi:10.1145/571637.571640.
- ^ Abd-El-Malek, M.; Ganger, G.; Goodson, G.; Reiter, M.; Wylie, J. Fault-scalable Byzantine Fault-Tolerant Services. Association for Computing Machinery. 2005. doi:10.1145/1095809.1095817.
|conference=被忽略 (幫助) - ^ Cowling, James; Myers, Daniel; Liskov, Barbara; Rodrigues, Rodrigo; Shrira, Liuba. HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance. Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation: 177–190. 2006. ISBN 1-931971-47-1.
- ^ Kotla, Ramakrishna; Alvisi, Lorenzo; Dahlin, Mike; Clement, Allen; Wong, Edmund. Zyzzyva: Speculative Byzantine Fault Tolerance. ACM Transactions on Computer Systems (Association for Computing Machinery). December 2009, 27 (4). doi:10.1145/1658357.1658358.
- ^ Guerraoui, Rachid; Kneževic, Nikola; Vukolic, Marko; Quéma, Vivien. The Next 700 BFT Protocols. Proceedings of the 5th European conference on Computer systems. EuroSys. 2010 [2017-11-29]. （原始內容存檔於2011-10-02）.
- ^ Clement, A.; Wong, E.; Alvisi, L.; Dahlin, M.; Marchetti, M. Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults (PDF). Symposium on Networked Systems Design and Implementation. USENIX. April 22–24, 2009 [2017-11-29]. （原始內容存檔 (PDF)於2010-12-25）.
- ^ Aublin, P.-L.; Ben Mokhtar, S.; Quéma, V. RBFT: Redundant Byzantine Fault Tolerance. 33rd IEEE International Conference on Distributed Computing Systems. International Conference on Distributed Computing Systems. July 8–11, 2013. （原始內容存檔於August 5, 2013）.
- ^ Bahsoun, J. P.; Guerraoui, R.; Shoker, A. Making BFT Protocols Really Adaptive. Parallel and Distributed Processing Symposium (IPDPS), 2015 IEEE International. 2015-05-01: 904–913 [2017-11-29]. doi:10.1109/IPDPS.2015.21. （原始內容存檔於2018-06-20）.
- ^ Chun, Byung-Gon; Maniatis, Petros; Shenker, Scott; Kubiatowicz, John. Attested Append-only Memory: Making Adversaries Stick to Their Word. Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles. SOSP '07 (New York, NY, USA: ACM). 2007-01-01: 189–204 [2017-11-29]. ISBN 9781595935915. doi:10.1145/1294261.1294280. （原始內容存檔於2020-01-29）.
- ^ Veronese, G. S.; Correia, M.; Bessani, A. N.; Lung, L. C.; Verissimo, P. Efficient Byzantine Fault-Tolerance. IEEE Transactions on Computers. 2013-01-01, 62 (1): 16–30 [2017-11-29]. ISSN 0018-9340. doi:10.1109/TC.2011.221. （原始內容存檔於2017-12-01）.
- ^ M., Paulitsch; Driscoll, K. Chapter 48:SAFEbus. Zurawski, Richard (編). Industrial Communication Technology Handbook, Second Edition. CRC Press. 9 January 2015: 48–1–48–26 [2017-11-29]. ISBN 978-1-4822-0733-0. （原始內容存檔於2020-06-26）.
- ^ Thomas A. Henzinger; Christoph M. Kirsch. Embedded Software: First International Workshop, EMSOFT 2001, Tahoe City, CA, USA, October 8-10, 2001. Proceedings (PDF). Springer Science & Business Media. 26 September 2001: 307– [2017-11-29]. ISBN 978-3-540-42673-8. （原始內容存檔 (PDF)於2017-08-09）.
- ^ Yeh, Y.C. Safety critical avionics for the 777 primary flight controls system 1: 1C2/1–1C2/11. 2001. doi:10.1109/DASC.2001.963311.
- ^ （[//web.archive.org/web/20160805064218/https://lwn.net/Articles/540368/ 頁面存檔備份，存於網際網路檔案館） ELC: SpaceX lessons learned [LWN.net]]
- ^ Nanya, T.; Goosen, H.A. The Byzantine hardware fault model. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1989, 8 (11): 1226–1231. ISSN 0278-0070. doi:10.1109/43.41508.
- ^ Martins, Rolando; Gandhi, Rajeev; Narasimhan, Priya; Pertet, Soila; Casimiro, António; Kreutz, Diego; Veríssimo, Paulo. Experiences with Fault-Injection in a Byzantine Fault-Tolerant Protocol 8275: 41–61. 2013. ISSN 0302-9743. doi:10.1007/978-3-642-45065-5_3.
- ^ US patent 7475318,Kevin R. Driscoll,「Method for testing the sensitive input range of Byzantine filters」,發行於2009-01-06,指定於Honeywell International Inc.