On the cost of recomputing: Tight bounds on pebbling with faults

We introduce a formal framework to study the time and space complexity of c omputing with faulty memory. For the fault-free case, time and space comple xities were studied using the "pebbling game" model. We extend this model t o the faulty case, where the content of memory cells may be erased. The mod el captures notions such as "check points" (keeping multiple copies of inte rmediate results), and "recovery" (partial recomputing in the case of failu re). Using this model, we derive tight bounds on the time and/or space over head inflicted by faults. As a lower bound, we exhibit cases where f worst- case faults may necessitate an Omega(f) multiplicative factor overhead in c omputation resources (time, space, or their product). The lower bound holds regardless of the computing and recomputing strategy employed. A matching upper-bound algorithm establishes that an O(f) multiplicative overhead alwa ys suffices. For the special class of binary tree computations, we show tha t f faults necessitates only O(f) additive factor in space. (C) 2000 Elsevi er Science B.V. All rights reserved.