Erasure coding for fault oblivious linear system solvers

David F. Gleich, Ananth Grama, Yao Zhu

Abstract

As high-performance computing (HPC) systems scale toward exascale, the probability of hardware failure increases significantly. Traditional fault-tolerance mechanisms, such as checkpoint-restart and active replication, face substantial overhead in these environments. This paper presents a novel approach to solving large-scale linear systems ($Ax = b$) that is inherently resilient to fail-stop errors. By applying erasure coding principles to matrix algebra, the authors develop a "fault-oblivious" solver that continues execution despite node failures, allowing for the reconstruction of the correct solution with minimal computational overhead.

Introduction

In the era of exascale computing, where systems comprise millions of processing cores, hardware and software faults are no longer rare anomalies but statistical certainties. The standard approach to resilience, checkpoint-restart, suffers from massive I/O bottlenecks as the state of the system is periodically saved to disk. Alternatively, active replication—running redundant instances of the same task—can double or triple hardware requirements, making it prohibitively expensive for large-scale scientific simulations.

This research addresses the challenge of solving Symmetric Positive Definite (SPD) linear systems in environments where processors may abruptly stop working. The goal is to achieve "algorithmic" fault tolerance: a system that does not require a global halt or a rollback when a component fails, but instead leverages mathematical redundancy to maintain progress.

Methodology: Input Augmentation and Erasure Coding

The core innovation of this work is the concept of input augmentation. Rather than protecting the state of the computation, the authors protect the problem itself by embedding the original $n \times n$ system into a larger, redundant $(n+k) \times (n+k)$ "encoded" system, where $k$ represents the number of simultaneous faults the system is designed to tolerate.

1. The Encoding Scheme

The authors design an augmented matrix $\tilde{A}$ and vector $\tilde{b}$ using an encoding matrix $E$. This process is analogous to adding parity bits in data storage. By making the system singular but consistent, the redundancy required to survive node crashes is stored within the "null space" of the augmented matrix.

2. The Fault-Oblivious Solver

The solver utilizes a modified Conjugate Gradient (CG) algorithm. In a distributed environment, if a process fails, the remaining processes do not stop to recover. Instead, they simply skip the faulty components during inner products and matrix-vector multiplications. The algorithm continues to iterate on a "purified" version of the system. This "fault-oblivious" nature is a significant departure from traditional methods; the mathematical properties of the augmented system ensure that the remaining nodes continue to converge toward a valid, albeit partial, solution.

3. Recovery and Kruskal Rank

Once the solver reaches convergence, the original solution $x$ is recovered from the augmented solution $\tilde{x}$ using a rapid reconstruction method. The success of this recovery regardless of which specific nodes fail depends on the Kruskal rank of the encoding matrix $E$. A high Kruskal rank ensures that any subset of the redundant data can be used to fill the gaps left by failed nodes. The authors demonstrate that simple random Gaussian matrices satisfy this property with high probability.

Experimental Evaluation

The approach was evaluated using three SPD test matrices representing different scientific domains:

  • Ltridiag500: A $500 \times 500$ matrix representing a 1D model problem.
  • mhdb416: A $416 \times 416$ matrix from an electromagnetics problem (University of Florida Sparse Matrix Collection).
  • nos3: A $960 \times 960$ matrix from a structural engineering problem.

Key Results

  • Computational Overhead: For the common case of a single fault, the time overhead was remarkably low, often staying below 10%.
  • Extreme Resilience: The solver demonstrated robustness even under extreme conditions, handling fault rates where up to 20% of components failed. While high failure rates increased the number of iterations (e.g., a 5x increase for the Ltridiag500 case), the system still successfully converged.
  • Numerical Precision: The accuracy of the recovered solution remained high. The relative residual—a measure of how well the solution satisfies the original equation—was nearly identical to fault-free baselines, typically reaching between $10^{-11}$ and $10^{-15}$.

Discussion and Future Work

The primary insight of this work is that fault tolerance can be integrated directly into linear algebra. By treating math as a safety net, the algorithm becomes resilient by design rather than through external system-level monitoring.

However, several areas for improvement remain. The current experiments utilized a simplified fault model where errors were injected simultaneously at the end of iterations. Future research will need to address "temporally interspersed" faults that occur at random intervals. Additionally, the use of dense Gaussian matrices for encoding presents a scaling challenge; the authors suggest that moving toward structured or sparse random projections will be necessary to reduce the computational cost of the augmentation phase. Finally, investigating "flexible CG" techniques may help stabilize and accelerate convergence in environments with very high fault rates.

Conclusion

Erasure coding for linear solvers provides a promising path toward truly resilient exascale computing. By shifting the burden of fault tolerance from the system level to the algorithmic level, this approach offers a high-precision, low-overhead alternative to traditional checkpointing and replication strategies.

Summary updated

BibTeX
@article{gleich2017erasure,
  author = {David F. Gleich and Ananth Grama and Yao Zhu},
  title = {{Erasure coding for fault oblivious linear system solvers}},
  journal = {SIAM J. Sci. Comput.},
  year = {2017},
  doi = {10.1137/15m1041511},
}
Figure