“原子广播是状态机复制的直接排序手段。本页的统一前缀版本与 uniform 分布式共识,在固定成员和匹配的 crash/termination 规格下可相互归约(见共识与原子广播等价性)。辅助…”
形式陈述
本库的分布式主线可按“可靠广播 → 共识 → 原子广播及其等价定理 → 状态机复制”阅读:可靠广播先固定消息传播与去重责任,共识决定一个值或一个日志位置,本页证明连续共识与全序交付可以互相构造,状态机复制再消费这条一致日志。本页只承担中间的等价定理,不重复定义四个相邻抽象。
固定进程集合
辅助可靠广播采用目标页的 eager 转发实现:正确发送者的消息最终到达所有正确进程,正确进程一旦可靠交付,其他正确进程也最终可靠交付,且任何进程都不交付伪造或重复消息。这里对无创造使用的是全参与者量词;它由 eager 协议中“只转发已收到的真实消息”及首次接收标识检查兑现,不能从目标页只约束正确进程的较弱无创造定义直接推出。传播的一致性仍只要求 non-uniform agreement,不额外要求 uniform reliable agreement。每条待排序消息包含全局唯一的 ID 与完整 payload;crash-stop 进程停止前遵守协议,不会为同一 ID 伪造不同内容。
用原子广播实现共识:每个进程广播自己的提议值,并决定自己交付的第一条消息所含的值。统一前缀保证任何两个已决定进程,即使后来崩溃,也取得同一首条消息。
用共识实现原子广播时,先可靠传播完整消息,再依次运行编号为
决定已经给出了完整内容,因此不再等待本地另一次可靠交付。例如一个进程独自可靠交付
安全性按槽位归纳:uniform 共识使所有决定该槽位的进程取得同一消息集合,固定批内排序和 ID 去重再给出共同交付前缀。决定值来自真实提案,每个提案又只含可靠交付过的消息,因此没有伪造;后来崩溃进程交付过的批次,也会随正确进程完成同一槽位而被交付。
还须排除消息饥饿。对正确进程广播的
这一定理不覆盖动态成员或成员重配置,也不把 crash-stop 归约自动提升为拜占庭版本。后两类模型需要重新定义合法消息、认证、法定人数和活性条件,再分别证明归约。
直觉
原子广播的实质是维护一本所有人一致的日志,而日志无非是"接连不断地回答'下一项是什么'";每一次回答恰好是一个共识问题,所以无穷次共识拼出原子广播。反方向更轻:全序交付的第一条消息本身就是一次全体一致、来源合法且人人可得的决定。这个等价把两个表面不同的抽象钉在同一难度等级上——一个是"就一个值达成一致"的一次性任务,一个是"永远保持同序"的持续性服务,理论上却互为改写。由此得到的方法论收益是双向搬运:关于共识的任何可能性、不可能性或最弱假设刻画,都自动成为关于原子广播的同类结论,反之亦然。
例子与边界
把"原子广播实现共识"的方向走一遍即可看到各性质如何对号入座:设进程
边界方面:仅有可靠广播不足以替代原子广播——它保证消息集合一致却不统一顺序,不同副本按不同交错写日志立即分叉。单独一次共识也不够——一个实例只能决定有限信息,为无穷多条消息定序需要无穷多个实例(或改用多决策的共识变体)。若改变两侧的 uniform 范围、辅助广播的传播责任或终止性量词,即使名称仍叫“共识”和“原子广播”,也须重新证明这些步骤;本页只证明上述 uniform 共识与统一前缀广播版本,其他版本须分别核对已交付消息与故障进程的量词。
推论与应用
这一等价性让可能性与不可能性在两个抽象间迁移。FLP 不可能性说至少两个进程、非平凡提议值域、可靠异步消息且允许一次崩溃时,确定性共识无法在所有可容许执行中保证终止,等价性立即推出确定性原子广播同样不可能;Chandra–Toueg 用故障检测器刻画共识可解性的结果,也可转用于原子广播。
工程上,反复运行共识为序列位置填值,可实现复制日志的 committed 前缀;把日志条目按序送入确定性状态机,便得到状态机复制。归约保证的是一致且持续推进的交付序列;本地未提交尾部如何恢复、已交付命令如何持久应用,仍由复制日志和状态机实现分别承担。
单元终结任务:让批次变成共同前缀
固定本页 crash-stop 模型,消息 ID 满足
- 执行。 写出各槽新增交付序列与最终状态。若一个副本只完成第一槽,另一个已经完成第三槽,是否违反统一前缀?网络后来重传同一 ID 的
,与重新广播同样 payload 但使用新 ID,是否都应去掉? - 迁移。 进程 F 独自可靠交付完整消息
,将 提议给下一槽后崩溃;其他正确进程的本地 pending 都为空,但共识合法选择了 F 的提案。它们要不要启动该槽?决定之后还要不要等自己的可靠广播交付 ?若决定只携带 的摘要,哪项证明失效? - 边界。 假设某条正确广播消息已经到达所有正确进程,却只被提议一次,此后永久从 pending 删去。每槽共识仍终止,能否推出该消息必交付?再判断:F 先交付
[a]后崩溃,其余正确进程先交付[b],随后才交付 a,是否符合只约束正确进程的版本、本页版本? - 量词。 用“交付首条提议就决定”说明 FLP 如何传到广播。若故障上界改为0,能否继续援引允许一次崩溃的同一不可能性结论?
核对:三槽分别新增 [a,b]、[]、[c],状态依次为2、2、5;[a,b] 是 [a,b,c] 的前缀。同一 ID 的重传不能再生业务效果,新 ID 则是另一条合法消息。第二题必须持续参加,空 pending 也提议空集;已选集合提供完整内容,直接交付,不能再等可能永不到达的本地可靠交付。只给摘要需要另证内容可取回。
第三题可让唯一一次含该消息的提案落选,后续全部决定空集,构成饥饿;持续重提才排除它。F 的 [a] 与正确进程当时的 [b] 不可比较,因此违反本页 uniform 前缀;仅约束正确进程的弱版本允许它们共同采用 [b,a]。第四题的归约在匹配模型中成立;
参考资料
- Tushar D. Chandra and Sam Toueg, “Unreliable Failure Detectors for Reliable Distributed Systems,” Journal of the ACM 43(2), 1996,§7、Figure 7:共识决定完整消息集合后直接交付。本文另明确 uniform 前缀目标所需的一致性和持续实例参与条件。