Fault Tolerance of Accelerated Asynchronous Fixed-Point Iterations on Flexible Computing Infrastructure Conference: The 35th International Symposium on High-Performance Parallel and Distributed Computing; July 13–16, 2026; Cleveland, OH, USA The 35th International Symposium on High-Performance Parallel and Distributed Computing (HPDC ’26), July 13–16, 2026, Cleveland, OH, USA DOI: 10.1145/3806645.3816236 ISBN: 979-8-4007-2640-8/2026/07 CCS: Computer systems organization Cloud computing CCS: Mathematics of computing Numerical analysis CCS: Computing methodologies Parallel algorithms

Evan Coleman, Masha Sosonkina · 2026

Read Fault Tolerance of Accelerated Asynchronous Fixed-Point Iterations on Flexible Computing Infrastructure Conference: The 35th International Symposium on High-Performance Parallel and Distributed Computing; July 13–16, 2026; Cleveland, OH, USA The 35th International Symposium on High-Performance Parallel and Distributed Computing (HPDC ’26), July 13–16, 2026, Cleveland, OH, USA DOI: 10.1145/3806645.3816236 ISBN: 979-8-4007-2640-8/2026/07 CCS: Computer systems organization Cloud computing CCS: Mathematics of computing Numerical analysis CCS: Computing methodologies Parallel algorithms by Evan Coleman, Masha Sosonkina (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-28426.txt.

Introduction

Evan Coleman and Masha Sosonkina test whether speed-up methods rescue asynchronous iterative methods when some processors lag. Using the Ray tool, they run Jacobi, Bellman value iteration, and Hartree-Fock iterations with a delayed worker. Straggler tolerance holds in all three cases whether speed-up is used or not. Anderson acceleration, however, fails when stale returns corrupt the iterate, yet keeps its gains when stale data only perturbs the map test.

Catalog record

CREATOREvan Coleman, Masha Sosonkina
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40291
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.28426

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fault Tolerance of Accelerated Asynchronous Fixed-Point Iterations on Flexible Computing Infrastructure Conference: The 35th International Symposium on High-Performance Parallel and Distributed Computing; July 13–16, 2026; Cleveland, OH, USA The 35th International Symposium on High-Performance Parallel and Distributed Computing (HPDC ’26), July 13–16, 2026, Cleveland, OH, USA DOI: 10.1145/3806645.3816236 ISBN: 979-8-4007-2640-8/2026/07 CCS: Computer systems organization Cloud computing CCS: Mathematics of computing Numerical analysis CCS: Computing methodologies Parallel algorithms Evan Coleman, Masha Sosonkina Abstract . Asynchronous iterative methods tolerate straggling processors by allowing workers to proceed with stale data, but at a cost: the iterates become inconsistent, potentially degrading convergence. We investigate whether convergence accelerators such as Anderson acceleration compensate for this degradation. We experimentally study three fixed-point iterations: the Jacobi method for sparse linear systems, value iteration for the Bellman equation, and the Hartree–Fock self-consistent field (SCF) iteration. The experiments are conducted using a high-performance execution framework Ray, which abstracts the complexity of distributed systems and enables code parallelization and fault injection with minimal changes. We establish two main results. First, straggler tolerance is universal: asynchronous execution provides wall-clock speedups of 2.9 × 2.9\times (Jacobi), 7.7 × 7.7\times (VI), and 16.9 × 16.9\times (SCF) over synchronous execution with a 100 ms-delayed worker, independent of whether acceleration is used. Second, Anderson acceleration’s effectiveness under asynchrony depends on where staleness enters the computation. We identify two staleness mechanisms: iterate-level corruption, where stale worker returns directly overwrite portions of the accelerated iterate (as in block Jacobi), and evaluation-level perturbation, where staleness acts as a bounded perturbation to the fixed-point map evaluation (as in VI and SCF). Anderson acceleration fails categorically under the first mechanism but retains its benefits under the second, consistent with the perturbation analysis of Toth et al. (2017). This distinction, rather than the contraction norm or smoothness of the map, is the primary determinant of whether acceleration survives asynchronous execution. † † cc-license: by 1. Introduction Fixed-point iterations, {x}^{(k+1)}=G({x}^{(k)}) , are found in many places throughout scientific computing. Classical iterative solvers for linear systems (Jacobi, Gauss–Seidel, Richardson), value iteration for Markov decision processes, and self-consistent field (SCF) iterations in electronic structure theory are prominent examples. In standard parallel implementations, these methods execute in a bulk-synchronous fashion: all processors complete the current iteration before any can begin the next. This model is straggler-sensitive (a single slow processor determines the wall-clock time of each step), as well as fragile (any hardware fault during an iteration typically requires discarding partial results and restarting from a checkpoint). As computing platforms grow more heterogeneous and adopt cloud-based and preemptible resources, both liabilities become increasingly costly. Asynchronous iterative methods, first analyzed by Chazan and Miranker ( 9 ) and unified by Frommer and Szyld ( 17 ) , offer a possible alternative. In the asynchronous model, each processor updates its block of the solution using whatever information is currently available, potentially including stale values. When the underlying map is contractive, convergence is guaranteed under a bounded-delay assumption, although the asynchronous iteration may converge at a different rate, or to a different fixed point. Separately, convergence accelerators like Anderson acceleration ( 1 ) (equivalently, DIIS in quantum chemistry ( 25 ) ) have long been used to speed up synchronous fixed-point iterations. These methods maintain a window of recent iterates and their residuals, then extrapolate to reduce the error. Their behavior under asynchronous execution, however, has received almost no study. This is a significant gap: if acceleration can compensate for the inconsistencies introduced by staleness, it could substantially broaden the regime in which asynchronous methods are practical. In this paper, we take a step toward closing this gap through systematic empirical investigation. We present a Ray-based experimental framework ( 21 ) for studying fault tolerance of asynchronous fixed-point iterations under controlled injection of delay. We study three iterations of increasing complexity: (1) Jacobi iteration for sparse linear systems. This is a linear fixed-point map whose asynchronous convergence is fully characterized by the spectral radius of the iteration matrix ( 9 ; 17 ) . The iteration contracts in the \ell_{2} -norm, and the Walker–Ni equivalence ( 34 ) gives a reference convergence rate for the accelerated synchronous case. (2) Value iteration for the Bellman optimality equation. This is a nonlinear fixed-point map involving the non-smooth \max operator, contractive in the \ell_{\infty} -norm with contraction constant \gamma (the discount factor) ( 8 ) . Asynchronous value iteration is well studied ( 7 ) , but its combination with Anderson acceleration raises subtle theoretical questions: the \ell_{2} -norm least-squares problem at the heart of Anderson acceleration is mismatched to the \ell_{\infty} -contraction of the Bellman operator, and the non-smoothness of \max violates regularity assumptions in existing convergence analyses ( 33 ) . Recent work has applied Anderson acceleration to synchronous value iteration ( 18 ; 28 ; 29 ) ; we look to extend this by testing it under asynchronous execution with delays. (3) SCF iteration for electronic structure. This is a nonlinear fixed-point map whose contraction properties vary with problem parameters. We use the Pariser–Parr–Pople (PPP) model Hamiltonian ( 23 ; 24 ) as a testbed with tunable nonlinearity. To our knowledge, no prior work studies SCF under asynchronous execution These three problems span two axes of difficulty for Anderson-type acceleration, summarized in Table 1 . The first axis is the contraction norm: Jacobi and SCF contract in the \ell_{2} -norm, where Anderson’s least-squares residual minimization is naturally well-matched, while value iteration contracts in the \ell_{\infty} -norm, creating a norm mismatch. The second axis is the regularity of the map: the Bellman operator’s \max is non-differentiable, which invalidates the quasi-Newton interpretation of Anderson acceleration ( 16 ) and the smoothness assumptions in convergence proofs ( 33 ) , while Jacobi and SCF are both smooth. By testing the same coordinator-level acceleration mechanism on all three, we can begin to disentangle which theoretical properties are actually necessary for Anderson acceleration to correct async bias. Table 1. Theoretical landscape of the three test problems. Problem Linear? Contraction Smooth? Anderson theory Jacobi Yes \|\cdot\|_{2} Yes = GMRES ( 34 ) Value iter. No \|\cdot\|_{\infty} No Open / heuristic SCF No \|\cdot\|_{2} Yes Local ( 33 ) In all three settings, we apply Anderson acceleration at the coordinator level; the same algorithmic mechanism under different names (Anderson mixing for Jacobi and VI, DIIS for SCF), and study whether it can compensate for the convergence degradation introduced by staleness. Our central finding is that the answer depends not on the contraction norm or smoothness properties ( Table 1 ), but on how staleness enters the computation relative to the Anderson subspace. We identify two distinct mechanisms: • Iterate-level corruption (Jacobi): stale worker returns directly overwrite portions of the coordinator’s extrapolated iterate, destroying the subspace correction. Anderson fails at every window size and firing frequency tested. • Evaluation-level perturbation (VI, SCF): staleness acts as a bounded perturbation to the fixed-point map evaluation, \widetilde{G}({x})=G({x})+{e} , where \|{e}\| is controlled by the contraction constant. Anderson retains its acceleration properties, consistent with the perturbation analysis of Toth et al. ( 32 ) . This distinction provides a practical criterion for predicting whether acceleration will survive asynchronous execution: if the worker’s computation produces a full evaluation of the fixed-point

Read the complete text