A STUDY OF CHECKPOINTING ALGORITHMS FOR MOBILE SYSTEMS

Abstract

Computing systems are vulnerable to many failure modes. In mobile computing systems likelihood of failure increases with the number of processes and a single failure often renders the entire system unusable. Checkpointing and rollback recovery is a common technique used for increasing the system reliability against various anticipated and unanticipated failures. Checkpointing can be used both for centralized and distributed systems. Recent integration of mobile computing devices to the general distributed systems elevates the problem of checkpointing distributed systems manifold and renders the conventional checkpointing protocols useless. Coordinated checkpointing is an attractive approach for adding fault tolerance to distributed applications since it avoids domino effects and minimizes the stable storage requirement. The main emphasis of this dissertation is on designing a checkpointing algorithm for distributed systems with mobile hosts. Coordinated checkpointing can be useful for mobile distributed computing systems provided that only minimum number of processes checkpoint and the protocol is non—blocking . But, if minimum number of process checkpointing is combined with non-blocking, the resulting protocol may force many useless checkpoints that are discarded at the completion of checkpoint. We have designed an efficient coordinated checkpointing protocol that is non-blocking, requires coordination of only a minimum number of processes and reduces the overhead of useless checkpoints greatly. The simulation studies show that our protocol reduces the number of useless checkpoints almost to zero. The simulations were carried out on Pentium IV machine in WINDOWS environment.