🔢 mathematics

Fault Tolerance of Accelerated Asynchronous Fixed-Point Iterations on Flexible Computing Infrastructure

This paper demonstrates that while asynchronous execution universally provides significant wall-clock speedups for fixed-point iterations, the effectiveness of Anderson acceleration in this setting depends critically on the staleness mechanism: it fails when staleness directly corrupts the accelerated iterate but remains beneficial when staleness acts as a bounded perturbation to the fixed-point map evaluation.

Original authors: Evan Coleman, Masha Sosonkina

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Evan Coleman, Masha Sosonkina

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive jigsaw puzzle with a team of friends. In a traditional, "synchronous" approach, everyone works on their own section, but you have to stop and wait for the slowest person before anyone can move to the next step. If one friend is distracted or slow (a "straggler"), the whole team sits idle.

Now, imagine an "asynchronous" approach. Here, everyone keeps working immediately on whatever information they have, even if it's slightly outdated because they haven't heard from the slow friend yet. This keeps the team moving fast, but it introduces a risk: you might be building your piece of the puzzle based on a picture that doesn't quite match what your neighbors are seeing.

This paper investigates two big questions about this "keep moving" strategy:

Does it actually save time? (Yes, it does, even with slow workers).
Can we use a "smart shortcut" to solve the puzzle even faster, even when everyone is working with outdated info? (Sometimes yes, sometimes no, and it depends on how the puzzle pieces are connected).

Here is a breakdown of their findings using simple analogies.

1. The "Straggler" Problem: Speed vs. Consistency

The researchers tested three different types of "puzzles" (mathematical problems):

The Grid (Jacobi): Like a grid of lights where each light only cares about its immediate neighbors.
The Game (Value Iteration): Like a board game where every move depends on the entire board state.
The Chemistry Model (SCF): Like a complex chemical simulation where every atom feels the pull of every other atom.

The Finding:
When they introduced a "slow worker" (a delay of 100 milliseconds), the asynchronous team was 2.9 to 16.9 times faster than the team that waited for everyone.

Analogy: It's like a relay race where the runners don't wait for the baton to be perfectly handed off; they just keep running. Even if they stumble a bit because of the messy handoff, they finish the race much sooner than a team that waits for perfect coordination.

2. The "Smart Shortcut" (Anderson Acceleration)

In math, there are "accelerators" (like Anderson Acceleration) that act like a coach. The coach looks at the last few moves the team made and says, "Hey, based on this pattern, if we jump here instead of taking small steps, we'll solve it faster."

The researchers wanted to know: Does this coach work when the team is running asynchronously with outdated info?

The answer was surprising and depended entirely on the type of puzzle:

Case A: The "Local" Puzzle (Jacobi) -> The Coach Fails

In the Grid problem, each worker only knows about their immediate neighbors.

The Analogy: Imagine a group of people painting a wall. Each person only paints a small square and only looks at the squares touching theirs. If the coach tries to predict the final wall color based on these tiny, isolated squares, the prediction is garbage.
The Result: When the workers used outdated info, the "coach" (accelerator) actually made things worse. It tried to jump ahead based on a pattern that didn't exist, causing the team to overshoot and have to start over. The "shortcut" broke the system.

Case B: The "Global" Puzzles (Game & Chemistry) -> The Coach Works

In the Game and Chemistry problems, every worker's calculation depends on the entire state of the system.

The Analogy: Imagine a group of people trying to predict the weather. Even if they are looking at slightly old data, because the weather in one city affects the weather in another, every single person's report contains information about the whole world.
The Result: Here, the "coach" (accelerator) still worked. Even though the data was slightly stale, the "stale-ness" was just a small, manageable error (like a slight wind shift). The coach could still see the big picture and guide the team to a faster solution.

The "Secret Sauce": Coupling Density

The paper concludes that the success of the "coach" doesn't depend on how hard the math is or how smooth the equations are. It depends on Coupling Density.

Low Coupling (Jacobi): Your piece of work only depends on a tiny, local part of the problem. If you use old data, you are building on a broken foundation. The coach can't help.
High Coupling (Game/Chemistry): Your piece of work depends on the entire problem. Even if the data is old, it still reflects the global picture. The coach can still see the path forward.

Summary of Results

Speed: Asynchronous methods are always faster (up to 17x faster) when workers are slow, regardless of the problem type.
Acceleration:
- If your problem is locally connected (like a grid), adding a "smart coach" to an asynchronous team will likely fail.
- If your problem is globally connected (like a game or chemical simulation), the "smart coach" succeeds and speeds things up further.

The Bottom Line:
If you are building a system where workers only know about their immediate neighbors, don't try to use complex acceleration tricks if you expect delays; just let them work asynchronously and accept the extra work. But if your workers are looking at the big picture, you can safely add those acceleration tricks to get even more speed.

Technical Summary: Fault Tolerance of Accelerated Asynchronous Fixed-Point Iterations on Flexible Computing Infrastructure

Problem Statement

As computing infrastructures increasingly rely on heterogeneous, cloud-based, and preemptible resources, traditional bulk-synchronous fixed-point iterations face two critical liabilities: sensitivity to "straggler" processors (where the slowest node dictates wall-clock time) and fragility to hardware faults (requiring costly restarts). While asynchronous iterative methods offer a solution by allowing workers to proceed with stale data, they introduce inconsistencies that can degrade convergence rates or alter the fixed point.

Concurrently, convergence accelerators like Anderson acceleration (and its quantum chemistry equivalent, DIIS) are widely used to speed up synchronous iterations. However, a significant gap exists in understanding whether these accelerators can compensate for the inconsistencies introduced by asynchrony. It is unclear if the theoretical guarantees of acceleration hold when the underlying map evaluations are perturbed by stale data, or if the acceleration mechanism itself is destroyed by the asynchronous update pattern.

Methodology

The authors investigate this gap through a systematic empirical study using a high-performance execution framework built on Ray. This framework abstracts distributed system complexity, enabling controlled fault injection (specifically, delayed workers) and minimal code changes for parallelization.

The study focuses on three distinct fixed-point iterations, chosen to span a theoretical landscape of varying contraction norms and map regularity (smoothness):

Jacobi Iteration (Sparse Linear Systems): A linear, smooth map contracting in the $\ell_2$ -norm.
Value Iteration (Bellman Equation): A nonlinear, non-smooth map (due to the max operator) contracting in the $\ell_\infty$ -norm.
Hartree–Fock SCF Iteration: A nonlinear, smooth map with variable contraction properties depending on correlation strength, tested using the Pariser–Parr–Pople (PPP) model.

In all experiments, Anderson acceleration is applied at a coordinator level. The coordinator maintains a history of global iterates and residuals, solving a least-squares problem to extrapolate a new iterate, which is then distributed to workers. The study compares synchronous execution against asynchronous execution with injected delays (up to 100 ms) and evaluates the impact of acceleration under these conditions.

Key Contributions and Findings

1. Universal Straggler Tolerance

The authors establish that asynchronous execution provides universal wall-clock speedups over synchronous execution, independent of whether acceleration is used. Even with a 100 ms delayed worker, the asynchronous variants achieved speedups of:

2.9× for Jacobi
7.7× for Value Iteration
16.9× for SCF
This speedup comes at the cost of increased total work (more worker-updates), but the reduction in wall-clock time is substantial.

2. The Critical Role of "Coupling Density"

The paper's primary contribution is identifying that the success of Anderson acceleration under asynchrony is not determined by the contraction norm ( $\ell_2$ vs. $\ell_\infty$ ) or the smoothness of the map. Instead, it depends on coupling density: the fraction of the global iterate that each worker's computation depends on.

The authors distinguish two mechanisms of staleness:

Iterate-Level Corruption (Low Coupling): Occurs in Jacobi on sparse systems. Workers return partial updates that overwrite specific blocks of the solution. Because these updates encode only local boundary information, the stale returns directly overwrite the extrapolated solution generated by the coordinator. This destroys the structure of the Anderson subspace, causing acceleration to fail categorically regardless of window size or firing frequency.
Evaluation-Level Perturbation (High Coupling): Occurs in Value Iteration and SCF. In these problems, a worker's update for a specific state or basis function depends on the entire global vector (via the transition matrix or two-electron integrals). Consequently, staleness acts as a bounded perturbation to the fixed-point map evaluation ( $\tilde{G}(x) = G(x) + e$ ). Under this mechanism, Anderson acceleration retains its benefits, consistent with perturbation analysis by Toth et al. (2017).

3. Specific Experimental Results

Jacobi: Anderson acceleration actively hurts convergence in asynchronous mode. The method requires 40–60% more work than unaccelerated asynchronous Jacobi and can diverge if the acceleration frequency is too high.
Value Iteration: Anderson acceleration provides consistent speedups (1.2×–1.7×) in both synchronous and asynchronous modes. The benefit scales with the discount factor $\gamma$ (up to 1.7× at $\gamma=0.99$ ). The study also found that greedy state selection outperforms uniform random selection.
SCF: At weak correlation, coordinator-level DIIS successfully corrects the asynchronous bias, converging to the correct fixed point (though with more iterations than the synchronous case). At intermediate correlation ( $U/|t|=2.5$ ), convergence becomes stochastic; interestingly, moderate delays (20 ms) were observed to improve reliability by effectively serializing worker contributions, whereas high delays (100 ms) caused failure.

Significance and Claims

The paper claims to resolve a theoretical puzzle: why Anderson acceleration fails for the "easiest" problem (linear, smooth Jacobi) but succeeds for "harder" problems (nonlinear, non-smooth Value Iteration). The authors argue that the determining factor is system design (how workers partition and return work) rather than the mathematical properties of the map.

The significance of this work lies in providing a practical criterion for predicting the viability of acceleration in asynchronous distributed systems:

If the problem structure ensures high coupling (workers compute full map evaluations on stale data), acceleration is likely to survive and provide benefits.
If the problem structure involves low coupling (workers return partial updates that overwrite specific blocks), acceleration will likely fail, and alternative strategies (such as returning full residual vectors) may be required.

The authors conclude that while straggler tolerance is a universal benefit of asynchronous execution, the integration of convergence accelerators requires careful consideration of the information content within worker returns. This distinction offers a new lens for designing fault-tolerant, accelerated algorithms on flexible computing infrastructure.