Byzantine Generals Problem

• 中文:拜占庭将军问题

解释

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

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

问题描述

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

实际应用

在点对点式数字货币系统比特币里，比特币网络的运作是平行的（parallel）。各结点与终端都运算著区块链来达成工作量证明（PoW）。工作量证明的链接是解决比特币系统中拜占庭问题的关键，避免有问题的结点（即前文提到的“反叛的将军”）破坏数字货币系统里交易帐的正确性，是对整个系统的运行状态有着重要的意义。

在一些飞行器（如波音777）的系统中[19] [20][21]也有使用拜占庭容错。而且由于是即时系统，容错的功能也要能尽快回复，比如即使系统中有错误发生，容错系统也只能做出一微秒以内的延迟。

一些航天飞机的飞行系统[22]甚至将容错功能放到整个系统的设计之中。

拜占庭容错机制是将收到的消息（或是收到的消息的签名）转交到其他的接收者。这类机制都假设它们转交的消息都可能念有拜占庭问题。在高度安全要求的系统中，这些假设甚至要求证明错误能在一个合理的等级下被排除。当然，要证明这点，首先遇到的问题就是如何有效的找出所有可能的、应能被容错的错误。这时候会试着在系统中加入错误插入器。