Gilbert–Lynch 2002：异步网上原子寄存器无法既可用又抗分区

破除误解：三选二不是开关，C 也不是事务#

第一层误解把猜想听成「一致性、可用性、分区容错，请永远选出两个」。布鲁尔 2000 年在 PODC 的受邀报告里，确实用过这三句口号。吉尔伯特与林奇把它收成一句关于执行集合的话：算法必须在包含消息丢失的公平执行上同时给出原子响应与终止。分区不是第三种你可以关掉的功能，而是环境被允许做的事。若正确性暗中依赖「邮件终将双方送达」，实现就没有抗分区。把「三选二」读成数据表上的两列表头，等于把全称量词收成一次采购。

第二层误解把 C 听成 数据库事务 里的 ACID，或听成「所有副本字节相同」。论文脚注写得很清楚：原子一致性谈的是单次请求—响应，不是多语句事务；它与 ACID 里那个 Atomic 也不是同一个词。他们选用的规格是原子对象，也就是 线性化 的读写寄存器：必须存在一种把全部操作收成单副本顺序的讲法，并且不相交的实时区间不得颠倒。写已经返回之后才开始的读，不得交回写之前的值。会话一致、读己之写、最终可见，都是后来更弱的合同，不是本页的 C。

第三层误解把 A 听成机房里的可用性百分比，或听成「集群里至少有一台还能 ping」。论文的可用性是：非故障节点收到的每一个请求，都必须产生一个响应；算法必须终止。它不给响应时间上界，所以单独看是弱的。一旦叠上分区许可，它又变强：哪怕对侧邮件全部丢掉，接到请求的那一侧仍须回答。布鲁尔口头上曾经允许「几乎所有请求」得到响应；吉尔伯特与林奇写成百分之百，并注明在任意故障模式下，把可用性改成概率并不改变结论。把这句话读成 SLA，类型就错了。

第四层误解把异步结果听成「网络一好，C 与 A 就能兼得」。那是后来口头传播里最常见的口号，也是部分同步里超时开始合法之后才近似成立的话。论文有一条推论 1.1：在完全异步里，若要求所有公平执行都可用，那么即便只要求「消息其实都送到的那些执行」保持原子，也做不到。原因是算法分不清「信丢了」与「信还在路上」。若某条坏执行里已经写出不原子的答案，你可以事后把尚未投递的信补送完，得到一条「其实没有永久丢失」的公平执行，答案却已经写坏。于是「没有分区就能兼得」在无钟模型里并不成立。钟与已知时限把这句话救回来，那是后文的模型更换，不是定理 1 的内容。

第五层误解把 CAP 与 FLP 收成同一条不可能。FLP 禁止的是完全异步下确定性共识的终止，故障是一次干净停机，信道对正确进程终将投递。本页几乎不谈停机；分区被写成组件之间的邮件丢失。对象是原子寄存器的读与写，不是就一个比特达成一致。用共识去实现线性化对象，是后来状态机复制的工程路线，会把活性再次交给多数派是否同侧；那条路线不是 2002 年的证明。本页也不把 Dynamo 的最终一致写成定理的「反例」：它换的是规格，不是推翻量词。

模型与证明：无钟、原子寄存器、两组之间的邮件#

装置从一份读写对象开始。客户端把读或写交给某个节点，节点可以互相发信，最后必须给客户端一个返回。原子一致性要求全体操作看起来像在单副本上一个接一个完成，并尊重实时先后。可用性要求每个被非故障节点接到的请求最终返回。分区容错被写成：网络可以丢掉任意多从一节点发往另一节点的邮件；一旦分成若干组件，跨组件的信全部丢失。任意一种丢信模式，也都可以说成「恰好在那一封信上出现过一次暂时分区」。他们明确不把停机当作本注记的故障类，尽管单节点停机有时可以被看成该节点独自构成一个组件。

异步模型取自林奇 1996 年《Distributed Algorithms》第 8 章。没有钟。节点只能根据已收到的信和本地计算做决定。公平执行里，该发生的本地步骤与未被丢掉的投递终会发生，只是没有上界。定理 1 说：不存在一种实现，使这份读写对象在所有公平执行上既可用又原子——这些执行包括丢信的那些。

证明用反证，几何很短。网络里至少两个节点，分成两个非空不相交的集合 \(G1\) 与 \(G2\)。令对象初值为 \(v0\)。先看前缀 \(\alpha1\)：只在 \(G1\) 发生一次写入，值不等于 \(v0\)，两侧之间没有任何邮件被投递。可用性强迫这次写在 \(G1\) 内部完成。再看前缀 \(\alpha2\)：只在 \(G2\) 发生一次读取，两侧之间同样没有邮件。可用性强迫这次读返回某个值；在 \(\alpha2\) 里从未发生过写，原子规格只允许返回 \(v0\)。把 \(\alpha1\) 接上 \(\alpha2\) 得到执行 \(\alpha\)。对 \(G2\) 里的节点来说，\(\alpha\) 与 \(\alpha2\) 不可区分，因为来自 \(G1\) 的信在两种讲法里都被丢掉，而 \(\alpha1\) 又没有把任何客户端请求送到 \(G2\)。于是 \(\alpha\) 里的那次读仍必须返回 \(v_0\)。可是在实时上，写已经结束，读才开始。原子性被当场撕开。方法上，他们指向阿蒂亚等人 1987 年 FOCS 的可实现情形，以及林奇书中定理 17.6；本页不把那些章节写成第二对象。

推论 1.1 把不可能再收紧一档。它禁止的是：所有公平执行都可用，并且仅仅在「没有丢信」的公平执行上保持原子。若存在这种算法，它在某条丢信执行里迟早会交出不原子的答案——否则就违反定理 1。那个坏答案出现在有限前缀上。把前缀之后尚未到达的信全部补送，得到一条「其实没有永久丢失」的公平执行，坏答案仍写在上面。异步里没有记号告诉你该把这次执行算成分区还是算成迟到。所以你不能一边承诺永远回答，一边承诺「只要事后看来信都到了，历史就是原子的」。

论文接着写「任意两句可以同时成立」，那是可行性素描，不是另一条不可能性。放弃可用性：可以指定一个中心节点持有真值，请求都转发过去；没有邮件时就等，原子性保住，回答可以永远不来。放弃分区许可：同一套中心算法在假定信会到达的内网里又可用又原子。放弃原子性：可以每次都返回 \(v_0\)，或返回本地看见过的某个值。这些素描标明量词卸在哪一处。它们不是集群产品目录，也不指定哪一种多数派协议。本页到此停在异步对象上。

它证明了什么，没有覆盖什么#

它证明了：完全异步、原子读写对象、接到请求就必须回答、邮件可以在组件之间丢掉，这四条叠在一起时，不存在实现能在所有公平执行上同时交出原子历史与响应。推论 1.1 还证明，无钟模型里你甚至不能把原子性推迟到「事后看来没有分区」的那些执行上，同时保留全称可用性。它把「慢」与「丢」写成同一种本地现象，并把许可用到极限。它没有比较哪种超时毫秒更好，没有给键值集群写标签，也没有讨论开放成员网络里多数如何定义。对象停在这条关于原子寄存器的全称不可能。

部分同步是同一篇注记的第二节，用来标明换模型之后哪一句仍然站住、哪一句松开。他们假定每个节点有钟，钟以同一速率前进，但不必显示同一个读数；钟的用处是当计时器。另假定一封信要么在已知时限 \(t{\mathrm{msg}}\) 内到达，要么丢掉；节点处理一封已达信件也有已知时限。定理 2 说：即便在这个有钟模型里，仍然不可能在包含丢信的所有执行上既可用又原子。证明几乎是定理 1 的定时版：先在 \(G1\) 完成一次写并丢掉跨组邮件，再插入一段足够长的空白，使写的结束确定地早于 \(G2\) 上那次读的开始。钟不能把丢掉的值传送到对侧。真正松开的是推论 1.1 的类比。有了时限，节点可以在 \(2t{\mathrm{msg}}+t_{\mathrm{local}}\) 之后判定「这封信按模型应当已经丢掉」，于是存在这样的算法：消息全部按时到达时历史保持原子，只有丢失发生时才退回陈旧本地值或提前确认写。他们把一种更弱的规格叫做 t-连通一致性：无丢失的执行必须原子；有丢失时，只要两次操作之间隔着一段长于 \(t\)、且其间邮件都到达的区间，后一次就不得在偏序里排到前一次之前。分区愈合之后，陈旧被允许的窗口被这段 \(t\) 钉住。这是 2002 年自己写下的折中，不是 2012 年的那篇澄清，也不是产品手册。

本页对象覆盖不到的，首先是没有分区时延迟与一致性的权衡。丹尼尔·阿巴迪（Daniel J. Abadi）2012 年在 IEEE Computer 把那条曲线写成 PACELC：若发生分区，在可用性与一致性之间选；否则在延迟与一致性之间选。吉尔伯特与林奇的定理 1 谈的是丢信执行里原子与终止不能并存，并不测量健康路径上多等几毫秒能换回多新的读。把 PACELC 读成 2002 年的定理，会把一条关于分区许可的不可能收成日常尾延迟调参。其次覆盖不到布鲁尔本人 2012 年同期刊的回顾。那篇文章把「永远三选二」标成误读，强调分区是少见窗口，窗口内有一组连续的降级，而不是两枚开关。它可以当作对照：猜想提出者后来想收窄口号；本页仍然停在 2002 年已经证明的那一句。再次覆盖不到把整套存储永久贴上 CP 或 AP。原子性是对单对象历史的条件，可用性是对单次请求的终止，两者都可以按操作、按键、按不变量切开；总览页已经警告过这件事，本页不把它写成第二遍标签指南。

它也不覆盖 FLP 的量词，不覆盖兼职议会如何相交多数，不覆盖 Dynamo 里 N、R、W 与向量时钟怎样买最终可见。那些工作可以引用 CAP 作为背景，背景不是对象。部分同步给了时限，于是超时重新合法；它没有给一份「如何在生产网络里制造分区」的步骤。概念证据到此为止。

跨域连接#

• 时间哲学：完全异步拒绝一个可共享的「此刻」。事件先后由调用、返回与投递给出，不由墙上读数给出。分区把对侧的将来从本地可观察的现在里剪掉：信也许仍在通道里，也许已经被模型写成丢失，两者在无钟节点上留下同一段沉默。推论 1.1 依赖的正是这种不可分辨。部分同步把计时器还回来，使「等过已知上界」成为一种终将正确的推断，于是「没有分区的执行」重新可以被认出来。把超时读成校准误差范围内的同时性，会把模型直接改回同步，定理 1 不再适用。本页的时间是历史上事件的排列，不是授时服务发出的时间戳。
• 认识论：每个组件必须在没有上帝视角时回答。证据是自己收到的邮件，不是关于「对侧已经写下新值」的现成知识。定理 1 的 \(\alpha\) 对 \(G2\) 不可区分于从未发生过写的 \(\alpha2\)：两种世界在本地证据上重合，原子规格却要求它们给出不同答案。可用性禁止以沉默充当判断。于是确定性程序要么违反规格，要么拒绝在欠定证据上作答——而拒绝作答正是可用性所禁止的。这不是怀疑主义练习，而是把「真」与「知」拆开。写在 \(G1\) 也许已经完成（真），\(G2\) 没有可核验的记号来知道这件事（知）。
• 知识：原子历史是一份关于「此刻寄存器是什么」的公共事实。线性化要求后来的读不得假装这份事实尚未写下。分区切断的是把局部成功提升为公共知识的通道。\(G1\) 上的写返回，只说明这一侧已经把值收进自己的知识状态；它并不因此成为 \(G2\) 持有的共同知识。把「我的调用返回了」听成「所有人都已经按这个顺序知道了这件事」，是把局部证据做成全局抄本。活性失败在这里表现为对侧迟迟不能闭合那份抄本；分叉才是两侧各自闭合了互不相容的抄本。本页的不可能说的是：你无法设计一种规则，让两侧在邮件被剪断时仍都闭合，并且闭合到同一份原子历史上。
• 同一性：原子寄存器凭规格被认作「那一个对象」，不凭某次运行里副本的内部布局。分区两侧各自继续回答之后，观察者手里会暂时出现两份历史。线性化问的是：它们是否仍能被收成同一份顺序规格的成员。若读已经交回旧值、而写的返回在实时上更早，规格不再承认这是同一个原子对象——不是因为机器换了，而是因为外延对不上。换一套中心节点、甚至换成一组副本，只要历史仍可线性化到同一寄存器规格，同一性在正确性条件的意义上保持。规格若改成允许陈旧窗口，对象就不再是 2002 年定理 1 里的那一个。t-连通一致性显式改了规格，因此改的是「它还是不是那个原子寄存器」这一问，而不是给原规格找反例。
• 信息不对称：分区把同一份寄存器切成两个暂时无法报价的信息集。一侧已经成交过一次写，另一侧仍按初值回答，像两座市场在同一商品上持有不能对盘的账本。经济学里的不对称通常假定通道还在、只是一方知情；这里的通道按模型被剪断，知情本身无法被对侧核实。愈合之后的 t-连通窗口，像是重新开盘后允许账本 lag 一段已知时间再对齐，而不是否认曾经各写各的。把这种结构读成「请去切断别人的通信」，会离开对象：本页只说明，当通道被许可剪断时，原子合同与「必须报价」不能同时作为全称承诺。

参考文献#

• Seth Gilbert & Nancy Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services", ACM SIGACT News 33(2), 2002, pp. 51–59. DOI: 10.1145/564585.564601. —— 本文对象：异步网上原子读写对象在丢信执行中不能同时可用且原子；部分同步下的定理 2 与 t-连通一致性用作同一篇注记内部的对照。
• Eric A. Brewer, "Towards Robust Distributed Systems" (invited talk), PODC, Portland, Oregon, July 2000. DOI: 10.1145/343477.343502. —— 被形式化的猜想来源，口头三句与证明中的定义并不自动等同。
• Eric Brewer, "CAP Twelve Years Later: How the 'Rules' Have Changed", IEEE Computer 45(2), 2012, pp. 23–29. DOI: 10.1109/MC.2012.37. —— 猜想提出者对「三选二」口号的事后澄清，用作对照，不是本页对象。
• Maurice P. Herlihy & Jeannette M. Wing, "Linearizability: A Correctness Condition for Concurrent Objects", ACM Transactions on Programming Languages and Systems 12(3), 1990, pp. 463–492. DOI: 10.1145/78969.78972. —— 论文把原子一致性等同于线性化，本页的 C 停在这份条件上。
• Michael J. Fischer, Nancy A. Lynch & Michael S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process", Journal of the ACM 32(2), 1985, pp. 374–382. DOI: 10.1145/3149.214121. —— 用以标明 CAP 与一次崩溃下确定性共识不是同一条不可能。

延伸阅读#

• 与 分布式系统、分布式计算理论 对读：总览里的 CAP 段落是路标，本页才是 2002 年的定理对象，不要把总览再织长。
• 与 线性化 对读：先看单对象历史怎样被收成顺序规格，再看这份规格在丢信执行里为什么不能与全称可用性叠在一起。
• 与 FLP 对读：先分清「终将投递的延迟加一次停机」与「组件之间的邮件丢失」，再看终止与原子寄存器各从哪一条前提长出来。
• 与 Dynamo 对读：最终一致换的是规格，不是对定理 1 的反例；N、R、W 是工程参数，不是 2002 年的量词。
• Daniel J. Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story", IEEE Computer 45(2), 2012, pp. 37–42. DOI: 10.1109/MC.2012.19. —— PACELC 把无分区时的延迟—一致权衡单独写出，用作本页明确不覆盖的那一条轴。