测试通过为什么还不够
IronFleet 这一讲先质疑一个常见判断:Raft 的论文有证明,自己的代码也通过了测试,是否就能断言实现没有 bug?论文证明针对抽象协议,测试只能覆盖部分执行轨迹,二者之间还隔着具体代码。
形式化验证尝试把这段距离写成明确的规格、实现和证明。规格说明系统允许出现什么行为;证明说明实现的行为落在规格范围内;检查器负责检查证明步骤。规格本身仍需要人理解,写错要求也可以“正确地证明”错误目标。
从程序前后条件走到状态机
讲义先用排序程序说明 Hoare 风格验证:前置条件限定输入,后置条件要求输出有序且保留原元素,循环不变量帮助证明每次迭代都保持必要性质。只要求有序不够,因为把全部元素删空也能满足空序列有序,这说明规格必须覆盖真正关心的行为。
分布式系统则把所有节点状态和网络中的消息一起作为全局状态。Init 规定起点,Next 规定一次合法转换:节点处理消息、更新本地数据、发送报文等。并发对应许多可能的交错,证明不能只针对一条正常执行轨迹。
分层 refinement 减少证明跨度

高层规格可以很小,例如一个锁在任一时刻至多属于一个持有者。协议层加入节点、消息、epoch 和故障;实现层再加入字节编码、数据结构与具体方法。
refinement 映射把低层状态解释成高层状态。低层一步可能对应高层一步,也可能只是内部工作,不改变高层可见行为。只要每层都保持对应关系,便可以利用传递性把实现与最初规格连接起来。
不变量需要经得住每一种转换
“不出现两个持有者”是目标性质,但未必足够直接完成归纳。证明往往还需要描述在途 Transfer 消息、旧 epoch 和持有权之间的关系,确保接收重复或延迟报文也不会制造第二个锁。
归纳证明要求不变量在初始状态成立,并且每一种合法转换都保持它。为某个接收分支补一条约束之后,还要检查其他发送、恢复和丢包分支;这一点正是只看正常执行容易遗漏的部分。
对 Raft 而言,取消投票中的日志新旧限制,可能使协议层无法细化到“不丢失已提交前缀”的规格。验证的价值不只是报告失败,还在于指出抽象规则与实现承诺在哪一层无法连接。
活性证明还需要环境假设
安全性讨论坏事永不发生;活性讨论好事最终发生。若网络永远丢弃所有消息,正确的协议也无法让远端取得锁。因此活性证明要明确公平调度、消息最终到达或网络最终稳定等假设。
IronFleet 的证明依赖规格、验证工具以及运行环境等可信基础,原论文的方法也有本地并发、崩溃恢复和客户端验证等范围限制。不能把“验证过一个协议实现”扩展成操作系统、硬件、部署和所有客户端都已经被验证。
这节课为调试提供另一种思考方式:遇到错误时,先写出被破坏的状态关系,再确认哪一次转换允许了它。即使暂时不使用验证器,这种表达也比凭感觉添加判断更容易复查。
