Tecnologias Movile Bajo Cost

oLow-Cost Checkpointing and Failure Recovery in Mobile Computing Systems
Ravi Prakash and Mukesh Singhal Department of Computer and Information Science The Ohio State University Columbus, OH 43210. e-mail: fprakash, singhalg@cis.ohio-state.edu
A mobile computing system consists of mobile and stationary nodes, connected to each other by a communication network. The presence of mobile nodes inthe system places constraints on the permissible energy consumption and available communication bandwidth. To minimize the lost computation during recovery from node failures, periodic collection of a consistent snapshot of the system (checkpoint) is required. Locating mobile nodes contributes to the checkpointing and recovery costs. Synchronous snapshot collection algorithms, designed for staticnetworks, either force every node in the system to take a new local snapshot, or block the underlying computation during snapshot collection. Hence, they are not suitable for mobile computing systems. If nodes take their local checkpoints independently in an uncoordinated manner, each node may have to store multiple local checkpoints in stable storage. This is not suitable for mobile nodes as theyhave small memory. This paper presents a synchronous snapshot collection algorithm for mobile systems that neither forces every node to take a local snapshot, nor blocks the underlying computation during snapshot collection. If a node initiates snapshot collection, local snapshots of only those nodes that have directly or transitively a ected the initiator since their last snapshots need to betaken. We prove that the global snapshot collection terminates within a nite time of its invocation and the collected global snapshot is consistent. We also propose a minimal rollback/recovery algorithm in which the computation at a node is rolled back only if it depends on operations that have been undone due to the failure of node(s). Both the algorithms have low communication and storage overheadsand meet the low energy consumption and low bandwidth constraints of mobile computing systems.

Abstract

Key words: checkpointing, causal dependency, global snapshot, mobile computing
systems, portable computers, recovery.

1

1 Introduction
A mobile computing system is a distributed system where some of nodes are mobile computers 3]. The location of mobile computers in the network maychange with time. The xed nodes in the system are connected by a static network. A mobile node communicates with the other nodes in the system through a xed node to which it is connected. The nodes have no common clock and no shared memory among them. They communicate with each other through messages. Each node operates independently of the others, with occasional asynchronous messagecommunication. In this paper we concentrate on the checkpointing and recovery aspects of mobile computing systems. In synchronous checkpointing algorithms, a consistent snapshot of the system (also called a checkpoint) is maintained at all times. In asynchronous algorithms, the constituent nodes take their local snapshots independently, and a local snapshot is selected for each node to construct a consistentsnapshot of the system at the time of recovery. A consistent global snapshot indicates a possible state of the system if the local states of all the nodes and the messages in transit along all the channels are recorded simultaneously. In a consistent global snapshot, the reception of a message is recorded by a node only if the corresponding send has been recorded. If a node fails, the system isrolled back to the latest consistent global snapshot 13, 20, 22, 25, 26], and then the computation proceeds from that point onwards. To minimize the lost computation during recovery from node failures, periodic collection of a consistent snapshot of the system to advance the checkpoint is required. Thus, collection of a consistent snapshot of a mobile system is an important issue in the recovery...