基于泛洪的可靠广播算法分析

摘要

由于非一致性可靠广播问题的普遍性,针对该问题已经形成了很多算法,其中最重要的是T.D.Chandra和S.Toueg提出的基于泛洪的可靠广播算法.对该算法的分析,已有的文献或者忽略,或者只是基于简短的自然语言分析.为了深入理解上述算法,对其活动性和安全性进行了严格的分析和证明.在系统模型为Fail-Silent进程和全互联,可靠的通讯子系统的条件下,首先分析了算法的执行逻辑和执行状态.在对算法的活动性分析中得出的结论:允许故障的条件下会出现接收员进程终止于状态S'0的情况.在对算法的安全性分析中得出的结论:系统中如果存在一个进程终止在SN状态,其他所有进程或者终止在SF状态或者终止在SN状态.