拜占庭将军问题

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

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

问题描述

莱斯利·兰波特在其论文[1]中描述了如下问题：

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

系统的问题在于，可能将军中出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。假设有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]
  • 假如上述两个解决方案里，将军们无法直接通信时，该论文亦有进一步的解决方案。

此外，1980年代还有其他用来达到拜占庭容错的架构被提出，如：FTMP[6]、MMFCS[7] 与 SIFT。[8]

实用拜占庭容错

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. ^ 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. ^ 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. ^ 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. 
  4. ^ 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）. 
  5. ^ 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. 
  6. ^ 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. 
  7. ^ 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 
  8. ^ 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. 
  9. ^ 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. 
  10. ^ 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=被忽略 (帮助)
  11. ^ 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. 
  12. ^ 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. 
  13. ^ 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）. 
  14. ^ 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）. 
  15. ^ 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）. 
  16. ^ 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）. 
  17. ^ 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）. 
  18. ^ 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）. 
  19. ^ 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）. 
  20. ^ 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）. 
  21. ^ 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. 
  22. ^ （[//web.archive.org/web/20160805064218/https://lwn.net/Articles/540368/ 页面存档备份，存于互联网档案馆） ELC: SpaceX lessons learned [LWN.net]]
  23. ^ 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. 
  24. ^ 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. 
  25. ^ US patent 7475318,Kevin R. Driscoll,“Method for testing the sensitive input range of Byzantine filters”,发行于2009-01-06,指定于Honeywell International Inc. 

外部链接