下载掌阅APP，畅读海量书库
立即打开
拜占庭将军问题是1982年由图灵奖获得者莱斯利·兰波特（Leslie Lamport）在论文“The Byzantine Generals Problem”中提出的分布式对等网络通信容错问题。其主要观点是，在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。在分布式计算中，不同的计算机通过通信交换信息并达成共识，从而按照同一套协作策略行动；但有时系统中的成员计算机可能会发送错误的信息，用于传递信息的通信网络也可能导致信息损坏，使网络中不同的成员关于全体协作的策略得出不同结论，从而破坏系统一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。
为了便于理解，莱斯利·兰波特在其论文中通过拜占庭将军的故事将问题描述为：一群拜占庭将军各带领一支军队共同围困一座城市拜占庭（东罗马帝国的首都）。如图1-13所示，为了简化问题，军队的行动策略只有两种：进攻（Attack，后面简称A）或撤退（Retreat，后面简称R）。如果这些军队不是统一进攻或撤退，就可能造成灾难性后果，因此将军们必须通过投票来达成一致策略：同进或同退。因为将军们分别在城市的不同方位，所以他们只能通过信使互相联系。在投票过程中，每位将军都将自己的投票信息（A或R）通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以分析出共同的投票结果，从而决定行动策略。
图1-13 拜占庭将军问题示意图
这个抽象模型的问题在于：将军中可能存在叛徒，他们不仅会发出误导性投票，还可能选择性地发送投票信息。由于将军之间需要通过信使通信，叛变将军可能通过伪造信件来以其他将军的身份发送假投票。即使在保证所有将军都忠诚的情况下，也不能排除信使被敌人截杀，甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通信可靠性来解决问题。假使那些忠诚（或没有出错）的将军仍然能通过多数投票来决定他们的战略，便称达到了拜占庭容错。在此，票都会有一个默认值，若消息（票）没有被收到，则使用此默认值来投票。
将上述故事映射到分布式系统中，将军便成了机器节点，信使就是通信系统。
莱斯利·兰伯特在其论文中提出了几个解决方案，达到了拜占庭容错。其中一个为BFT（Byzantine Fault Tolerant，拜占庭容错）算法，假设将军总数是 N ，叛徒将军数为 F ，则当 N ≥3 F +1时，问题才有解，才能达成共识。只要有问题的将军的数量不到三分之一，仍可以达到“拜占庭容错”，原因是把同样的标准下放到“军官与士官的问题”时，在背叛的军士官不足三分之一的情况下，有问题的军士官可以很容易地被发现。比如有军官A、士官B与士官C，当A要求B进攻，却要求C撤退时，即使B与C交换所收到的命令，B与C仍不能确定是否A有问题，因为B或C可能将已篡改的消息传给对方。也就是说，当将军总数为3、叛徒将军数为1时，系统无法达成一致或拜占庭容错。当将军总数为4、叛徒将军数为1时，系统可以达成一致或拜占庭容错。以函数来表示，将军的总数为 n ，其中背叛者的数量为 t ，则只要 n ＞3 t 就可以容错。
拜占庭容错算法是面向拜占庭问题的容错算法，解决的是在网络通信可靠但节点可能出现故障或作恶的情况下如何达成共识。长期以来，拜占庭问题的解决方案都存在运行过慢或复杂度过高的问题，实用拜占庭容错（Practical Byzantine Fault Tolerance，PBFT）算法解决了该问题。其核心思想是：对于每一个收到命令的将军，都要去询问其他人，他们收到的命令是什么。也就是说，利用不断的信息交换让可行的节点确认哪一个记录选择是正确的，即发现其中的背叛者。PBFT算法本质上就是利用通信次数换取信用。每个命令的执行都需要节点间两两交互去核验消息，通信代价是非常高的。通常，采用PBFT算法，节点间的通信复杂度是节点数的平方级。
1999年，这一算法由Castro和Liskov在论文“Practical Byzantine Fault Tolerance and Proactive Recovery”中提出。该算法首次将拜占庭容错算法的复杂度从指数级降低到了多项式级，目前已得到广泛应用。其可以在恶意节点不超过总数1/3的情况下同时保证安全性和活性。PBFT算法采用密码学相关技术（RSA签名算法、消息验证编码和摘要）确保消息在传递过程中无法被篡改和破坏。