ERASURE CODING FOR FAULT-OBLIVIOUS LINEAR SYSTEM SOLVERS

作者：Zhu Yao^*; Gleich David F; Grama Ananth

来源：SIAM Journal on Scientific Computing, 2017, 39(1): C48-C64.

DOI：10.1137/15M1041511

• erasure coding
• linear system solvers
• fault oblivious computation
• algorithm based fault tolerance

Dealing with faults is an important problem as parallel and distributed systems scale to millions of processing cores. 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, where we present input augmentation and output recovery techniques. Through simulations, 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.

• 出版日期2017