Research On Low Overhead Non-blocking Checkpointing Scheme For Mobile Computing System

Wireless networks are becoming explosive growth recently. Unfortunately, solutions to reliability of wireless network are getting more and more difficult compared to fixed wired networks. Since the probability of system failures is dramatically increasing while the sophistication level and knowledge to conduct attacks have been decreasing. Consequently, the research of fault-tolerance in mobile computing environment has theoretical contributions as well as practical application future.Fault tolerance of rollback recovery is achieved by periodically using stable storage to save the states of processes during failure-free execution. To deal with a failure, a failed process restarts from one of its former saved states, which therefore reduces the amount of lost computation. The optimizing schemes such as checkpointing cost reduction, checkpoints optimal interval discovery, which are presented in uniprocessors checkpointing can be adopted in the distributed checkpointing scenario. Furthermore, distributed systems complicate rollback recovery, since that transmit messages introduce inter-process dependencies during failure-free operation. It is desirable to reduce the overhead of checkpointing; and at the same time, keep the domino-effect freedom to ensure the consistent global checkpoints.When applied to mobile computing systems, checkpoint protocols for distributed computing systems would face many new challenges, such as low wireless bandwidth, frequent disconnections and lack of stable storage at mobile hosts. This thesis proposes an efficient checkpoint protocol to effectively reduce the coordinating overhead. By using a communication vector, the number of processes that participate in the checkpointing event is reduced. During checkpointing, the proposed scheme can save the time in tracing the dependency tree by sending checkpoint requests to dependent processes synchronously. In addition, processes are non-blocking in this scheme, since the inconsistency is resolved by the piggyback technique. This strategy addresses the problem of unnecessary and orphan messages. Compared to traditional coordinated checkpoint approach, the proposed non-blocking algorithm minimizes the number of processes to take checkpoints, as well as reducing the checkpoint latency, which brings less overhead to mobile system with limited resources.