Asynchronous recovery without using vector timestamps

doi:10.1016/S0743-7315(02)00005-9

Asynchronous recovery without using vector timestamps

2002-12-01

33

PRE

AI

DOI：10.1016/S0743-7315(02)00005-9

Original

Original request for help

Save

Abstract

En 中文

A checkpoint of a process involved in a distributed computation is said to be useful if it is part of a consistent global checkpoint. In this paper, we present a quasi-synchronous checkpointing algorithm that makes every checkpoint useful. We also present an efficient asynchronous recovery algorithm based on the checkpointing algorithm. The checkpointing algorithm allows the processes to take checkpoints asynchronously and also forces the processes to take additional checkpoints in order to make every checkpoint useful. The recovery algorithm can handle concurrent failure of multiple processes. The recovery algorithm has no domino effect and a failed process needs only to roll back to its latest checkpoint and request the other processes to roll back to a consistent checkpoint. Messages are only selectively logged to cope with various types of message abnormalities that arise due to rollback and hence results in low message logging overhead. Unlike some existing algorithms, our algorithm does not use vector timestamps for tracking dependency between checkpoints and hence results in low message overhead during failure-free operation. Moreover, a process can asynchronously decide garbage checkpoints and delete them from the stable storage-garbage checkpoints are the checkpoints that are no longer required for the purpose of recovery. (C) 2002 Elsevier Science (USA). All rights reserved.

Keywords:

distributed checkpointing

quasi-synchronous checkpointing

communication-induced check-pointing

failure-recovery

fault-tolerance

rollback-recovery

vector timestamps

multiple failures

asynchronous recovery

Asynchronous recovery without using vector timestamps

Abstract

AI Summary

Journal

Organization