拜占庭将军问题
概述
拜占庭将军问题（Byzantine Generals Problem）是由Leslie Lamport等人于1982年提出的一个分布式计算问题，定义了分布式系统中最强的故障模型（恶意故障），其中节点不仅可能崩溃，还可能恶意行为，试图欺骗其他节点。
关键内容
- 问题描述：
- 问题以拜占庭帝国军队围攻城市为比喻：多个将军必须通过信使协商作战计划
- 部分将军可能是叛徒，试图阻止忠诚的将军们达成一致
-
需要设计算法使得忠诚的将军们能够在叛徒干扰的情况下达成一致
-
故障模型：
- 比普通的崩溃故障模型更强
- 节点可能发送错误消息、虚假消息或恶意误导其他节点
-
叛徒节点可能以任意方式破坏共识过程
-
理论结果：
- 证明了容忍f个拜占庭故障需要至少3f+1个节点
- 当系统中超过1/3的节点为叛徒时，无法保证一致性
-
在非认证信道上，需要超过2/3的节点为忠诚的才能达成共识
-
与Paxos的关系：
- 与Paxos同为Lamport的重要贡献
- Paxos主要解决崩溃故障模型，而拜占庭将军问题处理更强的故障模型
-
拜占庭将军问题的解决方案需要更强的密码学机制
-
实际应用：
- 现代区块链系统的基础理论
- 高安全等级的容错系统设计
- 关键任务分布式系统的安全机制
来源
- 18-lamport-paxos — 详细分析了拜占庭将军问题作为Lamport的重要贡献之一
- Leslie Lamport — 问题提出者
- Paxos算法 — 同一研究者的相关贡献
相关
- Leslie Lamport — authored
- Paxos算法 — relates_to
- 拜占庭容错 — basis_for
- 分布式系统 — applies_to
- 共识算法 — relates_to
- 崩溃故障 — compares_to