激励全局稳定性 - Trail of Bits博客
共识协议在许多应用中扮演着关键角色。Fischer、Lynch和Paterson的经典不可能性结果表明，在合理假设下，协议可能无法达成共识。Dwork、Lynch和Stockmeyer的论文《部分同步环境下的共识》(DLS论文)通过引入以下"全局稳定时间"(GST)假设规避了这一不可能性结果：
对于每次执行，都存在一个处理器不知道的全局稳定时间(GST)，从GST开始消息系统将遵守上限Δ。
换句话说，GST是一个时间点，此后所有网络消息的延迟最多为Δ。DLS表明，在这一假设下，可以构建保证达成共识的协议。
FLP不可能性结果
在《一个故障进程下分布式共识的不可能性》中，Fischer、Lynch和Paterson证明，在非常温和的假设下，一组进程可能无法达成共识。这被称为FLP不可能性结果。
模型
在FLP模型中，两个或多个进程交换消息以尝试就值(0或1)达成一致。每个进程都有一个一次性写入的输出寄存器。进程达成共识的条件是至少一个进程将值写入其输出寄存器，且没有其他进程将相反值写入自己的输出寄存器。
配置包括所有进程的内部状态(包括输出寄存器)以及已发送但尚未传递的所有消息。事件e是(p,m)对，包含消息m和接收进程p。
证明思路
考虑作者的核心引理：如果C是一个二价配置(可能决定0或1)，e是在C中可传递的事件，那么可以以导致二价配置的方式传递e。使用这个引理，作者表明可以以永远无法达成共识的方式传递所有消息。
限制对手
DLS论文将共识视为协议设计者与对手之间的游戏。GST假设限制了对手的移动：对手选择Δ，设计者(知道Δ)提供共识协议，然后对手选择Δ必须开始保持的时间T(GST)。
将对手想象为一场雷暴：
- 可以通过电磁干扰在线路中引入噪声，导致消息需要重传从而延迟
- 闪电可能击中某个不幸的房屋(进程)，导致其停止响应消息
GST的到来意味着天空放晴。但进程无法知道GST是否已经到来。
从延迟中恢复
如果协议在GST假设下被证明是正确的，那么它必须能够从任何可能由延迟导致的配置中达成决策。这意味着：
- 无论GST时的配置如何(只要是由延迟导致的)，协议最终都能达成决策
- 这种恢复能力非常强大，因为延迟可能导致极其多样的配置
结论
虽然GST假设看似不切实际，但它是对逻辑公式的优雅调整。更重要的是，在GST假设下证明协议正确具有深远意义：无论对协议施加何种延迟，只要延迟最终停止，协议就能恢复并达成决策。
当然，GST假设可能不适用于所有协议，特别是那些预期在延迟持续且频繁的环境中运行的协议。此外，证明协议正确并不意味着其实现是正确的。