The Byzantine Generals Problem拜占庭将军问题的可解性

发布网友 发布时间：2024-10-24 02:36

我来回答

共1个回答

热心网友 时间：2024-11-07 08:50

在拜占庭将军问题中，当叛徒数量达到或超过总人数的三分之一时，问题的解变得极其复杂，无法确保所有忠诚的将军能够达成一致行动。例如，如果有三位将军，其中一位副官是叛徒，当司令发出进攻命令时，叛徒可能误导其他副官，导致混乱。如果司令本人也是叛徒，他会发出相互矛盾的指令，使得副官们无法确定正确的行动方向。

在三模冗余系统中，允许一个将军出现拜占庭故障，即叛徒数等于1/3时，问题变得不可解。三模冗余系统主要应对的是故障-冻结类型的故障，但无法处理叛徒的误导。为了克服这种情况，如果叛徒数少于1/3，即在四模冗余系统中，拜占庭问题可解。这需要至少四个人，其中叛徒不超过一个，确保多数意见能够正确执行。司令将命令逐级传达，忠诚的副官通过多数表决达成一致。

对于口头信息，如果叛徒少于1/3，可以通过明确的命令传递和沉默检测来解决拜占庭问题。然而，书写信息，即带有签名的信息，提供更高级别的安全性和可验证性，这对于保证至少2/3的将军忠诚时的拜占庭问题可解至关重要。即使司令是叛徒，他试图伪造签名或发送矛盾指令，忠诚的将军们通过相互验证签名，也能确保达成一致的行动。

一个可信的计算机系统必须容忍一个或多个部件的失效。失效的部件可能送出相互矛盾的信息给系统的其他部件。这正是目前网络安全要对付的情况，如银行交易安全、存款安全。美国2001/9/11遭恐怖袭击之后，大家普遍认识到银行的异地备份非常重要。纽约的一家银行可以在东京、巴黎、苏黎世设置异地备份。当某些点受到攻击甚至破坏以后，可以保证账目仍然不错，得以复原和恢复。从技术的角度讲，这是一个很困难的问题。因为被攻击的系统不但可能不作为，而且可能进行破坏。国家的安全就更不必说了。