Adaptive Row Selection Meets Asynchrony in Randomized Kaczmarz

Randomized Kaczmarz is a natural fit for large sparse least-squares and tomographic reconstruction, and adaptive row selection can reduce iteration counts.

However, deploying adaptive selection on a shared-memory machine means sampling from a residual that lock-free workers are concurrently modifying, often using stale data.

We present the first systematic study of this regime: residual-weighted and greedy Kaczmarz under asynchronous execution, measured across 339 runs on a 96-core node with realized (not injected) delays.

Four findings carry directly to practice.

(i) Stability is governed by a boundary $\ell^*(T)$ between sampling aggressiveness and thread count; below it, more aggressive sampling is strictly better, so one should tune to just inside the cliff.

(ii) Threshold-greedy selection (the standard accelerated rule) is unstable at high thread counts, diverging almost immediately.

(iii) Under-relaxation buys back the cliff at a predictable cost, giving a usable safety knob.

(iv) Consistent-snapshot reads admit a rare, scheduling-dependent divergence that live (inconsistent) reads never exhibited and that is also cheaper, making inconsistent reads the right default.

We validate the implementation against published sequential results and outline the distributed two-level sampler these measurements motivate.