  Dealing with hardware and software faults is an important problem as parallel
and distributed systems scale to millions of processing cores and wide area
networks. Traditional methods for dealing with faults include
checkpoint-restart, active replicas, and deterministic replay. Each of these
techniques has associated resource overheads and constraints. In this paper, we
propose an alternate approach to dealing with faults, based on input
augmentation. This approach, which is an algorithmic analog of erasure coded
storage, applies a minimally modified algorithm on the augmented input to
produce an augmented output. The execution of such an algorithm proceeds
completely oblivious to faults in the system. In the event of one or more
faults, the real solution is recovered using a rapid reconstruction method from
the augmented output. We demonstrate this approach on the problem of solving
sparse linear systems using a conjugate gradient solver. We present input
augmentation and output recovery techniques. Through detailed experiments, we
show that our approach can be made oblivious to a large number of faults with
low computational overhead. Specifically, we demonstrate cases where a single
fault can be corrected with less than 10% overhead in time, and even in extreme
cases (fault rates of 20%), our approach is able to compute a solution with
reasonable overhead. These results represent a significant improvement over the
state of the art.
