一台计算机出错，你重启它就好了。
但当成千上万台计算机通过会延迟、会丢包的网络协同工作时，一个全新的难题出现了：它们怎么对"现在到底发生了什么"达成一致？某台机器是真的崩溃了，还是只是网络慢了一拍？没有任何一台机器能看到全局。
分布式计算理论研究的，正是这种"没有上帝视角"的计算世界里，什么能做到、什么永远做不到。它和可计算性理论（见 computability）一样，核心结论是一组冷峻的"不可能性定理"——它们划出的边界，不会因为你买更多服务器、写更聪明的代码而后退。
破除误解：分布式系统的难点不是"机器不够快"
很多人以为分布式系统的挑战是性能——把任务切开，让更多机器并行跑得更快。
性能只是表面。真正的难点是不确定性：在一个异步网络里，消息可能任意延迟，你无法区分"一台机器崩溃了"和"它发的消息还在路上"。
这个看似工程细节的事实，会导致一个深刻的数学结论：在最一般的设定下，让一群机器可靠地达成一致，是不可能的。这不是工程偷懒，而是理论铁律。
现场：共识问题（Consensus）
分布式理论的核心是共识问题。
设想 $n$ 个进程，每个手里有一个初始值（比如 0 或 1）。它们要通过相互发消息，最终都"决定"出同一个值。一个正确的共识协议必须同时满足三条：
- 一致性（Agreement）：所有正确的进程决定出同一个值。
- 有效性（Validity）：决定出的值，必须是某个进程真正提出过的（不能凭空捏造）。
- 终止性（Termination）：每个正确的进程最终都能做出决定，不会永远卡住。
听起来理所当然。但魔鬼藏在"网络是异步的、且允许有进程崩溃"这两个前提里。
核心一：FLP 不可能性定理——异步共识的死刑判决
1985 年，迈克尔·费舍尔（Michael Fischer）、南希·林奇（Nancy Lynch）、迈克尔·帕特森（Michael Paterson）发表了分布式理论中最著名的定理（会议版 1983 年，期刊版 1985 年发表于 JACM）。
FLP 定理：在一个完全异步的分布式系统中，哪怕只允许一个进程崩溃（而且是最温和的崩溃——干净地停机，不作恶），也不存在任何确定性算法，能保证总是正确地解决共识问题。
直觉上为什么？因为在异步网络里，一个迟迟不回话的进程，可能是崩溃了，也可能只是消息在路上。算法被迫陷入两难：
- 如果它选择"不等了，先决定"——万一那个进程其实活着、且持不同意见，就违反一致性。
- 如果它选择"再等等"——万一那个进程真的崩了，就永远等下去，违反终止性。
FLP 的证明用了一个精巧的论证：总存在某种"恰到好处"的消息调度，让系统永远卡在"还没决定"的状态（称为 bivalent，二值待定态）。注意这个结论的精确含义——它说的是没有算法能在所有情况下保证终止，而不是说"系统总会卡死"。
核心二：如何"绕过"FLP
FLP 说异步确定性共识不可能。现实中的系统（数据库、区块链、协调服务）却天天在做共识。它们靠的是放松前提，从三个方向之一突围：
- 引入时间假设（部分同步）：现实网络大多数时候是好的。如果假设"消息延迟终究有个上界"（即便不知道具体是多少），共识就重新可能。这是 Paxos、Raft 等工程协议的立足点——它们牺牲了"最坏情况下的终止性"，换来实际中几乎总能终止。
- 引入随机性：让进程抛硬币来打破对称。随机化共识协议（Ben-Or 1983 是先驱）可以做到"以概率 1 终止"，绕开了 FLP 对确定性算法的限制。这与随机化算法（见 randomized-algorithms）绕开确定性下界的思路一脉相承。
- 引入故障检测器：假设系统能（哪怕不完美地）侦测哪些进程崩了。Chandra 与 Toueg（1996）刻画了"解决共识所需的最弱故障检测器"，把 FLP 重新表述为一个关于"系统能获得多少同步信息"的问题。
核心三：拜占庭将军问题——当节点会作恶
FLP 设定里的故障是"崩溃停机"——出错的进程只是安静地死掉。但有些进程可能更坏：它们会撒谎，向不同的人发不同的消息，甚至串谋。
1982 年，莱斯利·兰波特（Leslie Lamport）、罗伯特·肖斯塔克（Robert Shostak）、马歇尔·皮斯（Marshall Pease）把这种最恶劣的故障形式化为拜占庭将军问题（发表于 ACM TOPLAS）。
比喻是这样的：拜占庭帝国的几位将军围攻一座城，必须协同决定"进攻"还是"撤退"。他们只能靠信使沟通。但其中可能混有叛徒，叛徒会故意向不同将军传递相反的命令，制造混乱。忠诚的将军们如何仍能达成一致的行动？
他们证明了一个干净利落的下界：在不能验证消息真伪（口头消息）的前提下，要容忍 $f$ 个叛徒，至少需要 $3f+1$ 个将军（即叛徒数必须严格少于总数的三分之一）。直觉是：忠诚者必须能"投票压倒"叛徒制造的两种矛盾信息，而 $3f+1$ 恰好是让多数派稳定存在的临界点。
一个推论很重要：如果消息可以被数字签名（叛徒无法伪造别人的签名），下界就被打破了——签名让谎言可追溯，从而能容忍更多故障。这正是现代区块链（见 blockchain）能在公开网络上运作的密码学前提。
核心四：Paxos 与 Raft——把理论变成可运行的协议
FLP 关上了一扇门，工程师们从"部分同步"那扇窗爬了进去。
Paxos（兰波特，《The Part-Time Parliament》，1998 年发表于 ACM TOCS）是第一个被严格证明正确的实用共识协议。它保证：只要网络最终稳定下来、且多数派进程存活，系统就能就一个值达成共识。Paxos 以晦涩难懂著称——兰波特用了一个虚构的希腊议会故事来讲解，反而让一代工程师望而生畏。
正因如此，2014 年迭戈·翁加罗（Diego Ongaro）和约翰·欧斯特豪特（John Ousterhout）提出了 Raft（论文标题就叫《寻找一个可理解的共识算法》，获 USENIX ATC 最佳论文）。Raft 在能力上等价于 Paxos，但通过明确的"领导者选举 + 日志复制"结构，把共识讲清楚了。今天 etcd、Consul 等关键基础设施都建立在 Raft 之上。
这两个协议都依赖多数派（quorum）机制：任意两个多数派必然有交集，这个交集就是信息得以传递、避免脑裂的保证。
核心五：CAP 定理——一致性与可用性的取舍
2000 年，埃里克·布鲁尔（Eric Brewer）在 PODC 的主题演讲中提出了一个猜想，2002 年由塞思·吉尔伯特（Seth Gilbert）和南希·林奇严格证明，成为 CAP 定理。
它说：一个分布式数据系统，在以下三者中最多只能同时满足两个：
- 一致性（Consistency）：所有节点在同一时刻看到相同的数据。
- 可用性（Availability）：每个请求都能得到（非错误的）响应。
- 分区容忍性（Partition tolerance）：网络被切断成几块时系统仍能工作。
现实中，网络分区（Partition）迟早会发生，你无法选择不要它。所以真正的取舍发生在分区出现的那一刻：要么拒绝服务以保数据一致（CP，如传统数据库），要么继续响应但可能返回过期数据（AP，如很多 NoSQL）。
CAP 常被通俗化为"三选二"，但这是简化。更准确的说法是：当且仅当分区发生时，你必须在 C 和 A 之间二选一；没有分区时，两者可以兼得。这也是为什么后来出现了 PACELC 等更细致的表述。
核心六：逻辑时钟——没有全局时间，如何排序事件
分布式系统没有一座所有机器共享的时钟。那"事件 A 发生在事件 B 之前"该如何定义？
兰波特 1978 年的论文《Time, Clocks, and the Ordering of Events in a Distributed System》给出了奠基性答案：放弃物理时间，改用因果关系。他定义了"先发生于"（happens-before）关系——只有当 A 可能影响到 B 时，才说 A 先于 B；互不影响的事件则是"并发"的，没有先后。
由此引出逻辑时钟（Lamport timestamps）和更精细的向量时钟（vector clocks），它们用计数器而非真实时间来给事件排序。这是该领域引用量最高的论文之一，也是几乎所有分布式数据库追踪因果一致性的理论起点。
代价与争议
理论与实践的鸿沟：FLP、CAP 这些不可能性结果，刻画的是"绝对保证"。工程系统活在"绝大多数时候"的世界里——它们用超时、重试、概率把不可能性的概率压到足够低，但永远无法降到零。理解这条边界，能让你对任何声称"既强一致又高可用还永不宕机"的系统保持健康的怀疑。
一致性模型的光谱：在强一致性（线性一致性）与最终一致性之间，存在一整条光谱（因果一致性、读己之写等）。选哪种不是技术问题，而是业务问题——银行转账和点赞计数，对一致性的要求天差地别。
区块链的再发明：比特币（2008）被很多人当作全新发明，但它本质上是拜占庭容错共识在"开放、无需许可、有经济激励"环境下的一个变体。它用工作量证明替代了对参与者身份的假设，代价是巨大的能耗与较弱的终局性保证。理论界对"它是否真正解决了经典共识问题"至今有细致争论。
跨域连接
- 可计算性理论：两者同属不可能性定理家族，但不可能的来源不同。停机问题的根在自指，异步共识的根在信息不对称：无法区分一个进程崩了还是消息还在路上。因此绕开的方式也不同——前者无路可绕，后者只要给系统补上一点时间假设或随机性就能重新可能。
- 狭义相对论：没有全局时钟时，先后只能由因果定义：只有可能传递过信息的两个事件才有先后，其余是并发。这与光锥内外的划分是同构的——绝对的先后只存在于因果可达的事件之间。要强调的是结构相同而非同一回事：这里的限速是消息延迟，不是光速。
- 密码学基础：容忍作恶节点的经典下界建立在"消息无法验证真伪"这一前提上。一旦引入数字签名，谎言变得可追溯，下界随之被改写——密码学在这里不是加了一层防护，而是换掉了模型的假设，从而改变了可达的容错比例。
- 社会选择理论：共识要求的一致、有效、终止三条，与偏好聚合公理在结构上同型：几条各自看来温和的要求，被证明不能同时满足。两边的出路也一样——放宽某一条，或者限制输入的范围，而不是寻找更聪明的算法。
- 区块链：在开放网络里连"有多少参与者"都无法认定，于是身份假设被换成了资源与激励。代价明确：能耗巨大，且终局性只能是概率性的——不是"已确认"，而是"被推翻的概率随时间下降"。
参考文献
- Fischer, M. J., Lynch, N. A., Paterson, M. S. Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM 32(2) (1985): 374–382.（FLP 原始论文）
- Lamport, L., Shostak, R., Pease, M. The Byzantine Generals Problem. ACM TOPLAS 4(3) (1982): 382–401.
- Lamport, L. Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM 21(7) (1978): 558–565.
- Lamport, L. The Part-Time Parliament. ACM Transactions on Computer Systems 16(2) (1998): 133–169.（Paxos）
- Ongaro, D., Ousterhout, J. In Search of an Understandable Consensus Algorithm. USENIX ATC (2014).（Raft）
- Gilbert, S., Lynch, N. Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. ACM SIGACT News 33(2) (2002): 51–59.（CAP 定理证明）
- Lynch, N. A. Distributed Algorithms. Morgan Kaufmann (1996).（领域权威教材）