About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 1991
Conference paper
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.