A Hybrid Coordinated Checkpointing Protocol for Mobile Computing Systems

Minimum-process coordinated checkpointing is a suitable approach to introduce fault tolerance in mobile distributed systems transparently. The approach is domino-free, requires at most two checkpoints of each process and only minimum number of processes to checkpoint. At times, it requires piggybacking of some information with normal messages, blocking of the underlying computation or taking some checkpoints more than the minimum required. In minimum-process checkpointing, some processes, which are not part of minimum set, may not take checkpoints for several checkpoint initiations, and thus may starve to checkpoint. In case of recovery after a fault, this may lead to their rollback to far earlier checkpointed states and thus may cause greater loss of computation. In coordinated checkpointing, where all processes checkpoint, the recovery line is advanced for each process but the checkpointing overhead may be exceedingly high, especially in mobile environments; because, all mobile nodes need to checkpoint even if some may be disconnected or in doze mode operation. To balance the checkpointing overhead and the loss of computation on recovery, we propose a hybrid coordinated checkpointing algorithm, where an all-process coordinated checkpointing is forced after the execution of minimum-process coordinated checkpointing algorithm for a fixed number of times. Thus, the Mobile nodes with low activity or in doze mode operation may not be disturbed during minimum-process checkpointing and the recovery line is advanced for all processes after an all-process checkpoint. Additionally, we also optimize the piggybacked information, avoid blocking and minimize the number of useless checkpoints.