Decentralized training lets each machine average its model with a few neighbors at each step instead of with everyone. Recent work designs clever neighbor patterns, called logical topologies, that reach exact agreement in a few rounds while each machine talks to very few peers. These designs are scored by logical degree, meaning how many peers a machine contacts. Real clusters and cross-silo deployments, however, are wired as oversubscribed trees of racks, pods, and wide-area uplinks. Two machines that are logical neighbors may sit on opposite sides of a thin uplink, and many logical pairs can end up sharing that one link. Wall-clock cost is set by how badly the busiest physical link is overloaded, which we call congestion. Logical degree does not measure this.
This note proposes to measure and design for that cost directly. The main tool comes from an unexpected place. Results in parameterized complexity show that routing many point-to-point transfers along non-overlapping paths is intractable even on very tree-like networks. We read those results as a design constraint. Do not ask the network for disjoint paths. Instead, split each model transfer into chunks and route them fractionally, which a linear program solves in polynomial time. On tree-shaped fabrics congestion then reduces to counting how many communicating pairs straddle each cut. Once congestion is just a cut count, the real freedom left to the designer becomes visible. That freedom is which physical machine plays which logical node, and in what order the rounds are run.
Core Claim
For decentralized SGD with finite-time consensus graphs on hierarchical or oversubscribed fabrics, the right cost of one consensus round is its physical congestion, not its logical degree. Choosing the host placement and round order to follow the fabric's cut structure should cut time-to-accuracy substantially, with no change to the optimizer.
Concretely, let round $t$ of a consensus schedule require a set of host pairs $D_t$ to exchange messages of $b$ bytes. Let $c_t$ be the minimum, over fractional routings on the physical fabric, of the maximum ratio of link load to link capacity. The communication time of a schedule is then approximately
$$T = \sum_t \left( b \, c_t + \lambda \right),$$
where $\lambda$ is per-round latency. On a tree fabric each pair has a unique path, so the load on a link $e$ is simply the number of pairs in $D_t$ separated by removing $e$. This makes $c_t$ an exact, cheap cut count.
There is also a second-order effect that only this view exposes. After the rounds internal to a rack finish, every machine in that rack holds an identical model. The next cross-rack exchange can therefore be split into shards, with each rack member sending only its own $1/m$ slice, where $m$ is the rack size. This divides uplink load by $m$ while keeping consensus exact.
What the Complexity Results Do and Do Not Tell Us
The graph-routing literature supplies the constraint. Ganian et al. show that edge-disjoint routing is W[1]-hard parameterized by tree-cut width, although it is polynomial for each fixed width (The Power of Cut-Based Parameters for Computing Edge Disjoint Paths). The structural study of the same problem shows it stays W[1]-hard even when the physical graph plus the demand pairs has bounded treewidth or feedback vertex set. That study finds fixed-parameter algorithms only under joint treewidth-and-degree parameters, with running times of $2^{O(\Delta\omega\log\omega)} n$ that are unusable at switch radices (On Structural Parameterizations of the Edge Disjoint Paths Problem). On directed graphs, Lorenz et al. show hardness persists even when bounded congestion is allowed (Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors; Directed Disjoint Paths Remains W[1]-Hard on Acyclic Digraphs Without Large Grid Minors). The directed tangle work recovers tractability only for half-integral relaxations (Directed Tangle Tree-Decompositions and Applications).
Taken together, these results argue against any design that needs integral, collision-free paths for model exchanges, whether exact or with small bounded sharing. Model tensors are megabytes to gigabytes and are chunked anyway, so fractional routing costs essentially nothing in practice. This is why we do not follow the research file's suggestion that fractional splitting is too costly for gradient traffic. The integrality-gap bounds for bounded-treewidth graphs (On Routing Disjoint Paths in Bounded Treewidth Graphs) matter only for single-packet demands, which is not our regime.
The complexity lens still does useful positive work. The tree-cut decompositions that underlie Ganian et al.'s cut-based parameters give a natural host placement for fabrics that are almost trees. We use those decompositions to guide placement, not to solve routing.
The distributed-training literature supplies the objects we place. The BASE-$(k+1)$ graph of Takezawa et al. reaches exact consensus in $O(\log_{k+1} n)$ rounds for any number of nodes $n$ and degree $k$. It is evaluated purely as a logical mixing matrix, and the paper assumes each logical edge is a free link (Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence). Its digit-wise construction is what makes placement meaningful. Rounds that mix low-order digits can be made rack-local, and rounds that mix high-order digits cross uplinks.
Zhou et al. analyze two-tier Star/Ring hierarchies under non-IID data and find that a ring top tier wins. They treat the tiers as overlays with zero routing interference, so they motivate our question without answering it (Unified Analyses for Hierarchical Federated Learning: Topology Selection under Data Heterogeneity). Birch SGD models training as a tree of iterates in time and ignores the physical wires entirely (Birch SGD: A Tree Graph Framework for Local and Asynchronous SGD Methods). Canary shows that congestion on shared switch links dominates allreduce time in multi-tenant clusters. Its fix is heuristic, packet-level, and specific to programmable switches, and it does not touch decentralized schedules (Canary: Congestion-Aware In-Network Allreduce Using Dynamic Trees).
Research Program
The first component is a congestion evaluator. It takes a physical fabric with link capacities and a consensus schedule, and returns $c_t$ for each round. On trees it uses exact cut counting. On general fabrics (fat-trees, tori, multi-site meshes) it solves a min-congestion multicommodity flow linear program. We will then check how well $T$ predicts measured round time in packet-level simulation, using ATLAHS and ns-3.
The second component is a placement-and-ordering procedure for digit-structured finite-time consensus schedules. The procedure takes a tree or tree-cut decomposition of the fabric. It assigns the least significant digits of the BASE-$(k+1)$ node labels to the deepest subtrees and runs rounds from innermost to outermost. Whenever a group of hosts has reached internal consensus, it switches the next outward round to sharded exchange. For fabrics that are not trees, we add local search over placements, scored by the linear-program evaluator.
The theoretical target has two parts. The first is a bound on the schedule's congestion in terms of the fabric's tree-cut width and subtree sizes. The second is a proof that on oversubscribed trees the aligned placement is optimal among all placements of that schedule. This optimality is plausible because each cut's load becomes the minimum number of pairs that must cross it. The second part is a conjecture we will try to prove, and if it fails we will report a counterexample.
The third component plugs these schedules into decentralized SGD and into local SGD with decaying local-step counts (Faster Federated Learning With Decaying Number of Local SGD Steps). There, synchronization becomes frequent late in training, so congestion should matter most exactly when the decay schedule is working hardest.
Baselines
The naive reference point is BASE-$(k+1)$ decentralized SGD with a random host placement. This is what a practitioner gets by launching workers in arbitrary rank order. A second naive reference is the same schedule with rank order following the job scheduler's host list. Beating these references shows that placement matters at all.
The strongest competitor on wall-clock time is hierarchical exact averaging. That means topology-aware reduce-scatter inside racks, averaging across racks, then broadcast inside racks, run either every step or every $K$ local steps, as in the hierarchical federated setting. We also run the Ring-Ring hierarchy of Zhou et al., which on CIFAR-10 with ResNet-18 is reported at about 91.5% accuracy versus about 88.5% for Star-Star (Unified Analyses for Hierarchical Federated Learning: Topology Selection under Data Heterogeneity). This baseline is strong because it already exploits the physical hierarchy by hand. Our method must beat it on time-to-target-accuracy on an oversubscribed fabric, or else the contribution shrinks to the cost model alone.
On the consensus side, the reference is BASE graphs' reported exact consensus in 10–20 iterations for 100 to 1000 nodes, with ring and torus graphs still far from consensus after 50 (Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence). No reported CIFAR accuracy numbers for BASE graphs were found on Lacuna. We also include the Exponential graph with a physically optimized placement, which tests whether higher degree is recoverable once placement is fixed.
All methods share the same model, data split (Dirichlet $\alpha \in \{0.1, 10\}$), step budget, and simulated fabric. Each method gets an equal learning-rate and local-step grid search. Two ablations isolate the key ingredients. The first uses aligned placement without sharded outward exchange. The second uses sharding with random placement. Only their combination should give the full uplink reduction.
Why not just…?
Why not just rely on adaptive packet routing such as ECMP or dynamic in-network trees? Adaptive routing spreads load across parallel paths, but it cannot shrink the number of pairs that must cross a single oversubscribed uplink, because on a tree there is only one path. Canary still reports that static aggregation loses about 40% of performance under 32 concurrent reductions, and it needs Tofino switches (Canary: Congestion-Aware In-Network Allreduce Using Dynamic Trees). We run all our simulations with ECMP enabled, so any gain we report is on top of adaptive routing.
Why not just communicate rarely, with very large local-step counts? Photon trains a 7B model while communicating 64× to 512× less often and reaches 16.9% lower perplexity than a centralized baseline (Photon: Federated LLM Pre-Training). This is a real threat for near-IID pre-training. Under strong heterogeneity, however, large fixed step counts cause client drift. Decaying the step count gives an 18% CIFAR-100 accuracy gain over fixed counts (Faster Federated Learning With Decaying Number of Local SGD Steps), and that forces frequent synchronization late in training. Our decaying-step experiment tests whether congestion-aware schedules keep that gain while cutting its wall-clock cost. If large fixed step counts match our time-to-accuracy at $\alpha = 10$, we will report that the method matters only in the heterogeneous regime.
Why not just use topology-aware hierarchical allreduce, which libraries already do? This is the most serious alternative, and it is our main baseline rather than a straw man. Hierarchical allreduce is itself a sharded, hierarchy-aligned exact average. Our method differs in two ways. It spreads the cross-rack cost over decentralized steps, so no single step pays the full uplink bill. It also generalizes to non-tree fabrics through the evaluator and local search. If hierarchical local SGD matches us on every fabric, we will report that finding. The cost model would then stand as an explanation of why hierarchy-aligned methods win, and logical-degree metrics as a misleading design target.
Proposed Experiments
The first check tests the cost model. We generate BASE-$(k+1)$, Exponential, ring, and torus schedules under many random placements on three fabrics: a two-level tree with 1:4 and 1:16 oversubscription, a fat-tree under background multi-tenant traffic, and a three-site wide-area topology. We then measure how well congestion $c_t$ and logical degree each rank-correlate with simulated round time in ATLAHS. The claim fails if degree predicts round time as well as congestion does.
The second check is end-to-end training. It covers CIFAR-10 and CIFAR-100 with ResNet-18 at $n$ from 64 to 1024 simulated workers under Dirichlet splits, and FEMNIST and Shakespeare with decaying local steps. We report time-to-target-accuracy, final accuracy, and bytes carried on the most loaded link, against the baselines above.
The third check is a controlled emulation on a real GPU cluster. We rate-limit rack uplinks to confirm that the simulated gains survive real stacks.
The decisive outcome is threefold. Aligned, sharded BASE schedules must beat random placement by a margin that grows with the oversubscription ratio. They must match or beat hierarchical local SGD on time-to-accuracy on the oversubscribed tree. And the gain must shrink toward zero on a full-bisection fat-tree, where congestion is uniform and placement should not matter. Seeing the gain vanish on that fabric is the internal control that the mechanism is the one we claim.
References
- The Power of Cut-Based Parameters for Computing Edge Disjoint Paths
- On Structural Parameterizations of the Edge Disjoint Paths Problem
- Directed Disjoint Paths Remains W[1]-Hard on Acyclic Digraphs Without Large Grid Minors
- Directed Tangle Tree-Decompositions and Applications
- On Routing Disjoint Paths in Bounded Treewidth Graphs
- Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence
- Unified Analyses for Hierarchical Federated Learning: Topology Selection under Data Heterogeneity
- Birch SGD: A Tree Graph Framework for Local and Asynchronous SGD Methods
- Canary: Congestion-aware in-network allreduce using dynamic trees
- ATLAHS: An Application-centric Network Simulator Toolchain for AI, HPC, and Distributed Storage
- Faster Federated Learning with Decaying Number of Local SGD Steps
- Photon: Federated LLM Pre-Training