人工智能伦理

图5.43 拜占庭将军问题要解决在不信任环境里如何达成共识

例5.5 考虑思想实验：n位拜占庭将军各自率领军队围攻一座城池，之间靠传令兵口头联络，他们的决策只在“进攻”和“撤退”中二选一投票。每位将军都向其余的n−1位将军各派传令兵送上自己的投票，在收齐n张投票（包括自己的那张）之后，按照得票多的决策行事（即少数服从多数）。如果在规定的时间内未收到投票，则缺省地算作“进攻”。所有部队只有同时进攻或者同时撤退（即协调一致）才算成功，否则算失败。

图5.44 每位将军都向其他将军派发信使，传递他的决策或消息

譬如，有9位将军，其中4位投票“进攻”，5位投票“撤退”，则每位将军都执行“撤退”的决策。假设将军X主张“撤退”，则下面两种情况的最终结果是一样的。

将军X的某传令兵路上出了问题（譬如，被敌军杀死）没按时完成送达任务，而其他传令兵都按时送达了消息，则有一位将军执行了“进攻”，其他将军执行了“撤退”，整个部队行动失败。

874 ISLAND 1974

图5.45 信使有可能在路上被杀，将军有可能是叛徒

传令兵们都按时完成了送达任务。将军X是个隐藏的叛徒，为了搅乱决策，他向一位将军发送了“进攻”，而向其他将军发送了“撤退”。

未到达的传令兵、叛变的将军是对网络延迟、信息节点不可靠（如恶意节点）的隐喻。需要协调才能达成共识的情况经常出现在时钟同步、负载平衡、智能电网、多智能体、区块链、云计算等应用中，这些应用需要抗干扰能力强的共识协议。

因为叛徒们可以随心所欲，所以我们约定不考虑那些叛变的将军，只要忠诚的将军能够协调一致就算达成了共识。为了简化拜占庭将军问题，兰泊特假设传令兵们都能按时地传达真实的口头信息（即信道安全且没有时延），他把拜占庭将军的角色分为一位司令（即最早派发传令兵的那位将军，他是唯一的，但不是事先指定的）和n−1位副官，司令向副官们发布“进攻”或“撤退”命令（副官们可以相互告知他们得到的命令），使得：

所有忠诚的副官都服从同样的命令。

如果司令是忠诚的，那么每一个忠诚的副官都服从他发出的命令。

考虑一位司令、两位副官的拜占庭将军问题，如果其中有一人是叛徒（用灰色的节点表示），则不能达成共识^[94]，分以下两种情况。

(1)如果副官Y是叛徒，他对副官X谎称司令的命令是“撤退”，令副官X感到困惑，他不知道司令和副官Y哪个是叛徒，因此无法执行命令。

图5.46 副官Y说谎，造成副官X不知所措

(2)如果司令是叛徒，他对副官X,Y的命令不同，令他们无法协调一致。

图5.47 若司令是叛徒，副官们得到的命令不一致

下面，接着考虑一位司令、三位副官的拜占庭将军问题，如果其中有一人是叛徒，则忠诚的将军们能达成共识。分以下两种情况：

(i)如果副官Y是叛徒，他对副官X,Z谎称司令的命令是“撤退”（记作R）。忠诚的副官X,Z相互告知他收到的命令是“进攻”（记作A），二人按照多数投票执行“进攻”的命令。