A Hybrid Coordinated Checkpointing Protocol for Mobile Computing Systems

Abstract

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.

Indexing terms:

• Fault tolerance
• Checkpointing
• Consistent global state
• Coordinated checkpointing
• Mobile systems

Additional information

Notes on contributors

Parveen Kumar

Parveen Kumar received his MCA from Kurukshetra University in 1989 and MS (Software Systems) from BITS Pilani in 2001. He is working as Programmer in National Institute of Technology Hamirpur (HP) since 1989. He is doing his PhD on Checkpointing based fault tolerance in mobile distributed systems and contributed more than 15 articles in journals and international conferences.

Lalit Kumar

Lalit Kumar received his MTech (Computer Sc & Engg) from IIT Delhi in 1993 and PhD from IIT Roorkee in 2003. He is in the faculty of Computer science and Engineering, National Institute of Technology Hamirpur (HP) since 1989. Presently, he is holding the position of Assistant Professor and Head of the Department. His research interests include mobile distributed systems, checkpointing based fault tolerance and Ad hoc Networks. He has contributed more than 35 articles in national and international journals as well as conferences.

R K Chauhan

R K Chauhan received doctoral degree in computer science from Kurukshetra University Kurukshetra, India in 2000. He works in the field of mobile computing, ad hoc networks, databases and GIS. Since 1989, he has been on the faculty of Computer Science and Applications, Kurukshetra university. He is a member of CSI