Checkpoint Space Reclamation for Uncoordinated Checkpointing in Message- Passing Systems

Abstract

Uncoordinated check pointing allows process autonomy and general nondeterministic execution, but suffers from potential domino effects and the associated space overhead. Previous to this research, checkpoint space reclamation had been based on the notion of obsolete checkpoints; as a result, a potentially unbounded number of nonobsolete checkpoints may have to be retained on stable storage. In this paper, we derive a necessary and sufficient condition for identifying all garbage checkpoints. By using the approach of recovery line transformation and decomposition, we develop an optimal checkpoint space reclamation algorithm and show that the space overhead for uncoordinated check pointing is in fact bounded by N(N + 1)/2 checkpoints where N is the number of processes.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1991
Accession Number
ADA274186

Entities

People

  • In-jen Lin
  • Pi-yu Chung
  • W. Kent Fuchs
  • Yi-min Wang

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Materials and Manufacturing Processes
  • Space

DTIC Thesaurus Topics

  • Algorithms
  • Autonomy
  • Computers
  • Decomposition
  • Engineering
  • Fault Tolerance
  • Fault Tolerant Computing
  • Guarantees
  • Illinois
  • Intervals
  • Military Research
  • New York
  • Reclamation
  • Recovery
  • Simulations
  • Universities

Readers

  • Calculus or Mathematical Analysis
  • Parallel and Distributed Computing.

Technology Areas

  • Space
  • Space - Spacecraft Maneuvers