Search papers, labs, and topics across Lattice.
This paper investigates the impact of asynchronous execution and straggling processors on the convergence of fixed-point iterations, specifically Jacobi, Value Iteration (VI), and Hartree-Fock Self-Consistent Field (SCF) methods. They find that asynchronous execution provides significant speedups over synchronous execution, regardless of whether acceleration techniques like Anderson acceleration are used. However, the effectiveness of Anderson acceleration under asynchrony depends on the type of staleness introduced, with iterate-level corruption leading to failure and evaluation-level perturbation allowing it to retain its benefits.
Anderson acceleration, a popular technique for speeding up fixed-point iterations, completely fails under asynchronous execution when stale data directly overwrites iterates, revealing a critical sensitivity to how staleness enters the computation.
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\times$ (Jacobi), $7.7\times$ (VI), and $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.
