拜占庭将军问题_1982_.pdf
免费下载
作者：LESLIE LAMPORT、ROBERT SHOSTAK 和 MARSHALL PEASE @ 斯坦福国际研究院
译者&校对：闵敏 & 裴奇, Elisa @ EthFans.org
拜占庭将军问题
可靠的计算机系统必须具备处理故障组件的能力，以防它们向系统中的其它组件传递冲突信息。这种情况可以抽象地
表述成一群拜占庭军队的将军各自带领部队驻扎在一座敌城周围。在只能依靠信使进行通信的情况下，这些将军必须
就同一个作战计划达成共识。然而，他们中间可能会出现一个或多个叛将，试图混淆其他人的视听。问题在于如何找
到一种算法来确保忠将之间达成共识。经论证，如果仅使用口信交流，当且仅当忠将人数超过 2/3 时，此问题有解；
因此，一位叛将可以迷惑两位忠将。如果使用无法伪造的书信交流，无论将军总人数和潜在叛将的人数是多少，这个
问题都有解。本文最后讨论了如何应用这些解法构建可靠的计算机系统。
分类和关键词：C.2.4. [计算机通信网络]：分布式系统——网络操作系统；D.4.4 [操作系统]：通信管理——网络通
信；D.4.5 [操作系统]：可靠性——容错
通用术语：算法，可靠性
其它关键词：交互一致性
1.引言
可靠的计算机系统必须具备处理一个或多个故障组件的能力。故障组件可能会表现出一类常常被忽视的行为——向系
统中的其它组件发送冲突信息。处理这类故障的问题可抽象地表述成拜占庭将军问题。本文主要讨论了这一抽象问
题，并在结论中提出了如何用这些解决方案实现可靠的计算机系统。
假设拜占庭军队中有几个分队驻扎在一座敌城周围，每个分队都有一个将军。这些将军之间只能依靠信使进行交流。
侦查过敌军之后，他们必须制定一个统一的作战计划。然而，一些将军可能会叛变，企图阻止忠将达成共识。这些将
军必须通过一种算法来保证：
A. 所有忠将都达成一致的作战计划。
忠将会遵从算法的一切指令，叛将则会随心所欲。算法必须保证无论叛将怎么捣乱条件 A 都成立。
忠将不仅应该达成共识，还应该就合理的计划达成一致。因此，我们还想要保证：
B. 少数叛将无法致使忠将采纳不良计划。
要将条件 B 形式化很难，因为这需要精确定义何为不良计划，我们也不打算尝试给出该定义，而是把各位将军达成
共识的方式作为思考的切入点。每位将军都会侦查敌方情况，并将侦查结果传达给其他将军。假设第 位将军传达的
消息为 ，将军总人数为 ，每位将军通过某种方法将 的值结合起来形成一个作战计划。要实现
条件 A ，所有将军必须采用同一种方法结合信息。要实现情况 B ，必须采取一种稳健的方法。例如，如果只需决定
是进攻还是撤退， 则可以代表将军 认为哪种选项更好的观点，最终决定可以采用多数票决的方式作出。只有在
忠将投出的正反票数几乎相等的情况下，少数叛将才能左右最终决定，在这种情况下，进攻或撤退都不算是不良方
案。
虽然这种方式可能不是满足条件 A 和 B 的唯一方法，但这是我们了解的唯一方法。该方法假设各位将军通过某种方
法彼此传达 值。最直接的方式是让将军 通过信使将 传达给其他将军。然而，这是行不通的，因为满足条
件 A 需要每位忠将获得相同的 值，而叛将可能会向不同的将军传递不同的值。若要满足条件 A，必须
做到：
1. 每位忠将必须获得相同的信息 $v(1), … ,v(n)$。
条件 1 意味着其它将军不一定要使用直接从将军 处获得的 值，因为如果叛变的是将军 ，他可能会向不同的将
军发送不同的值。此即表明，除非非常谨慎，否则为了满足条件 1 ，还需考虑一种可能性，哪怕将军 是忠诚的，其
他将军们还是使用了一个不同于将军 发送的 值（校注：即接收 的将军中有叛变）。若要满足条件 B ，必
须禁止这种情况发生。例如，在所有忠将发送的值均为 “进攻” 的情况下，不能允许少数叛将诱导忠将在 “撤退”, … ,
“撤退” 这些值中作出决定。因此，将军 还必须遵从下列要求：
2. 如果将军 是忠诚的，那么其它忠将必须将他发送的值作为 值。
我们可以将条件 1 改为针对所有将军 的条件（不管将军 忠诚与否），
1'. 任意两位忠将使用的 值是相同的。
条件 1' 和 2 均针对将军 发送的值。因此，我们现在仅需考虑一位将军如何将他的值发送给其他将军。这种情况可
以描述成一位指挥官向副官下达命令，引出了下述问题。
一位指挥官必须向他的 位副官发送一个命令，这个命令要满足以下两个条件：
IC1. 所有忠诚的副官都服从同一个命令。
IC2. 如果指挥官是忠诚的，则每位忠诚的副官都会服从他下达的命令。
IC1 和 IC2 称为 条件。请注意，如果指挥官是忠诚的，那么满足了 IC2 势必会满足 IC1 。然而，指挥官
不一定是忠诚的。
若要解决最初的问题，将军 在发送 值之时使用拜占庭将军问题的解法，发送命令“将 作为我的值”，其他
将军则充当副官。
2. 无解之解 （反证法）
拜占庭将军问题看似简单，实则难在：如果将军只能发送口信的话，除非忠将人数达 2/3 以上，否则无解。尤其是在
仅有三位将军的情况下，一旦出现一位叛将，这个问题就无解。由于口信的内容是完全由发送者控制的，因此叛变的
发送者可以传达任意消息。这类消息类似于计算机通常情况下互相发送的那类消息。我们在第 4 节提出的签名书面消
息属于另一种情况。
如上所述，如果以口信作为通信方式，一旦三位将军中有一位叛变 ，则该问题无解。为了简化问题，我们只考虑“进
攻”和“撤退”两种选择。首先探究图 1 所示场景，即指挥官是忠诚的，并发送了“进攻”的命令，然而副官 2 叛变了，向
副官 1 谎报自己收到的是“撤退”的命令。若要满足条件 IC2 ，副官 1 必定要服从进攻的命令。
现在考虑图 2 所示的另一个场景，即指挥官叛变了，并向副官 1 发送了“进攻”的命令，向副官 2 发送了“撤退”的命
令。副官 1 不知道谁是叛将，而且没法辨别指挥官实际向副官 2 发送了什么消息。因此，图 1 和图 2 所示场景对副
官 1 来说没有区别。如果叛将坚持谎报军令，副官 1 没法辨别是哪种场景，就必须服从“进攻”的命令。因此副官 1 只
要从指挥官处收到 “进攻” 的命令，必定会服从。
of 14
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
文档被以下合辑收录
评论