Dwork–Lynch–Stockmeyer 1988：终将有界的延迟怎样让确定性共识可能

破除误解：部分同步不是「网还不错」#

第一层误解把论文听成一句观感：「现实网络大多数时候是好的，所以共识能工作」。部分同步不是经验分布，是一条对执行集合的许可。要么存在某个固定上界 \(\Delta\)，协议却不许把 \(\Delta\) 写进等待规则；要么 \(\Delta\) 可以写进规则，却必须容忍一个未知时刻 GST 之前任意有限的迟到。两种写法都允许坏前缀任意长。它们禁止的是「延迟可以永远没有上界」。把这句话收成机房里的口碑，量词就从模型掉进了运维。

第二层误解以为「代码里加超时」就是这篇论文。超时是程序里的一行；论文问的是模型里有没有终将生效的上界。完全异步里，到期仍然分不清崩了还是信还在路上。部分同步使「等足够久就该当对面已停」成为一种终将正确的推断，不是把某次等待拧到某个毫秒。论文明确不假定投递时间服从某种概率分布，因此也不能靠反复测量把未知的 \(\Delta\) 估出来。未知上界不是统计量。本页不比较间隔、不写退避曲线、不教人如何布置计时器。把模型读成菜谱，会把「上界终将出现」误认成「你应当把哪一个数字写进配置」。

第三层误解把 1988 年听成推翻了 1985 年。FLP 的前提是：没有 \(\Delta\)，也没有相对速度上界 \(\Phi\)，协议还是确定性自动机。德沃克、林奇与斯托克迈尔不改那条证明，他们拿掉「上界永不存在」这一条。1987 年，多莱夫、德沃克与斯托克迈尔已经证明：\(\Delta\) 与 \(\Phi\) 只要缺一，连一次停机也能挡住共识。1988 年接着问：上界不必从一开始就以已知常数的面目出现，只要它存在或终将生效，确定性协议是否重新可能。可能，并不等于 FLP 写错了。假设不成立时，FLP 的对手调度可以再次出现。

第四层误解把后来的两扇门收进本页。本-奥尔 给硬币，把终止改成几乎必然，完全异步仍然完全异步。故障检测器 给一份会犯错的怀疑名单，时间仍可以没有上界。部分同步给的是时间。三扇门互不吞并。把 GST 听成「检测器最终不再误杀」，或把未知 \(\Delta\) 听成「加一点抖动」，都换了合同。本页也不把拜占庭故障写成口头撒谎的操作步骤：故障类只用来标明人数界限落在哪一档，不用来说明如何作恶。

模型：未知上界，或已知上界从 GST 起生效#

装置与 FLP 同族：有限多个进程，消息进缓冲，进程是确定性自动机。通信有一个候选上界 \(\Delta\)：若 \(\Delta\) 在某段时间上成立，则该段里每封被投递的信都不晚于 \(\Delta\)。处理器另有相对速度上界 \(\Phi\)：若 \(\Phi\) 成立，没有一个正确进程能比另一个快出这个倍数。完全同步把两个上界都写成事先已知、并且从第一步就成立。完全异步说两个上界都不存在。部分同步夹在中间，而且通信与处理器可以分开谈。

通信的部分同步有两种合同，论文把它们收成同一句话。第一种：对每一次执行，都存在某个 \(\Delta\) 从一开始就管住投递，但协议设计时不许知道它是多少。观念上像一场博弈：设计者先交出协议，对手再宣布 \(\Delta\)，协议仍须正确。第二种：\(\Delta\) 可以事先知道，但只从某个未知时刻 GST 起成立；GST 之前，迟到可以任意长，只要仍是有限的。博弈顺序反过来：对手先点名 \(\Delta\)，设计者按这个 \(\Delta\) 写协议，对手再挑选 GST。GST 不必被设想成「从此网络永远完美」。任一在 GST 之后仍有有限时间上界 \(L\) 就能决定的协议，其实只要求上界维持到 \(\mathrm{GST}+L\)；论文为了少写一个参数，让上界从 GST 起一直成立，再单独给出 \(L\) 是 \(N\) 与 \(\Delta\) 的多项式。两种合同都不把「晚到或暂时没到」算成进程故障。若把某个随便选定的等待当成 \(\Delta\)，再把超时的进程一律算故障，论文认为不可接受：估小了，正确进程会全体被开除，决定变成对空集的空话。协议先写在一种更强的「基本轮模型」里：轮次清楚，每轮结束时该到的信都到。再把同一套规则翻译到未知 \(\Delta\) 或 GST。翻译的存在说明两种部分同步对可解性等价，不说明某一次等待该设成多少。

论文把安全与终止拆开，用来说明 GST 合同为什么不是一句软弱的「后来会好」。一致性与有效性是安全：两个正确进程不得写出不同的值；若全体初值都是 \(v\)，决定必须是 \(v\)。终止是活性：每个正确进程终将决定。要求安全在任意异步行为下都成立、只要求终止在「\(\Delta\) 终将成立」时成立，等价于要求协议在 GST 模型里解共识。理由很短。安全若被破坏，破坏发生在某个有限时刻；把那一段前缀接上「此后 \(\Delta\) 成立」的后缀，就得到一条 GST 执行，而协议在 GST 执行上被假定为正确，安全不该已经坏掉。于是：GST 从未到来时，协议仍不得分叉、不得发明第三种答案；它只被允许永远不决定。这与 兼职议会与 Paxos 后来把安全写成始终成立的不变量、把活性另靠稳定窗口，是同一类量词安排。亲属不是对象。本页不把多数相交、选票编号或视图更换写成实现说明书。

处理器也可以部分同步：\(\Phi\) 存在但未知，或 \(\Phi\) 已知却只从某个 GST 起成立。当通信与处理器同属一种部分同步时，进程不再自动共享「第几轮」。论文为此给出容错的分布式钟，作为兰波特时钟的变体，让部分同步的处理器重新模拟轮次。两只钟分别服务不同故障档：一只用 \(2t+1\) 个进程，覆盖停机、遗漏与带认证的拜占庭；另一只用 \(3t+1\) 个进程，覆盖不带认证的拜占庭。把钟与「只有通信部分同步」时已经写出的共识协议叠在一起，就得到两边同为部分同步时的协议。钟是把模型接回可解性的装置，不是授时服务配置单。本页只承认轮次可被模拟，不把对时步骤写出来。

故障分成四类：停机、遗漏、带认证的拜占庭、不带认证的拜占庭。停机是进程安静地不再发送。遗漏是该发未发或该收未收。后两类允许错误消息，人数界限因此更苛刻。本页给出界限，不描述如何伪造、如何对两名听众说两套话。共识的值域在上界协议里是任意集合；下界即便限制成二值仍然成立。强一致性要求全体初值相同时必须选这个值，弱一致性只在无人故障时这样要求。除一处带认证且只有处理器部分同步的技术例外，上界协议达到强一致性。

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

它证明了：在处理器完全同步、通信部分同步时，停机或遗漏故障下 \(t\) 容错共识可能，当且仅当 \(N \ge 2t+1\)；拜占庭故障下——无论是否认证——当且仅当 \(N \ge 3t+1\)。通信与处理器同为部分同步时，人数界限相同，只是时间多项式还依赖 \(\Phi\)。未知 \(\Delta\) 模型里，正确进程决定所需时间是 \(N\) 与 \(\Delta\) 的多项式；GST 模型里，是 GST 加上同一类多项式。报文比特数也有同样的多项式上界。协议共用一种锁值几何：某个进程发现值 \(v\) 可被接受，就设法让别人改到 \(v\)；收到足够多的确认之后才决定 \(v\)，使以后再没有另一个值会被当成可接受。确认集合必须大到与任何后来的可接受集合相交。这是安全始终成立的原因，也是停机档需要多数、拜占庭档需要更苛刻相交的原因。几何是外延的集合相交，不是机柜拓扑。这些数字与几何是存在性证据：模型一旦允许终将生效的上界，确定性协议就不必再把终止交给硬币或预言。

界限为什么落在「完全同步与完全异步之间」，值得单独说清。完全同步且停机时，缺席可被时钟认出，容错可以高到只剩一个正确进程。完全异步时，FLP 与 1987 年那篇最小同步性论文一起给出：缺 \(\Delta\) 或缺 \(\Phi\)，一次停机就够挡住确定性终止。部分同步的通信拿掉了「缺席可立即认作死亡」，却留下「上界终将管住投递」。协议因此不能把沉默直接写成故障；它必须准备在尚未稳定的前缀上保持一致，并在稳定之后靠足够大的相交集合把值锁住。停机与遗漏需要多数，\(N \ge 2t+1\)。拜占庭还要压过错误消息，\(N \ge 3t+1\)。认证在完全同步里能把拜占庭容错抬到与停机同档；在部分同步的通信里，认证不提高容错份额。这是论文自己标出的对照，不是产品对比。

处理器部分同步而通信完全同步时，容错可以更好：停机档回到更接近完全同步的人数，带认证的拜占庭可以落到 \(2t+1\)。那一列不是本页的主对象，只说明「哪一种上界先回来」会改变算术。下界方面，论文证明在处理器同步、通信部分同步且 \(2 \le N \le 2t\) 时，停机或遗漏下不存在共识协议；拜占庭侧对应地卡在 \(N \le 3t\)。对象覆盖的是这些可能性与不可能性，不是某一次具体交换的报文格式。

它没有证明完全异步里确定性共识突然可以终止。它没有给出 本-奥尔 那种几乎必然的测度语句，也不需要随机源。它没有定义不可靠故障检测器：钱德拉与图埃格 八年后才把「终有一个正确进程不再被误杀」写成预言规格；那种预言可以在部分同步里被实现，实现是后来的归约，不是 1988 年的对象。它没有讨论开放成员、分区三角或原子寄存器：消息传递上的安装见 ABD 1995，本页不需要那份多数派仿真。Gilbert 与 Lynch 2002 的异步不可能谈的是丢信执行里读与写，本页谈的是终将有界的延迟里一个值的决定。它更没有比较哪种等待更灵敏。2007 年 Dijkstra 奖授予这篇论文，不是因为它发明了某一种集群，而是因为它把「多同步才够用」写成可检验的合同。概念证据到此为止。

跨域连接#

• 时间哲学：完全异步拒绝一个可共享的「此刻」。部分同步并不把此刻还回来，它只断言存在一个未知的「之后」：GST 不是墙上的某一秒，\(\Delta\) 也不是校准误差。缺席在 GST 之前仍不是可观察的现在，而是可能仍在未来才到达的延迟；GST 之后，同一段沉默才被允许读成「按合同应当已经停机」。把超时读成人人共用的薄薄一层现在，模型会塌回完全同步，FLP 与 DLS 的分界一起消失。本页的时间是执行上的分界点，不是授时服务发出的时间戳。
• 认识论：正确进程必须在没有上帝视角时决定。GST 之前，延迟与停机仍产生形状相同的证据。论文允许的不是从欠定现象推出不可撤回的死亡证明，而是把「何时可以结束等待」推迟到上界生效之后。安全判断——尚未决定，或已决定的值不得改口——必须在证据仍欠定时就能作出。活性判断可以等。工程事故常发生在把本地等待当成已经共享的公共知识。本页把两句话拆开：你可以在稳定之前拒绝宣称已知谁已死亡；你不得把这份拒绝写成第二个值。
• 模态逻辑：未知 \(\Delta\) 是关于整条执行的存在句：存在一个上界，它始终管住投递，只是协议看不到那个数。GST 是带 \(\Diamond\) 的句子：存在某个时刻之后，已知上界成立。两种部分同步都把必然性从「每一步都同步」上拿掉，却不把可能性写成「也许永远没有上界」。FLP 禁止的是没有这层 \(\Diamond\) 时的确定性全称终止。把菱形听成「再等一会儿就知道谁死了」，会把最终算子还原成一次已经发生的观察，合同退回没有上界的等待。
• 知识：安全是关于已经写下的值的公共事实：一旦两个正确进程都决定，他们必须知道同一个答案。活性是这份事实终将闭合。GST 模型允许知识状态在未知长的前缀上保持二值待定，只要待定不破裂成分叉。分布式钟要解决的，是部分同步的处理器如何重新获得一种近似公共的「第几轮」，以便把锁值与决定放进同一段被上界管住的交换里。把「集群里有人已经提交」与「我已经知道有人提交」混成同一个时刻，会把活性延迟误诊成数据分叉。延迟是知识尚未闭合；分叉才是安全被打破。
• 概率：本-奥尔把终止改写到硬币测度上的几乎必然，不需要 \(\Delta\) 出现。部分同步不进入概率空间，它需要上界终将出现。两条逃逸的量词不同：一个交出全称调度、换回零测例外；一个交出「延迟可以永远任意长」、换回多项式时间的确定性终止。把「我们加了抖动」说成已经进入 GST 合同，等于既要随机化的启发式，又要时间模型的措辞。抖动若不附带一句关于上界或关于测度的话，仍是确定性程序里的另一种排列。

参考文献#

• Cynthia Dwork, Nancy A. Lynch & Larry Stockmeyer, "Consensus in the Presence of Partial Synchrony", Journal of the ACM 35(2), 1988, pp. 288–323. DOI: 10.1145/42282.42283. —— 本文对象：部分同步的两种模型，以及四类故障下确定性共识的容错界限。
• Cynthia Dwork, Nancy A. Lynch & Larry Stockmeyer, "Consensus in the Presence of Partial Synchrony (Preliminary Version)", Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (PODC), Vancouver, 1984, pp. 103–118. —— 会议版，用以标明模型在期刊长文之前已经公开。
• 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. —— 完全异步下的确定性不可能，用以标明本页放松的是哪一条时间假设。
• Danny Dolev, Cynthia Dwork & Larry Stockmeyer, "On the Minimal Synchronism Needed for Distributed Consensus", Journal of the ACM 34(1), 1987, pp. 77–97. DOI: 10.1145/7531.7533. —— \(\Delta\) 与 \(\Phi\) 缺一则一次停机即可挡住共识，用作 1988 年「部分恢复上界就够」的对照。

延伸阅读#

• 与 FLP 不可能性 对读：先看完全异步禁止什么，再看本页把哪一句时间许可加回去。
• 与 钱德拉与图埃格 对读：给时间与给怀疑名单是两扇门；检测器可以在部分同步里被实现，实现不是本页对象。
• 与 兼职议会与 Paxos、分布式共识算法 对读：安全始终成立、活性依赖稳定窗口，是后来协议从这份模型继承的量词，不是 1988 年的产品说明书。
• 与 本-奥尔 对读：硬币不需要上界出现；部分同步不需要随机源。
• 与 辛西娅·德沃克 对读：1988 年部分同步是分布式里的一次立法，人物页里的差分隐私是另一条，不要收成同一个故事。
• 与 Gilbert 与 Lynch 2002 对读：那篇注记的部分同步用来谈原子寄存器的时限，本页用来谈一个值的决定。