Efficient sequential and parallel algorithms for computing recovery points in trees and paths

Abstract

We present efficient sequential and parallel algorithms for the problem of finding an optimal placement of recovery points in a tree (and in a path) system. The placement of recovery points together with rollback mechanisms (which recover the latest such point) is a major fault-tolerance technique used in many systems. We achieve an O(n log n) time worst case algorithm for trees, which can be sped up when some problem parameters such as the number of recovery points, or the depth of the tree are small. For the important case of path systems we give an O(n log∗ n) algorithm. We also give efficient poly-logarithmic parallel (PRAM) algorithms for these problems.