区块链原理 / 系统课时
异步网络为何无法保证确定终止
异步网络为何无法保证确定终止
两个共识节点长期收不到彼此的消息时,对方究竟已经宕机,还是网络只是很慢?本课通过三种消息调度场景,解释为什么节点无法仅凭沉默判断故障,以及 FLP 不可能性结论怎样限制确定性共识的终止保证。
学习目标
- 区分异步网络中的消息延迟、节点崩溃与超时怀疑。
- 用两个节点的三种执行场景解释一致性和终止性为何发生冲突。
- 准确识别 FLP 定理的适用前提,并判断实际区块链系统如何获得有条件的最终性保证。
异步网络究竟不保证什么
考虑两个节点 A 和 B,它们需要就一个二进制值达成共识,候选值为 0 和 1。A 在本地发送消息后,B 可能立即收到,也可能等待 30 秒才收到。在完全异步模型中,协议不能假设消息延迟和节点处理时间存在已知的有限上界。
这里的异步并不等于消息必然丢失。我们甚至可以假设通信可靠,发出的消息不会被篡改,并且发往持续运行节点的消息最终能够送达,但无法保证具体送达时间。
假设 A 已经等待 B 的回复 200 毫秒,以下两种情况在 A 看来完全相同:
- B 已经崩溃,不会再发送回复。
- B 正常运行,但消息被网络延迟了 30 秒。
将等待阈值改成 5 秒或 60 秒,也无法在完全异步模型中消除这种歧义,因为合法的消息延迟始终可以更长。
为了明确共识目标,先约定三项性质:
| 性质 | 必须满足的条件 | 违反示例 |
|---|---|---|
| 一致性(Agreement) | 已作出决定的正确节点不能决定不同值 | A 决定 0,B 决定 1 |
| 有效性(Validity) | 如果所有节点都提议同一个值,决定必须是该值 | 全部提议 0,却决定 1 |
| 终止性(Termination) | 每个未崩溃的节点最终必须作出决定 | 正常节点无限等待 |
这里的终止性指每一次符合模型的执行最终都会结束,而不只是正常网络中通常能够结束。它也不要求预先给出固定的完成时间。
两个节点为何无法区分延迟与崩溃
假设协议完全确定:节点下一步执行什么,只取决于自己的输入、当前状态和已经收到的消息,不使用随机选择。系统最多允许一个节点崩溃,崩溃节点会永久停止执行。
现在构造三种执行场景。
| 场景 | A 的输入 | B 的输入 | 执行条件 | 协议必须面对的结果 |
|---|---|---|---|---|
| 甲 | 0 | 0 | B 在发送任何消息前崩溃 | A 必须最终决定 0 |
| 乙 | 1 | 1 | A 在发送任何消息前崩溃 | B 必须最终决定 1 |
| 丙 | 0 | 1 | 两个节点均正常,双向消息暂时延迟 | 不能允许 A 和 B 决定不同值 |
场景甲中,A 无法再获得 B 的信息。如果协议保证容忍一个节点崩溃,它就必须让 A 在有限的本地执行步骤后决定。由于两个初始提议均为 0,有效性要求 A 决定 0。
场景乙与之对称。B 必须在有限步骤后决定 1。
关键在场景丙:A 的输入仍然是 0,B 的输入仍然是 1。网络调度器暂时不交付两者之间的消息,让 A 一直看不到 B,让 B 一直看不到 A。
在 A 作决定前,它经历的本地输入与收消息历史可以和场景甲完全一致;B 的本地经历则可以和场景乙完全一致。确定性协议无法区分这些本地经历,因此 A 会决定 0,B 会决定 1。

场景丙中的消息无需永久丢失。调度器只需要将消息延迟到双方作出决定以后,再正常交付即可。因此,即使通信可靠,也无法挽救已经发生的一致性冲突。
如果协议为了避免这种冲突,规定必须收到对方消息才能决定,那么场景甲和乙中仍在运行的节点可能永远无法决定,终止性又会失败。
这个双节点反例表明,在要求容忍一个崩溃故障时,确定性协议无法同时满足上述三项性质。它揭示了 FLP 的关键直觉,但一般节点规模的完整证明还需要更严格的状态分析。
FLP 定理真正证明了什么
Fischer、Lynch 和 Paterson 于 1985 年提出的 FLP 不可能性结论表明:在完全异步的消息传递系统中,即使通信可靠、最多只有一个节点可能发生崩溃故障,也不存在能够在所有允许执行中同时保证一致性、有效性和终止性的确定性共识协议。
这个结论有几个不能省略的限定条件:
- 完全异步:消息传输与节点执行速度没有已知的时间上界。
- 确定性:相同状态及相同输入消息总会产生相同的协议行为。
- 崩溃故障:节点可能停止执行,但不需要假设它会恶意发送伪造信息。
- 全执行保证:协议必须对模型允许的每一种执行都满足共识要求,而不是只在大多数实际运行中成功。
FLP 的一般证明使用双值状态(Bivalent Configuration)的概念:从同一个系统状态出发,未来可能决定 0,也可能决定 1,具体结果取决于后续消息的调度顺序。
证明首先说明存在这样的初始状态,然后利用异步调度可以推迟关键消息这一事实,反复构造仍然保持双值性的后续状态。这样就存在一种符合模型要求的执行,使协议始终无法到达决定状态。
因此,FLP 并不是说所有异步执行都会无限停滞,也不是说网络中只要出现一次延迟,共识就必然失败。它说明的是:无法对每一种允许的执行无条件承诺确定终止。
原始论文可参考:Impossibility of Distributed Consensus with One Faulty Process(1985)。
实际共识协议怎样获得进展
真实系统并非只能无限等待。工程实现通常会调整 FLP 的某项前提,或者降低对终止保证的要求。
| 处理方式 | 增加的条件或改变的保证 | 实际效果 |
|---|---|---|
| 部分同步模型 | 假设某个未知时刻之后,网络延迟和处理时间存在有限上界 | 网络稳定后可恢复终止性保证 |
| 随机化共识 | 引入随机选择 | 在指定故障条件下可获得概率意义上的终止保证,而非所有随机执行都确定终止 |
| 超时与领导者切换 | 使用超时怀疑和视图切换,通常依赖最终稳定的网络条件 | 解决正常运行中的长时间等待,但超时本身不证明节点已经崩溃 |
例如,一个基于部分同步假设的协议初始使用 500 毫秒超时。如果网络长期拥塞导致消息需要 2 秒才能到达,协议可能连续切换领导者,无法完成提交。将超时调整为 1 秒、2 秒、4 秒并继续重试,是一种实际策略;只有结合协议的具体安全规则、故障界限和最终稳定的网络条件,才能论证它最终能够结束。
这也解释了为什么区块链协议需要把安全性与活性分别分析。对于带最终确认投票的区块链,假设有 4 个验证者,一次确认要求至少 3 个有效投票。如果网络将它们分成两个各含 2 个验证者的分区,任何一侧都无法单独获得 3 票。系统可能暂时停止最终确认,但不应该为了维持出块速度而降低投票规则,使冲突区块同时获得最终确认。
这个四验证者场景是确认阈值的工程示例,并非 FLP 定理本身的证明。恢复通信以后,能否继续完成确认,还需要检查协议的投票规则、故障上限、领导者选择以及网络时序假设。
如何判断一份共识保证是否可信
审查共识协议时,可以针对一个具体故障场景逐项核对:
- 查明网络假设:协议要求同步、部分同步,还是完全异步?是否依赖某个最终稳定阶段?
- 查明故障模型:允许多少个节点崩溃,是否还允许拜占庭节点发送冲突消息?
- 查明最终性规则:哪些投票、证明或链上条件意味着决定不可撤销?
- 查明终止性条件:在长期分区和消息无限期延迟时,协议是否仍然声称一定完成?
- 查明保证类型:最终确认是确定性的、概率性的,还是依赖额外网络和诚实节点条件?
例如,一份设计文档同时宣称‘完全异步’‘确定性协议’‘容忍至少一个节点崩溃’‘所有执行必定完成共识’,就与 FLP 的结论冲突。设计者必须指出其中哪项假设实际上发生了变化,或者重新限定终止保证的适用范围。
对交易最终性而言,暂时无法决定不等于已经出现冲突决定。网络分区可能使交易持续处于待确认状态;只要协议仍坚持正确的确认条件,就可以在牺牲部分活性的情况下保留安全性。FLP 划定的正是这条边界:完全异步且可能崩溃的环境中,不能同时承诺无条件的确定性终止与正确共识。