Hybrid checkpoint protocol with unreliable wireless channels

摘要

This paper proposes a novel checkpoint-recovery protocol for achieving fault-tolerant execution of an application in a mobile network system. The protocol is an implementation of hybrid checkpointing where fixed computers take local checkpoints by using a synchronous checkpoint protocol and mobile computers take local checkpoints by using asynchronous checkpoint protocol. Until now, two protocols of hybrid checkpointing have been designed. One is for systems with a communication model in which all messages transmitted from a mobile computer are transmitted through an access point even if the message is destined to another mobile computer within the same wireless cell. The other is for systems with a different communication model in which two mobile computers within the same wireless cell communicate directly without help of an access point. In the latter protocol, wireless communication channels are assumed reliable, that is, recovery of lost message is assumed to be supported by a protocol in underlying layer. Due to unreliable wireless communication channels and the existence of hidden terminals, more messages are lost than in a wired network. Even though an acknowledgment message and retransmission timer for reliable message transmission are applied, a message directly exchanged between mobile computers is not surely received by an access point. Hence, it is not certain to store required messages for replaying in recovery for a mobile computer to get a consistent state with other computers. In order to solve this problem, the proposed protocol supports that all the required messages are surely received by an access point before that fixed computers take local checkpoints by using a synchronous checkpoint protocol. In this protocol, each mobile computer temporarily stores messages sent after taking a local checkpoint in a buffer and each message carries event sequence of events on which the message causally depends. The proposed protocol includes a function of garbage collection for the messages in the buffers and the events in the messages.