FLP、CAP 与不可能性结果：被误读的三座里程碑

你大概率在面试或技术博客里见过这两个说法：

• “FLP 不可能定理证明了异步系统中共识不可能达成。”
• “CAP 定理说分布式系统只能三选二。”

但 Raft 跑在”异步”网络上，共识达成得好好的——etcd 集群每天处理数百万次写入，没有违反物理定律。Spanner 声称同时提供外部一致性（比线性一致性更强）和高可用性，Google 也没被理论计算机科学家找上门。

矛盾在哪？

不在定理本身。FLP 和 CAP 都是经过严格证明的数学定理，它们不可能”错”。矛盾在于：大多数工程师（包括不少写教材的人）在引用这些定理时，跳过了精确的前提条件和术语定义。“异步”到底是什么意思？“一致性”指的是哪种一致性？“可用”的标准是什么？这些细节决定了定理是否适用于你面前的系统。

这篇文章做一件事：回到原始论文，把四个不可能性结果的精确陈述、证明直觉和工程含义逐一拆清楚。不是为了背诵定理，而是为了理解分布式系统的理论边界到底画在哪里——以及工程师如何在边界内做出正确的取舍。

一、FLP 不可能定理

背景与精确陈述

1985 年，Michael Fischer、Nancy Lynch 和 Michael Paterson 发表了论文”Impossibility of Distributed Consensus with One Faulty Process”。这篇论文获得了 2001 年 Dijkstra 奖，被认为是分布式计算理论的奠基性结果之一。

FLP 定理的精确陈述需要先定义模型：

系统模型：N 个进程（Process）（N >= 2）通过异步消息传递（Asynchronous Message Passing）通信。“异步”在这里有严格含义：

• 消息传递延迟没有上界——一条消息可能 1 毫秒送达，也可能 1 小时送达，协议不能假设任何时间限制。
• 进程的相对执行速度没有上界——一个进程可能跑得比另一个快一万倍。
• 没有全局时钟，没有超时机制。

故障模型：最多有 1 个进程可能发生崩溃故障（Crash Failure）——进程停止执行，不再发送消息，但不会发送错误消息（没有拜占庭行为）。

共识问题的定义：每个进程有一个输入值（0 或 1），需要决定（Decide）一个输出值，满足三个性质：

FLP 定理：在上述纯异步模型中，即使最多只有 1 个进程可能崩溃，也不存在一个确定性协议能同时满足一致性、有效性和终止性。

注意每一个限定词：纯异步、确定性、1 个崩溃。去掉任何一个，定理就不成立。这正是 FLP 之后三十年共识研究的突破口。

证明直觉：二值性与对手调度

FLP 的证明精巧而反直觉。核心思路是构造一个”对手”（Adversary），它通过控制消息的送达顺序，让任何确定性协议永远无法做出决定。

首先定义几个概念：

配置（Configuration） 是系统在某一时刻的全局快照：所有进程的内部状态，加上所有正在传输中的消息。

步骤（Step） 是一个原子事件：某个进程收到某条消息（或者一个特殊的”空消息”表示没有新消息到达），然后根据协议规则更新自己的状态并发送新消息。

从一个配置出发，不同的步骤顺序会导致不同的后续配置。所有可达的配置形成一棵树（或者说有向无环图）。

现在看这棵树上的每个配置节点：

• 0-valent 配置：从这个配置出发，无论后续步骤怎么走，最终只能决定 0。
• 1-valent 配置：从这个配置出发，无论后续步骤怎么走，最终只能决定 1。
• 二值配置（Bivalent Configuration）：从这个配置出发，既存在一条路径最终决定 0，也存在一条路径最终决定 1。决定值尚未确定。

证明分两步：

第一步（引理 2）：存在一个初始二值配置。

直觉是这样的：如果所有进程的输入都是 0，协议必须决定 0（有效性要求）。如果所有进程的输入都是 1，协议必须决定 1。从”全 0”到”全 1”，我们可以逐个翻转进程的输入值。每翻一次，决定值要么还是 0，要么变成了 1。一定存在某一次翻转是”临界点”——翻转前决定 0，翻转后决定 1。在这个临界点上，如果被翻转的那个进程恰好在第一步之前就崩溃了（它还没来得及告诉任何人自己的输入值），剩下的进程面对的局面是相同的，但协议却应该给出不同的决定。这就意味着这个初始配置必须是二值的——两种决定值都有可能。

第二步（引理 3）：从任何二值配置出发，对手总能找到一步，使得系统进入另一个二值配置。

这是证明的核心。假设 C 是一个二值配置，e 是某个待处理的事件（某个进程即将收到的消息）。对手考虑所有可能的调度顺序。如果不管怎么调度，应用 e 之后都进入单值配置，那么必定存在两个”相邻”的配置（只差一步），一个是 0-valent，一个是 1-valent。但在异步模型中，这两个配置之间的差异只取决于一个进程的一步操作。如果这个进程恰好崩溃了，剩下的进程无法区分这两种情况——一个应该决定 0，一个应该决定 1，矛盾。所以假设不成立，对手一定能找到一条通往二值配置的路径。

把两步合在一起：从初始二值配置开始，对手可以无限地让系统停留在二值状态，永远不做出决定。终止性被违反了。

这个证明有一个精妙之处：对手不需要做任何”恶意”的事情。它只是合法地延迟消息——在异步模型中，任意长的延迟都是允许的。对手利用的正是”异步”这个假设。

FLP 之后：共识为什么没有死

FLP 发表时，很多人以为共识问题已经被判了死刑。但实际上，FLP 做的是划出一条精确的边界线，而工程师的工作就是在边界线的另一边找到立足点。三条路线分别放松了 FLP 的一个前提假设：

路线一：部分同步模型（Partial Synchrony）。 Dwork、Lynch 和 Stockmeyer 在 1988 年提出了部分同步模型：存在一个未知的全局稳定时间（Global Stabilization Time，GST），GST 之后，所有消息都会在有界延迟 Delta 内送达。在 GST 之前，系统表现得像纯异步——消息可以任意延迟。

Paxos 和 Raft 都工作在部分同步模型中。它们保证安全性（Agreement + Validity）在任何情况下都成立——即使网络完全异步。但终止性（Liveness）只在 GST 之后才保证：如果网络长时间无法送达消息，Raft 的选举会反复超时，系统停滞，但不会做出错误的决定。

这就回答了开头的问题：Raft 没有违反 FLP，因为 FLP 说的是纯异步模型。Raft 的 election timeout 把系统从纯异步拉到了部分同步——它假设网络最终会恢复到消息能在有限时间内送达的状态。在纯异步的极端情况下（消息永远不送达），Raft 确实不保证终止。这不是 bug，是设计。

路线二：随机化。 1983 年，Michael Ben-Or 证明了：如果允许进程抛硬币（使用随机数生成器），共识可以在异步系统中以概率 1 终止。协议不再是确定性的——FLP 只排除了确定性协议。随机化共识的期望轮次数虽然可能很高，但终止概率随轮次趋近于 1。

路线三：故障检测器（Failure Detector）。 1996 年，Chandra 和 Toueg 提出了故障检测器抽象。故障检测器是一个”预言机”（Oracle），它告诉进程”谁可能崩溃了”。关键在于，故障检测器不需要完美——它可以误报（把活着的进程报告为崩溃），也可以漏报（没检测到真正崩溃的进程），只要最终能收敛到正确的判断就行。

Chandra-Toueg 的核心结果：一个叫 Diamond-P（最终完美故障检测器）的故障检测器，加上异步消息传递，就足以解决共识问题。Diamond-P 的要求是：最终（从某个时间点开始），它不再误报，也不再漏报。

工程上的超时机制——“如果 500ms 没收到心跳就认为对方挂了”——就是一个不完美的故障检测器。它可能误判（网络抖动时），但在网络稳定后最终会变准确。这和 Diamond-P 的假设吻合。

值得深入理解的是故障检测器如何从形式上绕过 FLP。FLP 证明了在纯异步模型中——没有任何故障检测能力——共识不可能达成。Chandra 和 Toueg（1996）的关键洞察在于：如果我们用一个外部的故障检测器预言机来增强异步模型，共识就变得可解。故障检测器不需要嵌入系统模型本身，它是一个独立的抽象层，为进程提供关于其他进程存活状态的（可能不准确的）信息。这种分离使得我们可以精确地刻画”解决共识到底需要多强的故障检测能力”。

Chandra、Hadzilacos 和 Toueg 建立了一个故障检测器的层级结构，按检测能力从强到弱排列：

• P（完美故障检测器）：完备（Complete）且准确（Accurate）——每个崩溃的进程最终都会被检测到，且永远不会误报存活的进程。P 只在同步系统中才能实现，因为它要求消息延迟有已知上界。
• ◇P（最终完美故障检测器）：最终完备且最终准确——可能在一段时间内犯错（误报存活进程为崩溃，或漏报已崩溃的进程），但从某个时间点开始，它的判断将完全正确。这正是前面提到的 Diamond-P。
• ◇S（最终强故障检测器）：比 ◇P 更弱。它只保证两件事：最终完备（每个崩溃进程最终被某个正确进程怀疑），以及最终存在某个正确进程永远不被任何正确进程怀疑。
• Omega（最终领导者预言机）：最弱的一类。它只提供一个保证：最终所有正确进程就同一个正确进程达成一致，将其视为”领导者”。在收敛之前，不同进程可能认为不同的进程是领导者。

graph TD
    P["P（完美故障检测器）<br/>完备 + 准确<br/>仅同步系统可实现"]
    DP["◇P（最终完美故障检测器）<br/>最终完备 + 最终准确<br/>可能暂时犯错"]
    DS["◇S（最终强故障检测器）<br/>最终完备 + 最终存在不被怀疑的正确进程"]
    OM["Omega（最终领导者预言机）<br/>最终所有正确进程同意同一个领导者<br/>解决共识的最弱充分条件"]

    P -->|"放松准确性<br/>允许暂时误报"| DP
    DP -->|"放松准确性<br/>只需一个不被怀疑"| DS
    DS -->|"进一步抽象<br/>只关心领导者选举"| OM

    style P fill:#e8f4f8,stroke:#2c3e50,stroke-width:2px
    style DP fill:#e8f4f8,stroke:#2c3e50,stroke-width:2px
    style DS fill:#e8f4f8,stroke:#2c3e50,stroke-width:2px
    style OM fill:#fdebd0,stroke:#e67e22,stroke-width:2px

这个层级从上到下逐步放松对故障检测准确性的要求。关键结论是：Omega 是能够解决共识问题的最弱故障检测器类别（Chandra、Hadzilacos、Toueg，1996）。这意味着共识问题在故障检测器的意义上与领导者选举”等价”——任何能解决共识的故障检测器都至少和 Omega 一样强。从工程角度看，Raft 的领导者选举机制本质上就是在实现 Omega：当网络稳定之后（即超过全局稳定时间 GST），所有 follower 通过超时和投票机制最终同意同一个 leader——这恰恰是 Omega 所提供的保证。

工程含义：不是”不可能”，而是”必须取舍”

FLP 对工程师的真正信息不是”共识不可能”，而是：

在异步系统中，确定性共识协议不可能同时保证安全性和活性。你必须在两者之间做出选择。

几乎所有实际的共识系统都选择了同一侧：永远保证安全性，在网络条件允许时提供活性。 这意味着：

• 网络正常时，系统正常工作，共识在几个 RTT 内达成。
• 网络分区或严重延迟时，系统可能暂停（不接受新的写入），但绝不会返回不一致的结果。

etcd 的行为就是这样：少数派分区里的节点停止接受写入，等待重新加入多数派。数据安全，但该分区内的客户端在分区期间无法写入。这是 FLP 告诉我们的工程代价，不是 Raft 的实现缺陷。

FLP 定理的精确条件也暗示了另一个工程判断：如果你的系统部署在一个网络延迟有实际上界的环境中（比如同一个数据中心、同一个机架），那么”纯异步”的假设过于悲观。你面对的更接近部分同步模型，共识的终止性有更强的保障。反过来，如果你的系统需要跨越不可靠的广域网（海底光缆可能被切断），FLP 的警告就更值得认真对待。

二、CAP 定理

Brewer 猜想（2000）与 Gilbert-Lynch 证明（2002）

2000 年，Eric Brewer 在 PODC 会议的主题演讲中提出了一个猜想：分布式系统不可能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition Tolerance）三个性质——最多只能满足其中两个。

这就是广为流传的”三选二”。

两年后，Seth Gilbert 和 Nancy Lynch 在论文”Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services”中给出了形式化证明。但 Gilbert-Lynch 的证明和 Brewer 的演讲说的不是同一件事——证明中的每个术语都有精确的数学定义，而 Brewer 的猜想是用自然语言表述的，留下了大量解释空间。

工程师社区记住了 Brewer 的”三选二”口号，但很少回去读 Gilbert-Lynch 的精确定义。这是 CAP 被大规模误读的根源。

精确陈述

Gilbert-Lynch 证明中的三个性质定义如下：

一致性（Consistency）：这里的 C 不是数据库 ACID 里的 C（事务一致性），也不是”最终一致性”的反义词。Gilbert-Lynch 的 C 是线性一致性（Linearizability）——也称为原子一致性（Atomic Consistency）。线性一致性要求：对一个读写寄存器的所有操作，存在一个全局的线性顺序，这个顺序和每个操作的实际时间区间相容，并且每次读操作返回最近一次写操作的值。

这是一个非常强的一致性模型。大多数被称为”一致”的系统并不提供线性一致性——它们可能提供顺序一致性（Sequential Consistency）、因果一致性（Causal Consistency）或会话保证（Session Guarantees）。CAP 的 C 不涵盖这些较弱的模型。

可用性（Availability）：每一个发到非故障节点的请求，都必须收到一个（非错误的）响应。注意两个关键点：第一，“每一个”——不是 99.99%，是 100%。第二，没有时间限制——响应可以慢，但必须最终到来。

这比工程师通常理解的”高可用”严格得多。如果一个系统在分区期间让某些节点返回错误或超时，按 CAP 的定义，它就不”可用”——即使它的 SLA 还是 99.99%。

分区容错性（Partition Tolerance）：网络可以丢失任意多的消息——也就是说，任意两个节点之间的通信可能被切断。

CAP 定理：在异步网络模型中，不存在一个读写存储系统能同时保证线性一致性和可用性（在可能发生网络分区的前提下）。

“三选二”的三重误读

“三选二”这个口号流行了二十年，但它至少在三个地方误导了工程师。

误读一：分区是一个可以”选择”的选项。

“三选二”暗示你可以选 CA（一致性 + 可用性，放弃分区容错）、CP（一致性 + 分区容错）或 AP（可用性 + 分区容错）。但网络分区不是你选择的——它是发生在你身上的事情。光缆被挖断、交换机故障、路由表错误——这些不是设计决策。

在分布式环境中（进程运行在不同的机器上），分区是必然会发生的。所谓”CA 系统”只在单机或严格不分区的网络中才有意义。一旦你把数据放到多台机器上，P 就不是可选项，而是前提条件。

真正的问题是：当分区发生时，你牺牲 C 还是 A？

误读二：CAP 的 C 代表”一致性”。

很多文章在讨论 CAP 时，把 C 等同于笼统的”一致性”。这导致了诸如”Cassandra 是 AP 系统所以不一致”的说法。实际上，Cassandra 在没有分区时可以提供因果一致性或 quorum 读的强一致性——这些只是不满足线性一致性这一个特定模型。

如果你的系统需要的是因果一致性而不是线性一致性，CAP 定理根本没有限制你。它画的那条线，比很多人以为的要窄得多。

误读三：CAP 的 A 是”系统大部分时间能用”。

CAP 中的可用性是一个极端定义：所有非故障节点的所有请求都必须收到响应。如果你的系统在分区期间让少数派分区的节点拒绝服务（像 Raft 那样），按 CAP 的定义它就不可用——尽管多数派分区内的客户端还能正常读写。

工程上的可用性（SLA、可用百分比、P99 延迟）和 CAP 的可用性是不同的概念。Spanner 的”高可用”是工程意义上的：Google 的专用网络让分区极其罕见，所以 Spanner 在实践中几乎总是可用。但按 CAP 的严格定义，Spanner 在分区发生时会牺牲可用性（某些请求会超时），它是 CP 系统。Spanner 没有违反 CAP，它只是让 P 几乎不发生。

Brewer 本人在 2012 年发表了”CAP Twelve Years Later: How the ‘Rules’ Have Changed”一文，承认”三选二”的表述具有误导性。他指出，CAP 的实际含义更接近：在分区持续的时间窗口内，系统需要在一致性和可用性之间做出权衡；分区结束后，系统需要恢复到一致状态。这是一个动态的、有时间维度的权衡，不是一个静态的”三选二”。

关于 CAP 的更深入讨论，可以参考 CAP 的谎言与真相。

PACELC：更实用的权衡框架

CAP 有一个明显的盲区：它只讨论分区发生时的取舍，但现实中大多数时间网络是正常的。正常运行时，系统的设计选择是什么？

Daniel Abadi 在 2012 年提出了 PACELC 框架来填补这个空白：

• Partition 时，选择 Availability 还是 Consistency？
• Else（正常运行时），选择 Latency 还是 Consistency？

PACELC 比 CAP 更接近工程现实，因为它承认了两个事实：第一，分区是偶发事件，不是常态；第二，即使没有分区，一致性也是有代价的——代价就是延迟。提供线性一致性的系统（例如 Spanner）需要跨节点协调，这不可避免地增加延迟。提供最终一致性的系统（例如 Dynamo）可以本地响应，延迟更低。

用 PACELC 框架来分类常见系统：

PACELC 不是定理，而是分类框架。它的价值在于：迫使设计者回答两个问题，而不是一个。仅回答”分区时怎么办”是不够的——正常运行时的延迟/一致性取舍，才是影响日常用户体验的主要因素。

三、共识数与等待自由层级

Herlihy 1991：同步原语的能力边界

1991 年，Maurice Herlihy 发表了论文”Wait-Free Synchronization”，提出了一个根本性的问题：不同的共享对象（Shared Object），在构建并发数据结构时的能力有没有本质差异？

答案是有，而且差异是不可逾越的。

等待自由（Wait-free） 是并发算法的一种进度保证：每个进程在有限步内完成操作，无论其他进程的执行速度如何——即使其他进程全部停滞。这是最强的进度保证，比无锁（Lock-free）更强。

共识数（Consensus Number） 的定义：一个共享对象的共识数是 n，如果用这种对象（加上原子读写寄存器）可以为 n 个进程实现等待自由的共识，但不能为 n+1 个进程实现。

Herlihy 证明了一个层级结构：

这个层级是严格的：共识数为 n 的对象不能为 n+1 个进程实现等待自由共识，无论你多聪明都不行。这不是工程限制，而是数学证明。

用具体例子来感受这个层级的含义：

读写寄存器（共识数 1）：假设两个进程 A 和 B 试图仅用原子读写操作达成共识。A 写入 0，B 写入 1。无论谁最后读，都能看到对方的值，但问题在于——没有原子的方式来”判定胜负”。最后一个写入者覆盖了前一个的值，而”输家”无法分辨自己是否输了，因为读和写是两个独立的步骤，中间可能被其他操作插入。对于两个进程的共识问题，读写寄存器就已经无能为力。

队列（共识数 2）：两个进程可以用一个 FIFO 队列解决共识。协议很简单：两个进程各自将自己的提议值入队（enqueue），然后各自出队（dequeue）。第一个被出队的值就是共识决定——因为 FIFO 保证了全局顺序，两个进程出队的第一个值必然相同。但这个方法无法扩展到三个进程：第三个进程无法仅通过队列操作确定前两个进程的操作的相对顺序，因为它看到的出队序列取决于它自己入队的时机。

比较并交换 CAS（共识数无穷大）：CAS 可以为任意数量的进程解决共识。每个进程执行 CAS(shared_var, initial_value, my_proposal)。恰好有一个进程成功（第一个执行 CAS 的），其余所有进程的 CAS 失败并读到胜者的值。成功者知道自己赢了，失败者知道自己输了并且知道决定值是什么——这是一个通用的共识对象。

这个层级是严格的且经过数学证明的：没有任何算法上的巧妙设计能让共识数为 1 的对象解决两个进程的共识问题。这是计算的基本限制，不是工程能力的不足。

CAS 的无穷共识数意味着什么

比较并交换（Compare-and-Swap，CAS）的共识数是无穷大——它可以为任意数量的进程实现等待自由共识。这使得 CAS 成为一个通用（Universal） 的同步原语：任何共享对象都可以用 CAS 实现等待自由版本。

这就是为什么现代 CPU 架构（x86 的 CMPXCHG、ARM 的 LDXR/STXR 即 LL/SC）都提供 CAS 或等价的原子操作。不是因为 CAS 方便，而是因为没有它，很多并发数据结构在理论上就无法实现。

工程上的体现随处可见：

• Java 的 java.util.concurrent.atomic 包建立在 CAS 之上。
• Go 的 sync/atomic 提供 CompareAndSwap 系列函数。
• Linux 内核的无锁数据结构大量使用 cmpxchg。
• 无锁队列、无锁哈希表、无锁跳表——所有这些数据结构的正确性都依赖于 CAS 的无穷共识数。

反过来看：如果你只有原子读写寄存器（共识数 1），连两个进程的共识都实现不了。这就是为什么纯粹基于读写操作的并发算法（比如 Peterson 算法）只能处理两个进程的互斥，而不能扩展到 n 个进程的共识。

Herlihy 的结果和 FLP 有一个有趣的对照：FLP 讲的是消息传递模型中的不可能性，Herlihy 讲的是共享内存模型中的不可能性。两者从不同角度刻画了分布式计算的能力边界。消息传递模型中，瓶颈是异步性和故障；共享内存模型中，瓶颈是同步原语的强弱。

四、收割与产出

从二元到连续

1999 年，Armando Fox 和 Eric Brewer（对，就是 CAP 的 Brewer）发表了”Harvest, Yield, and Scalable Tolerant Systems”。这篇论文比 CAP 猜想早一年，却提出了一个在工程上更实用的视角：可用性和一致性不是全有全无的，而是可以在一个连续光谱上调节的。

两个核心概念：

产出（Yield）：请求被成功完成的概率。接近于工程上的可用性百分比，但更侧重于从用户请求的角度看——发出的请求有多大比例得到了完整响应？

收割（Harvest）：响应的数据完整性。如果一个查询应该检索 100 个分片的数据，但有 2 个分片不可达，系统返回了 98 个分片的结果，那么 harvest = 98%。

CAP 把可用性看作二元的（可用或不可用）。Fox-Brewer 的框架把它拆成了两个连续维度：你的系统在多大概率上能响应（yield），以及响应的数据有多完整（harvest）。

现代系统在光谱上的位置

这个框架的实用性在于：大多数系统的故障应对策略不是”整体不可用”或”返回错误数据”，而是在 harvest 和 yield 之间做局部交换。

搜索引擎是典型例子。Google 搜索的某个索引分片挂了，搜索服务不会返回错误——它返回剩余分片的结果。用户拿到的结果可能不完整（harvest 降低），但请求被成功响应了（yield 维持）。大多数用户甚至不会注意到少了几条结果。

购物车是另一个例子。Amazon 的 Dynamo 论文描述了这种场景：网络分区时，购物车服务允许在两个分区中分别接受写入（高 yield），分区恢复后合并冲突。合并过程可能导致已删除的商品重新出现（harvest 临时降低），但 Amazon 认为”多加一件商品”比”购物车不可用”的代价小得多。

对比 CAP 和 harvest/yield 的视角：

从工程设计的角度，harvest/yield 框架比 CAP 更有操作性。它促使设计者问正确的问题：不是”我的系统是 CP 还是 AP”，而是”对于这个具体的功能，在故障场景下，我愿意牺牲多少数据完整性来换取多少可用性？”

五、四个结果的工程综合

回到开头的两个矛盾。

Raft 跑在”异步网络”上但共识达成得好好的——因为 Raft 不在纯异步模型中工作。它通过 election timeout 引入了时间假设，把系统模型从纯异步推到了部分同步。在这个模型中，FLP 不适用。代价是：如果网络真的长时间不可用（纯异步的极端情况），Raft 停止服务。安全性不丢，活性暂停。

Spanner 声称兼得一致性和可用性——因为 Spanner 的”可用”是工程意义上的（SLA 99.999%），不是 CAP 定义的”所有非故障节点 100% 响应”。Spanner 在分区发生时确实会牺牲可用性。Google 的做法是让分区几乎不发生（专用网络、冗余链路），而不是绕过 CAP。

四个不可能性结果画出了分布式系统的理论边界。对工程师来说，它们的价值不在于告诉你”什么做不到”，而在于告诉你”做到这个目标的代价是什么”：

• FLP 说：异步 + 确定性 + 安全性 + 活性不能兼得。工程选择：放弃纯异步（引入部分同步），或放弃确定性（引入随机化），或引入故障检测器。
• CAP 说：分区期间，线性一致性和完全可用性不能兼得。工程选择：明确你在分区时牺牲哪一个——或者用 PACELC 框架思考正常运行时的延迟/一致性取舍。
• 共识数 说：同步原语有能力层级，读写寄存器做不了的事情再聪明也没用。工程选择：需要等待自由的并发结构时，确保底层硬件提供了足够强的原子操作（CAS / LL-SC）。
• Harvest/Yield 说：可用性和一致性是连续光谱，不是二选一。工程选择：按功能、按场景分别设定 harvest 和 yield 的目标，不要一刀切。

理论边界是固定的——数学证明不会因为工程需求而改变。但边界内的设计空间是巨大的。理解这些定理的精确条件，就是理解这个设计空间的边界在哪里。不多，不少。

参考资料

论文

• Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson. “Impossibility of Distributed Consensus with One Faulty Process.” Journal of the ACM, 32(2):374-382, 1985. (FLP 不可能定理原始论文)
• Seth Gilbert, Nancy Lynch. “Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services.” ACM SIGACT News, 33(2):51-59, 2002. (CAP 定理形式化证明)
• Eric Brewer. “CAP Twelve Years Later: How the ‘Rules’ Have Changed.” IEEE Computer, 45(2):23-29, 2012. (Brewer 对 CAP 的重新解读)
• Armando Fox, Eric Brewer. “Harvest, Yield, and Scalable Tolerant Systems.” Proceedings of the 7th Workshop on Hot Topics in Operating Systems (HotOS), 1999. (Harvest/Yield 框架)
• Maurice Herlihy. “Wait-Free Synchronization.” ACM Transactions on Programming Languages and Systems, 13(1):124-149, 1991. (等待自由层级与共识数)
• Daniel Abadi. “Consistency Tradeoffs in Modern Distributed Database System Design.” IEEE Computer, 45(2):37-42, 2012. (PACELC 框架)
• Cynthia Dwork, Nancy Lynch, Larry Stockmeyer. “Consensus in the Presence of Partial Synchrony.” Journal of the ACM, 35(2):288-323, 1988. (部分同步模型)
• Tushar Deepak Chandra, Sam Toueg. “Unreliable Failure Detectors for Reliable Distributed Systems.” Journal of the ACM, 43(2):225-267, 1996. (故障检测器与共识)
• Michael Ben-Or. “Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols.” Proceedings of the 2nd ACM Symposium on Principles of Distributed Computing, 1983. (随机化共识)

演讲

• Eric Brewer. “Towards Robust Distributed Systems.” Keynote at ACM Symposium on Principles of Distributed Computing (PODC), 2000. (CAP 猜想首次提出)

上一篇：分布式系统模型 | 下一篇：故障的分类学