一种基于移动计算环境的因果日志卷回恢复算法

由于移动节点的不可靠和无线网络连接的脆弱性,研究移动计算系统容错机制具有重要意义.对可以跨区移动、随时可以与网络断开的自治性很强的移动节点来说,异步的卷回恢复是一种重要的容错手段.现有的移动计算环境下的卷回恢复算法都无法完全实现一致的异步卷回恢复.基于因果消息日志,提出一种新的移动计算环境的卷回恢复算法:通过先行图来记录节点间的消息依赖关系,将异步检查点、基于发送方的暂存消息日志和先行图全部在移动支持站上存储和处理,为移动节点提供一种透明的容错服务,完全消除依赖关系在移动节点之间造成的影响.用形式化的方法证明了系统的一致性.仿真结果表明,在卷回开销达到最低的同时,也显著降低了无错运行时的通信和存储开销.

A Rollback Recovery Algorithm Based on Causal Message Logging in Mobile Environment

Due to the unreliable mobile hosts and the fragile network connection,it is significant to research on the fault tolerance of the mobile systems.Asynchronous rollback and recovery is suitable for the mobile hosts which move across cells and disconnect from the wireless networks from time to time.The existent rollback and recovery algorithms in the mobile computing environment can not completely implement consistent asynchronous recovery.A novel rollback recovery algorithm suitable to mobile environment based on causal message logging is presented.This algorithm takes advantage of antecedence graph to trace the message dependency of mobile hosts.Simultaneously,the storage of uncoordinated checkpoint,volatile sender-based message log and antecedence graph information is carried out on the mobile support station in order that the mobile hosts can gain a transparent fault tolerant service.This algorithm can tolerate multi-failures of mobile hosts when the mobile support station fails,and completely eliminate the effect of dependence among the mobile hosts.By means of formalization,the consistency of the system is proven.The simulation result shows that compared with the optimistic and pessimistic message logging,the causal message logging algorithm has the minimized rollback cost and communication,and storage cost in the failure free phase is enormously reduced.