Placing Decentralized Learners Where Network Delay Bursts Coincide

In decentralized training, each machine trains its own copy of a model and repeatedly averages it with a few neighbors. A synchronous round finishes only when the slowest neighbor exchange finishes. The placement question is which physical machine hosts which logical position in the communication graph. Current methods answer it with a fixed delay matrix, as if network latency were a constant. Real wide-area links instead show bursts: queues fill, cross-traffic spikes, and then things calm down. This is the same failure that signal processing faced when it moved past "stationary" noise models, meaning models whose statistics never change. We propose to treat link delay the way modern speech enhancement treats non-stationary noise: as a slowly drifting baseline plus a structured burst process that is worth modeling explicitly rather than averaging away.

Once delay is modeled that way, a counterintuitive placement rule follows. A synchronous round stalls if any one of its links is bursting. It is therefore cheaper to put the logical edges onto physical links whose bursts happen at the same time than onto links that burst independently. Two independent bursty links stall roughly twice as many rounds as two links that always burst together. The core claim is that, under bursty and spatially correlated delays, the placement that minimizes wall-clock training time is set by the joint burst structure, which arises naturally from shared physical paths. It is not set by per-link mean or tail delays. We further claim that a placement chosen this way, combined with fast and cheap reweighting during bursts, beats repeatedly re-solving the placement as delays change.

Core Claim

Let $\phi$ map logical nodes of a decentralized-learning graph to physical hosts. Let $d_{ij}(t)$ be the delay from host $i$ to host $j$ in round $t$. The per-round bottleneck is

$$B_\phi(t) = \max_{(u,v) \in E_L} d_{\phi(u)\phi(v)}(t),$$

where $E_L$ is the set of logical edges. Bottleneck Communication Delay Minimization for Communication-Efficient Decentralized Learning introduced this bottleneck view and minimizes $B_\phi$ for a static, symmetric $d$, using a 2-approximation solver (BTSP-MSR) for circulant graphs such as rings and exponential graphs. The authors state the static, symmetric assumption explicitly as a limitation.

We instead decompose delay into two parts:

$$d_{ij}(t) = \bar d_{ij}(t) + \sum_{\ell \in P_{ij}} b_\ell(t).$$

Here $\bar d_{ij}$ is a slowly varying baseline, $P_{ij}$ is the set of physical links on the route from $i$ to $j$, and $b_\ell(t) \ge 0$ is a burst process on physical link $\ell$. Because many overlay pairs route over the same physical links, their delays co-burst. We choose $\phi$ to minimize $\mathbb{E}[B_\phi]$, or its conditional tail, under the fitted model.

For an expected maximum, joint structure matters at first order. With $k$ logical edges that each burst with probability $p$, the stall probability is $p$ if the edges share one burst domain and $1-(1-p)^k$ if their bursts are independent. A placement that looks only at marginal delays cannot see this difference.

The same model also predicts the opposite preference for sequential microservice chains, whose latency is a sum of link delays. There, correlation inflates tail latency, so decorrelation is preferred. We use this sign flip as a falsifiable secondary prediction.

Relation to Prior Work

Several placement papers motivate this work by showing that the communication topology matters but assuming away its dynamics. BTSP-MSR treats delays as constants, as described above. Topology-aware Microservice Architecture in Edge Networks: Deployment Optimization and Implementation maps microservice chains onto edge links using steady-state M/M/1 queues, a standard queueing model that assumes stationary random arrivals. It tests bandwidth fluctuations only as random, unstructured perturbations, and it optimizes placement before execution. Topology-Aware Knowledge Propagation in Decentralized Learning weights neighbors by graph centrality on a known, static, idealized graph. All three ignore the time structure of link delay. Our proposal keeps their graph-embedding view and replaces the delay input with a stochastic, path-correlated model.

The closest runtime competitor is Reducing Training Time in Cross-Silo Federated Learning using Multigraph Topology. It labels links as fast or slow using a latency threshold and temporarily isolates slow nodes, which then train asynchronously. The authors acknowledge that sustained isolation causes local bias, meaning isolated models drift from the global objective. That method changes which edges are used. Ours changes where nodes sit, so that bursts hurt less in the first place. The two can be combined, and we test the combination.

The noise literature supplies both the diagnosis and the method. Bhiksha Raj et al. and E. van Heerden et al. show that stationary noise templates break under bursty interference, producing artifacts and false detections. Dong Yu et al. track signal-to-noise ratio frame by frame instead of averaging over a whole utterance. We borrow that idea to track $\bar d$ and the burst component per round. Shuo Wang et al. estimate an unknown noise profile from the corrupted mixture itself. Analogously, we fit the burst model only from the delays of links the training job already uses, plus sparse probes, so no global measurement campaign is needed. Interactive Speech and Noise Modeling for Speech Enhancement argues that interference is a structured signal that deserves its own model rather than a residual. Our explicit burst-and-correlation term is the network analogue of that argument.

AdaKWS: Towards Robust Keyword Spotting with Test-Time Adaptation constrains our design. It found that adapting a model during deployment from small batches was unstable, while large batches were too slow to follow fast shifts. We read this as a warning against re-solving placement from short delay windows, which would chase noise. That is why our design separates a slow re-placement loop from a fast reweighting loop.

Research Program

The system has three parts.

The first is an online delay model. Each round, it updates the baseline $\bar d$ with a slow exponential filter. It fits a per-physical-link burst process, a two-state on/off model with heavy-tailed burst magnitudes, by attributing excess overlay delay to the physical links on each route. The attribution uses non-negative least squares over the routing matrix. The output is a co-burst covariance estimate over overlay pairs.

The second is a correlation-aware placement solver. It starts from the BTSP-MSR solution computed on $\bar d$, which preserves the circulant structure that solver requires. It then runs local search over node swaps, scoring each candidate by a Monte Carlo estimate of $\mathbb{E}[B_\phi]$ drawn from the fitted model. Hata and Niwa report that the exact integer-programming solver SCIP "failed to find any solution within a 30-minute time limit" at scale, so we deliberately avoid exact solving.

The third is a two-timescale controller. Re-placement, which costs a model migration, fires only when a change-point test on $\bar d$ or on the burst covariance triggers, and only if the predicted gain over a horizon exceeds the migration cost. During individual bursts, the controller does not move nodes. It softly reweights gossip mixing coefficients away from currently bursting edges for the duration of the burst. This is a continuous version of the binary isolation used in multigraph methods.

The analysis component has two parts. We will derive the expected-max gap between correlated and independent burst placements under the on/off model, using the union-versus-shared-event argument above. We will also characterize when the correlation term vanishes: when bursts are independent across physical links, or when routes are disjoint. In those regimes our method should reduce to percentile-based placement, which defines the method's honest scope.

Baselines

The naive reference is random placement with standard synchronous gossip. This is the comparison point Hata and Niwa used. On the 87-node Ebone topology, they report that BTSP-MSR reduces bottleneck delay by "approximately 23%" for rings and "6–16%" for exponential graphs relative to random placement, under static delays. No reported result was found on Lacuna for any placement method under non-stationary or bursty delays. Our first deliverable is to establish these numbers.

The strongest existing placement method is BTSP-MSR. We run it in two variants. The first uses the long-run mean delay matrix. The second uses a per-link 95th-percentile delay matrix, a robust marginal version that a careful practitioner would try first. Both see the same delay traces our method sees, use the same physical topology and logical graph, and receive the same wall-clock compute budget for solving.

The strongest runtime competitor is the multigraph strategic-isolation method of Do et al. On Exodus with FEMNIST, they report a communication cycle time of 12.1 ms versus 24.7 ms for a ring, at 71.13% versus 71.05% accuracy. Across their network suite, they report an 18.5× to 21.9× wall-clock speedup over a star topology. We run it on our bursty traces with its latency threshold tuned over the same grid budget we use for our own hyperparameters. We also run it on top of our placement, to test whether the two methods are complementary or redundant.

The adaptive competitor is a sliding-window re-solver. It re-runs BTSP-MSR every $W$ rounds on recent delays and is charged the same migration cost as our method, with $W$ tuned over the same budget.

The key ablation is our full system with the burst covariance replaced by an independent burst model that has identical per-link marginals. It isolates whether joint structure, rather than better marginal tracking, drives any gain. A second ablation removes the fast reweighting loop. An oracle that knows future delays and re-places for free gives an upper bound.

Beating the field means two things. Our method must reduce wall-clock time to target accuracy and 95th-percentile per-round bottleneck relative to both percentile BTSP-MSR and the sliding-window re-solver, on at least the majority of topologies and burst regimes. Final accuracy must stay within noise of synchronous training, as Do et al. demonstrated for their method. The correlation ablation must lose most of that gain.

Why not just…?

Why not just re-run BTSP-MSR periodically on recent delays? This is the most serious threat. If bursts last longer than a migration takes to pay off, periodic re-solving could match our method. If bursts are short, it will chase them, which mirrors AdaKWS's finding that short-window adaptation destabilizes. The sliding-window baseline, with its window tuned and migration cost charged honestly, settles this question directly. We will report the burst-lifetime regime in which it wins. If it wins across realistic regimes, the contribution narrows to the placement objective alone.

Why not just place on high-percentile delays? Percentile placement guards each link marginally, but by construction it cannot tell co-bursting links from independent ones, and the expected maximum depends on exactly that difference. The independent-burst ablation is the clean test. If percentile BTSP-MSR matches our method, the joint-structure claim is false for these networks, and we will say so.

Why not just isolate slow nodes at runtime as the multigraph method does? Isolation reacts after a burst has started and accumulates local bias under non-IID data, as Do et al. acknowledge. It also leaves the placement, and therefore future co-burst exposure, unchanged. Running isolation both alone and on top of our placement shows whether placement adds anything beyond runtime reaction.

Why not just learn placement end to end with reinforcement learning? Policy-gradient placement has been applied to edge-cloud microservices in Efficient Microservice Deployment in the Edge-Cloud Networks With Policy-Gradient Reinforcement Learning. However, it offers no structural guarantee and needs many episodes on each new topology. We treat it as a secondary baseline at a matched interaction budget rather than as the main competitor, because an explicit delay model is far more sample-efficient when bursts arise from routing structure that is already known.

Proposed Experiments

The physical topologies are Ebone, Exodus, Gaia, Amazon, and Geant, as used by Do et al. and Hata and Niwa, with shortest-path routing defining each $P_{ij}$. Neither paper supplies non-stationary delay traces. We therefore generate them by injecting on/off cross-traffic bursts on physical links, sweeping three factors: burst duty cycle, burst lifetime relative to round time, and the number of independent burst sources. Because bursts are injected on physical links, correlation emerges from shared routes rather than being imposed by hand. We will also report a regime where bursts are independent by construction, to check the predicted reduction to percentile placement.

The training tasks follow the prior papers: CIFAR-10 with LeNet-5 and CIFAR-100 with ResNet-18 on ring, exponential, and 1-peer exponential graphs, as in Hata and Niwa, plus FEMNIST, as in Do et al. All use non-IID partitions. Metrics are mean and 95th-percentile per-round bottleneck delay, wall-clock time to a fixed target accuracy, final accuracy, the number of migrations, and solver time.

Three decisive checks would most change our belief. First, the correlation ablation must account for most of the improvement over percentile BTSP-MSR. Second, in a controlled two-link sweep, the measured stall rate must track the shared-versus-union prediction. Third, the sign-flip prediction must hold. We test it with a small simulated sequential-chain experiment that uses the delay-sum objective of Chen et al.'s three-tier model in place of M/M/1 delays. The prediction is that correlation-aware placement there prefers decorrelated links. If it prefers correlated links instead, the delay model is wrong. If both results go the predicted way, the general lesson is that placement under bursty networks should be scored by how its objective combines delays across links, maximum or sum, rather than by any per-link delay number.