Attiya–Bar-Noy–Dolev 1995：消息传递上的原子寄存器

破除误解：共享内存仿真不是共识，多数派也不是法令投票#

第一层误解把标题听成「网络其实就是共享内存，按共享内存的办法写就行」。论文要证明的是可实现性：消息传递加上多数派活着，足以对外表现得像一份原子寄存器。它没有授权把缓存行、互斥锁或无锁队列直接搬到邮路上。寄存器是一种极窄的对象：写一个值，读出一个值。队列、集合、日志都不是本页的产物。把仿真读成配方，会把存在性证明写成操作单。本页拒绝配方。

第二层误解把 ABD 收成线性化本身。线性化是观察者应当承认的效果：写已经返回之后才开始的读，不得交回写之前的值；两次不相交的读，不得新-旧倒置。ABD 是一种被证明满足该效果的装置。条件可以与锁共存，也可以与副本共存；本页只给出崩溃停机、异步信道、多数派相交这一种安装。把「我们做了 ABD」说成「我们重新定义了线性化」，类型就错了。规格在 1990 年已经写下；1995 年回答的是邮路够不够用。

第三层误解以为「既然共享内存被仿真出来了，共识也就有了」。共享内存算法里，有的只使用原子寄存器，有的还需要测试并设置、队列或比较并交换。等待自由层级 已经标明：原子读写寄存器的共识数是 1。ABD 仿真出来的正是这一级对象。你可以把只靠寄存器就能跑的程序搬到邮路上；你不能因此得到两个进程的等待自由共识。FLP 仍然管着下面那层消息传递系统：一次崩溃加上完全异步，确定性共识的终止不能在所有合法调度上被担保。两句话同时成立——寄存器可以被仿真，共识仍然不必能被决定。把「robustly sharing memory」听成「robustly deciding a value」，把对象换掉了。

第四层误解把多数派听成兼职议会里的一次投票，或听成「大多数机器同意就赢」。议会要锁定的是一条以后不能偷换的法令；ABD 要锁定的是一个带时间戳的值已经进入某个多数，从而使后来的多数无法假装没见过它。相交几何看起来像亲戚：任意两个多数共享至少一名进程。亲属不是对象。Paxos 把安全写成始终成立的不变量、把活性另靠稳定窗口；ABD 在完全异步里就能让读写终止，条件是多数仍然应答。它不选举领导者，不更换视图，也不把客户端命令排成日志。把 ABD 读成「简化版 Paxos」，会把寄存器误认成共识，也会把 1995 年的对象误认成 1998 年才刊出的寓言。

印本装置：时间戳、多数派、读回写#

装置从一份本地副本开始。每个进程手里都有寄存器的一份拷贝，拷贝不是真值，真值也不存在于任何单独的地址。可观察的合同只有读与写的调用和返回。要把并发历史收成单副本的原子规格，论文配备三件彼此咬合的零件：给写排序的标签、强迫写与读相遇的集合、以及让一次读的返回成为后来者无法否认的事实。

第一件是时间戳。每次写必须带一个可全序比较的标签，使「更新」有唯一含义。单写者可以用私有计数器：自己的下一次写，标签严格大于上一次。多写者不能共用一只看不见的全局钟。他们需要一对不会碰撞的标签，通常是序号加上写者身份，按字典序比较。身份只用来打破平局，不是权限。标签要满足的外延很窄：任意两次已完成的写，必须能排出先后；后开始的写不得拿到更小的戳。这与 Lamport 1978 的先于关系精神相近——因果上的后事不得在序里排到前事之前——但兰波特给出的是偏序，ABD 要的是「取最大」这一运算总有定义。把时间戳听成墙上时钟，或听成授时服务发出的毫秒，装置会塌回同步。标签是写操作上的全序，不是时刻的测量。

第二件是多数派。一次写把带标签的值送到足够多的进程，使得收到的集合构成全体的多数；一次读也从某个多数收集拷贝。几何只有一句：任意两个多数至少交于一个进程。因此，已经完成的写所进入的那个多数，与后来任何一次读所询问的多数，必有一名共同证人。证人不必知道自己在作证。他只是保存着那份带标签的拷贝。读在收集结果里取标签最大的值，于是已完成的写不可能被后来的读整段漏掉。少数派崩溃不会拆开这句几何——只要活着的人仍够组成一个多数，证人还在某个仍然应答的集合里。多数不是统计抽样，也不是「看起来够了」。它是集合相交：对每一次执行、每一对多数都成立，不是对大多数执行成立。

第三件是读回写。只做「写进多数、读出多数里的最大标签」，还不够原子。两个读可以与同一次写重叠，也可以彼此重叠。先返回的那次读可能已经看见新值；后返回的那次读若问到另一块尚未被新值覆盖的多数，就会交回旧值。这叫新-旧倒置。原子规格禁止它：不相交的实时区间不得在顺序历史里颠倒。读回写补的正是这一刀。读在决定返回哪个值之前，必须先把这个带标签的值再安装进一个多数。安装完成之后，任何后来的多数都必与这个新多数相交，因而必看见至少这么大的标签。于是先返回的读不但自己看见了新值，还把「新值已被多数持有」写成后来者无法绕开的事实。写已经返回之后才开始的读，本来就会撞上写的多数；读回写要挡住的，是读与读之间的倒置，不只是读与写之间的过期。

三件零件合在一起，才对上原子这一档。兰波特 1986 年把寄存器分成安全、常规、原子。常规允许与写重叠的读返回旧值或新值，但不允许返回从未写入的值；原子还要挡住新-旧倒置。ABD 瞄准的是最强那一档。对读写对象而言，它与线性化重合。论文用的词是原子寄存器，不是把 1990 年的历史定义再讲一遍。有界时间戳系统可以把无界计数换成有限标签；那是后来可以叠上去的技术，不是 1995 年这篇要卖的几何。本页承认标签在基本构造里无界，不把有界化写成第二套装置。

它证明了什么，也就划出了它没有证明什么。它证明：崩溃停机的异步邮路上，多数派活着时，原子的多写者/多读者寄存器可以被仿真；仿真的安全来自标签全序与多数相交，仿真的活性来自「总还有一个多数会应答」。它没有证明任意对象都可以这样仿真。队列的共识数是 2，比较并交换是无穷；那些对象在等待自由的共享内存里已经强于寄存器，本页不把它们安装到邮路上。它也没有给出报文格式、重试曲线或如何布置缓冲区。把读回写听成「请在生产里加一次额外的 put」，会把几何收成运维清单。

容错界限与假设：崩溃与 \(n>2f\)#

故障是崩溃停机。进程安静地不再发送，不伪造、不对两名听众说两套话。信道对仍然正确的进程终将投递，只是没有上界。这与 FLP 同族：完全异步，延迟可以任意长，慢与死在本地观察上重合。差别在对象。FLP 问共识能否在所有合法执行上既一致又终止；ABD 问寄存器的读与写能否在多数仍然应答时返回，并且返回值能被收成原子历史。不需要 DLS 1988 的未知上界，也不需要 GST。超时在本页不是合法推断：到期时你仍然分不清对面崩了还是信还在路上。读写之所以能结束，不是因为有人被判定死亡，而是因为活着的多数已经应答。分不清死亡，并不妨碍多数相交。

人数界限是 \(n>2f\)，也就是 \(n\ge 2f+1\)。若最多 \(f\) 个进程崩溃，剩下至少 \(f+1\) 个正确进程；当 \(n=2f+1\) 时，这恰好构成一个多数。于是每个尚未崩溃的调用者，仍能凑齐一次写或一次读所需要的应答。两个多数至少交一人，安全不靠认出谁已停机。若 \(n\le 2f\)，活着的人可能凑不成多数，等待多数应答的调用可以永远不返回。界限因此同时卡住活性：多数派活着是终止的前提，不是一句关于机房口碑的观感。把 \(n>2f\) 读成「再加几台就更安全」，会把一条紧的算术收成容量规划。少一台，几何就不再保证相交与应答同时成立。

这条界限与后来吉尔伯特与林奇 2002 年关于原子寄存器的分区论证是亲戚，仍不是同一对象。那边允许邮件在两个非空组件之间丢掉，并要求两侧接到请求都必须回答；原子性当场破裂。ABD 不承诺在多数已死或多数被剪到对侧时仍然回答。它承诺的是：当崩溃人数不超过少数、正确进程之间的信终将到达时，读写既终止又原子。可用性被钉在多数这一侧，而不是钉在每一个分区上。把 ABD 听成 CAP 的反例，等于把前提里的多数活着删掉。把 CAP 听成 ABD 写错了，同样换了量词。

拜占庭不在假设里。错误消息会让「标签最大」不再可信：一个撒谎的进程可以出示从未被写入的巨大时间戳。人数界限与相交几何都要另写，本页不写。成员是否开放、多数如何随加入退出重新定义，也不在 1995 年的装置里。进程集合被当成固定的 \(n\)。2011 年 Dijkstra 奖授予这篇期刊论文，理由是它把共享内存与消息传递在崩溃异步下的间距收成一条可检验的仿真，而不是因为它发明了某一种集群。

概念证据到此为止。本页不提供如何发送查询、如何等待应答、如何在生产里避免活锁的步骤。三件零件回答的是「何种几何足以让寄存器的原子规格出现在邮路上」；\(n>2f\) 回答的是「这句几何在多少人崩溃时仍然站得住」。两句都不是操作单。

跨域连接#

• 时间哲学：ABD 的时间戳不是墙上的一格，也不是人人共用的薄薄一层现在。它是给每次写选出的全序标签，使「更新」不必依赖可共享的此刻。读回写把一次已经发生的观察安装进未来：先返回的读所看见的值，成为后来者不能当作尚未发生的事。线性化点仍是存在量词下的虚构瞬间，不必对应某封邮件的到达。把标签听成授时，会把异步模型改回同步，FLP 与 ABD 的分界一起消失。本页的时间是写操作上的全序，不是时钟读数。
• 认识论：读者从来看不见全部副本。证据是某一个多数交回的拷贝，不是上帝视角下的真值。沉默既可被当成延迟，也可被当成崩溃；ABD 不要求先弄清这两种原因再决定返回。它要求的是：在欠定的证据上选出标签最大的值，并把这份局部证据提升为后来的多数无法否认的事实。写的返回也不等于「我已经知道所有人都看见了」。它只等于「任意一个将来的多数都会与我写过的集合相交」。把本地成功做成全局已经共享的知识，是工程事故里最常见的一跃。
• 模态逻辑：写一旦在某个多数上完成，任何未来的多数都必然与它相交，因而必然看见至少这么大的标签。重叠期间的读则只是可能看见新值：它的收集集合尚未被强迫与那次写相遇。必然性出现在调用返回之后，可能性留在相交的区间里。读回写再加一句必然：读一旦返回 \(v\)，此后的读不得可能再交回更旧的值。把菱形听成「再问一次机器就知道了」，会把模态还原成一次已经发生的观察，原子规格塌回尽力而为的可见性。
• 知识：多数派知识不是公共知识。没有人需要知道「所有人都知道这个值」，甚至不需要知道「所有活着的人都知道」。合同只要求：任何以多数为窗口的后来观察，都见得到这个标签或更新的标签。公共知识太贵，完全异步里通常买不到；寄存器规格也用不到那么强的闭合。学习者完成一次读，知道的是一个可被后来者核验的下界，不是一份已经写死的全局历史。尚未结束的写仍可能插在相交的区间里。把下界当成全序抄本，会把安全性失败误诊成「慢」。
• 概率：多数不是随机抽样，相交也不是大数定律。ABD 给出的是对每一次执行都成立的集合论保证：两个多数必交，标签最大者必被后来的多数看见。它不进入测度空间，不把终止写成几乎必然，也不需要硬币去打破对称。随机化共识走的是另一扇门：交出最坏情况的全称调度，换回零测例外上的进展。把「大多数副本看起来一致」说成本页的证明，等于用频率语言替换必然相交。看起来一致可以在某次运行里碰巧成立；几何要求的是它不得失败。

参考文献#

• Hagit Attiya, Amotz Bar-Noy & Danny Dolev, "Sharing Memory Robustly in Message-Passing Systems", Journal of the ACM 42(1), 1995, pp. 124–142. DOI: 10.1145/200836.200869. —— 本文对象：异步消息传递上对原子多写者/多读者寄存器的多数派仿真。
• Hagit Attiya, Amotz Bar-Noy & Danny Dolev, "Sharing Memory Robustly in Message-Passing Systems", Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, 1990, pp. 363–375. DOI: 10.1145/93385.93441. —— 会议先驱，用以标明对象是 1995 年期刊长文而非 1990 年摘要。
• Leslie Lamport, "On Interprocess Communication, Part I: Basic Formalism; Part II: Algorithms", Distributed Computing 1(2), 1986, pp. 77–101. DOI: 10.1007/BF01786227. —— 安全 / 常规 / 原子寄存器分级，用以标明 ABD 瞄准的是原子这一档。
• 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. —— 读写对象上与原子寄存器重合的正确性条件，用以标明本页是安装而非定义。
• Maurice Herlihy, "Wait-Free Synchronization", ACM Transactions on Programming Languages and Systems 13(1), 1991, pp. 124–149. DOI: 10.1145/114005.102808. —— 寄存器共识数为 1，用以标明仿真共享内存并不给出等待自由共识。
• 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. —— 完全异步下确定性共识的不可能，用以对照本页对象不是共识。

延伸阅读#

• 与 线性化 对读：先看规格要求历史怎样被收成顺序，再看本页用标签、多数派与读回写去满足它。
• 与 等待自由层级 对读：仿真出来的仍是共识数为 1 的寄存器，不要把「有了共享内存」听成「有了共识」。
• 与 FLP、DLS 1988 对读：寄存器可以在完全异步里被仿真；共识的确定性终止仍然要时间、随机或额外信息。
• 与 Lamport 1978 对读：先于关系是偏序，ABD 的标签是为「取最大」准备的全序，两者精神相近、对象不同。
• 与 分布式共识算法 对读：多数相交可以服务于法令，也可以服务于寄存器；本页只做后一种。
• 与 内存一致性模型 对读：硬件可见顺序不是邮路上的原子寄存器仿真。