Distributed learning methods that avoid waiting for slow workers were designed for wired clusters. There, each worker's delay is treated as an independent random draw, and a "straggler" is just an unlucky draw. Over a dense wireless network the picture is different, because the workers are each other's slowdown. While many devices upload gradients at once, every transmission adds interference to every other link, so uploads fail and repeat. As devices finish, the air clears and the remaining uploads speed up. The time to collect the $K$-th gradient is therefore an ordered sequence of completions in which each finisher shortens the wait for the rest. It is not the $K$-th fastest of $N$ independent clocks. Separately, the workers that finish last are not random. They are the ones with geometrically bad positions, such as cell-edge devices, and they finish last almost every round.
This note proposes to model these two effects, which we call self-relief and spatial persistence, and to build a quorum-and-access rule on them. The core claim is falsifiable. In the interference-limited regime, two consequences follow. First, the wall-clock benefit of waiting for only the fastest $K$ workers is much smaller than independent-delay theory predicts, and the best quorum moves toward full synchronization as device density grows. Second, the residual stragglers form a fixed spatial subset, so dropping them biases training toward devices in good locations. A rule that adapts the uplink access probability to the number of workers still uploading, and gives priority to persistent stragglers once the quorum is nearly met, should beat both full synchronization and partial-quorum schemes tuned for wired settings.
Background and the gap
Two literatures sit on either side of this problem. On the straggler side, Slow and Stale Gradients Can Win the Race analyzes K-sync and asynchronous SGD under independent exponential delays. It shows a "$P \log P$" wall-clock speedup and argues for optimizing error reduction per second; this is the analysis whose independence assumption we challenge. Taming unbalanced training workloads continues once a majority of workers has reported, giving 1.27x–2.64x speedups on wired clusters. Gradient Coding and Coding for Straggler Mitigation in Federated Learning recover exact gradients from any $n-s$ workers, at the cost of each worker processing at least an $(s+1)/n$ share of the data. All four treat the communication fabric as idealized; the coded federated work uses a fixed LTE delay model with no spatial interference. They supply the methods we compare against, and our claim is that their delay model is wrong in the regime we target.
On the wireless side, the network-level results motivate the work. Percolation and Connectivity on the SIR Graph shows that connectivity holds only inside a bounded density window, and that full connectivity needs $O(\log n)$ orthogonal resources. MDC Enhanced IoT Networks shows that higher packet rates activate more transmitters and lower coverage, but it models passive telemetry rather than closed-loop learning. The Waterfilling Game-Theoretical Framework finds network rate peaking at about 14 transmitters for 10 receivers. None of these papers asks how order statistics of upload completion behave when the set of transmitters shrinks as uploads finish.
The closest bridge papers address a different straggler. Relay-Assisted Cooperative Federated Learning treats the weakest channel in analog over-the-air aggregation within a single cell with perfect channel knowledge and no inter-cell interference. Adaptive Federated Learning Over the Air models interference phenomenologically as heavy-tailed noise, requires tight synchronization, and does not address timing stragglers. Argus argues that asynchrony is needed in space–air–ground networks but does not model interference scaling. Our proposal differs from all three in two ways: delays arise endogenously from a spatial interference field, and the decision variables are the quorum and the access probability.
Core model and claim
We place devices participating in learning, across many cells, as a Poisson point process of density $\lambda$, with each receiver at distance $r$ from its access point. Uplinks use slotted random access, in which each still-uploading device transmits with probability $q$ in each slot. With Rayleigh fading, path-loss exponent $\alpha$, $\delta = 2/\alpha$, and decoding threshold $\theta$, the standard interference-limited success probability gives the per-area completion rate of the still-uploading density $\lambda_t$:
$$\frac{d\lambda_t}{dt} = -\,q\,\lambda_t \exp\!\left(-c\, q\, \lambda_t\, \theta^{\delta} r^2\right), \qquad c = \pi\,\Gamma(1+\delta)\Gamma(1-\delta).$$
The exponential factor is the self-relief mechanism. When $\lambda_t$ is large, completions are throttled. As $\lambda_t$ falls, each remaining device succeeds faster. In the dense regime, the time spent between the $K$-th and $N$-th completion is a small fraction of the round, because by then the medium is nearly empty. Under independent exponential delays, that fraction is large. The equation also gives a backlog-adaptive access probability, $q_t = 1/(c\,\lambda_t\,\theta^\delta r^2)$, which maximizes the instantaneous completion rate. Its derivation uses only quantities a server can estimate: the count of outstanding uploads and long-term average geometry.
Distance $r$ varies across devices, so the last finishers are those with large $r$ and many close interferers. The same devices lag every round. This is spatial persistence. Dropping them excludes a fixed geographic, and in practice data-distribution, slice of clients. This matters because Gradient Coding already found that ignoring stragglers hurts held-out AUC even when they are random.
Research Program
We build three things. The first is a mean-field predictor of the time to $K$ completions, $T_K(\lambda, q)$, from the equation above. We validate it against Monte Carlo simulation, then combine it with a standard per-round progress model to obtain error reduction per second as a function of $K$. This gives a predicted optimal quorum $K^\*(\lambda)$, which we compare against the one implied by the exponential model in Slow and Stale Gradients Can Win the Race.
The second is the controller, which we call self-relief access. It sets $q_t$ from the outstanding-upload count. Once fewer than a small number of uploads remain, it raises the access priority of those devices, which are typically persistent stragglers, at almost no cost, since the medium is nearly empty. Its quorum is $K^\*(\lambda)$, recomputed whenever measured density changes.
The third is a characterization near the dense end of the percolation window of Percolation and Connectivity on the SIR Graph. There, self-relief may fail because some devices are in outage even with no other transmitters active. The model should predict where full synchronization becomes infeasible and a quorum is truly required.
Baselines
The naive reference is full-synchronization federated averaging with a fixed access probability: the server waits for every device each round. It sets the floor and shows how large the raw straggler cost is.
The strongest existing quorum method is K-sync SGD with $K$ chosen by the independent-exponential analysis of Slow and Stale Gradients Can Win the Race, together with majority-quorum eager-SGD from Taming unbalanced training workloads. On wired clusters, eager-SGD reports a 2.64x speedup over asynchronous centralized SGD and 1.29x over Horovod on ImageNet ResNet-50, and 1.27x on UCF101. No reported result was found on Lacuna for either method under spatial interference.
The strongest exact-gradient competitor is coded federated learning from Coding for Straggler Mitigation in Federated Learning, which reports up to a 9.2x speedup to 85% on Fashion-MNIST and 6.6x to 95% on MNIST over conventional federated learning in its LTE-delay simulation.
The analog-aggregation competitor is Adam-OTA from Adaptive Federated Learning Over the Air, which reports about 70% CIFAR-10 accuracy in roughly 200 rounds with non-IID Dirichlet(0.1) data. We add neighboring-cell concurrent transmissions to its setting.
Fairness rules apply to every method. All see the same device placements, fading realizations, data partitions, model, local-step count, and wall-clock budget, measured in slots. Each gets the same hyperparameter search budget. The strongest reference is an oracle grid search over $K$ and fixed $q$ at each density.
Ablations isolate each ingredient: backlog-adaptive $q_t$ without priority boosting, priority boosting with fixed $q$, and $K^\*$ from the mean-field model versus the exponential model. Beating the baselines means two things. In time to target accuracy, the method must be faster than tuned K-sync and coded federated learning at densities above the noise-to-interference transition. It must also come within 10% of the oracle grid search without per-density search. Separately, final accuracy on the persistently straggling clients' data must match full synchronization.
Why not just…?
Why not just grid-search $K$ and $q$ empirically? This is the real threat. If density is fixed and known, a sweep finds the best static setting, and our method's only advantage would be the adaptive $q_t$ within a round. The experiments measure exactly this through the oracle baseline. If the oracle's static optimum matches self-relief access, the contribution shrinks to the predictive model, which still says how $K^\*$ shifts with $\lambda$. If the oracle loses because no fixed $q$ fits both the crowded early part of a round and the empty late part, the controller is justified. A second test changes density mid-training, which a one-time sweep cannot track.
Why not just orthogonalize the uplinks? Percolation and Connectivity on the SIR Graph shows that orthogonal resources must grow as $O(\log n)$ for full connectivity. Adaptive Federated Learning Over the Air notes that orthogonal digital access makes aggregation time linear in the number of clients. We include a time-division baseline at matched spectrum to measure where it loses.
Why not just run asynchronous SGD? The guarantees in An Asynchronous Mini-Batch Algorithm require a bounded maximum delay, with an $O(\tau_{\max}^4/T^2)$ penalty. Persistent cell-edge stragglers make delays large and correlated with data, so their stale gradients carry a systematic bias rather than random noise. We run asynchronous SGD with staleness tracking and report per-region accuracy.
Why not just drop stragglers with a timeout? If stragglers are spatially persistent, a timeout acts as a fixed data filter, which is worse than the random dropping already shown to hurt AUC in Gradient Coding. The per-region accuracy metric tests this directly.
Proposed Experiments
The testbed follows the Monte Carlo setup in MDC Enhanced IoT Networks: a 1000 m × 1000 m plane with Poisson-placed access points and devices, $10^4$ Rayleigh realizations, and slotted random access, with multiple cells running learning at once. We couple this channel simulator to training on CIFAR-10 with Dirichlet(0.1) partitions, Fashion-MNIST, and MNIST, so results can be read against the numbers above. We assign data partitions both randomly and correlated with location, mimicking regional user populations. Metrics are slots to target accuracy, final accuracy overall and on the 10% of clients with worst geometry, and total transmission attempts as a proxy for energy.
Three decisive checks follow. First, the mean-field $T_K$ must match the simulated $K$-th completion times. The ratio of $T_N$ to $T_K$ should fall with density as the model predicts, while the independent-exponential model predicts a roughly constant gap. If the simulated ratio does not fall, self-relief is not real and the proposal fails. Second, the identity of the slowest decile across rounds should overlap far above chance; measuring this overlap tests persistence. Third, in the location-correlated split, quorum baselines should lose worst-region accuracy relative to full synchronization, and self-relief access should recover it at near-quorum wall-clock time. We repeat all three across densities spanning the noise-limited regime, the interference-limited regime, and the dense edge of the percolation window.
References
- Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD
- Taming Unbalanced Training Workloads in Deep Learning with Partial Collective Operations
- Gradient Coding: Avoiding Stragglers in Distributed Learning
- Coding for Straggler Mitigation in Federated Learning
- Percolation and connectivity on the signal to interference ratio graph
- MDC Enhanced IoT Networks: Network Modeling and Performance Analysis
- The Waterfilling Game-Theoretical Framework for Distributed Wireless Network Information Flow
- Relay-Assisted Cooperative Federated Learning
- Adaptive Federated Learning Over the Air
- Argus: Federated Non-convex Bilevel Learning over 6G Space-Air-Ground Integrated Network
- An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization