The Computer Journal Advance Access originally published online on February 17, 2006
The Computer Journal 2006 49(5):527-540; doi:10.1093/comjnl/bxk004
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Design and Evaluation of a Low-Latency Checkpointing Scheme for Mobile Computing Systems
1 School of Computer Science and Technology, Huazhong University of Science and Technology P. R. China
2 Department of Accountancy, National Cheng Kung University Taiwan 701, ROC
*Corresponding author: shulc{at}mail.ncku.edu.tw
Fault-tolerant mobile computing systems have different requirements and restrictions, not taken into account by conventional distributed systems. This paper presents a coordinated checkpointing scheme which reduces the delay involved in a global checkpointing process for mobile systems. A piggyback technique is used to track and record the checkpoint dependency information among processes during normal message transmission. During checkpointing, a concurrent checkpointing technique is designed to use the pre-recorded process dependency information to minimize process blocking time by sending checkpoint requests to dependent processes at once, hence saving the time to trace the dependency tree. We show that our checkpoint algorithm forces a minimum number of processes to take checkpoints, which is an important property for checkpointing mobile applications. Via probability-based analysis, we show that our scheme can significantly reduce the latency associated with checkpoint request propagation, compared with traditional coordinated checkpointing approaches. Experimental results indicate that we have <2% overhead in transmitting piggybacked information during normal runtime. However, we can achieve up to a 60% reduction in checkpoint latency time.
Key Words: Fault tolerance • mobile computing systems • rollback recovery • causal dependency • coordinated checkpointing