Don’t Let a Few Network Failures Slow the Entire AllReduce Peiqing Chen1 Jiedong Jiang2 Nengneng Yu1 Yuefeng Wang3 Sixian Xiong1 Wei Wang1 Zaoxing Liu1
arXiv:2606.01680v1 [cs.DC] 1 Jun 2026
1
University of Maryland, College Park
2
Utrecht University
3
Kyoto University
Abstract Network failures are among the most frequent hardware faults in large-scale GPU clusters and a leading cause of training-job interruptions. Modern collective communication libraries such as NCCL mitigate network failures by rerouting traffic through surviving NICs on the same server, trading reduced inter-node bandwidth for uninterrupted training. However, the degraded server remains on the critical path of the standard ring algorithm, slowing the entire collective. We present the first information-theoretic lower bound on AllReduce completion time under asymmetric network bandwidth and show that when the straggler retains at least half of its original bandwidth, the unavoidable overhead relative to the faultfree optimum is only O(1/p) for p GPUs. We then design O PT CC, a four-stage pipelined AllReduce algorithm that approaches this lower bound. Experiments on SimAI confirm that O PT CC closes the gap left by existing fault-tolerant schemes: under practical network failures with up to 50% bandwidth loss, O PT CC completes AllReduce within 2–6% of NCCL’s fault-free ring performance, whereas the stateof-the-art incurs up to 57% overhead.
1
Introduction
Network failures, including NIC, cable, and port faults, are among the most frequent hardware faults in large-scale GPU clusters, wasting 10–15% of GPU hours in production training runs [9, 12, 6, 4]. Recent systems mitigate these failures by rerouting the traffic on these GPUs through surviving NICs on the same server via PXN [17], keeping the training job alive without a full restart [10, 25, 22] (Figure 2). However, this reduces the affected server’s aggregate inter-node bandwidth, turning its GPUs into stragglers—GPUs whose effective network bandwidth is lower than their healthy peers. On mainstream multi-NIC servers such as those with H100 or B100 GPUs, losing a single NIC cuts bandwidth by 12.5%. The collective most affected by this bandwidth degradation is the AllReduce used for data-parallel gradient synchronization [5, 14, 21]. Ring AllReduce [18, 27, 15] is bandwidth-optimal on homogeneous links, but this optimality breaks down on heterogeneous topologies [32]; a network failure creates precisely such asymmetry. After failover, existing systems resume the standard Ring AllReduce without adapting to the asymmetric bandwidth, causing congestion at the straggler’s degraded link that throttles the entire collective. Even the most sophisticated optimization among these [30] still incurs up to 57% increase in AllReduce runtime when 50% of the bandwidth is lost on a single straggler. Existing approaches leave a significant performance gap between fault-free AllReduce and the degraded setting; in this paper, we aim to close it. Our key insight is that a straggler’s irreducible contribution to AllReduce is inherently small: to guarantee correctness, the straggler must transmit its own private data at least once, but all remaining data transfers can be handled entirely by healthy GPUs. Crucially, these two parts use physically separate links—the straggler’s slow link and the healthy GPUs’ fast links—so they can proceed in parallel. Since the straggler’s bandwidth is only one out of p links in the cluster, a well-designed
Table 1: Theoretical lower bounds on straggler overhead relative to the fault-free baseline T0 ; p: number of GPUs; ℓ (resp. ℓi ): straggler slowdown factor; ℓ1 = maxi ℓi . For one GPU per server, T0 = 2(p−1)n/p; for g GPUs per server, T0 = 2(p−1)n/(gp). 1 ℓ (ℓ1 ) < 2− p−1
1 ℓ (ℓ1 ) ≥ 2− p−1
T0
No straggler
+ O p12 1 + ℓ−1 ℓp
Single straggler, 1 GPU/server in DP group (Thm. 1)
T0
ℓ + 2ℓp + O p12 2
T0
P ℓi −1 i
ℓi
+ O p12 T0 2 g(ℓ−1) 1 + ℓ p + O gp2 T0
m stragglers, 1 GPU/server in DP group (Thm. 2)
1+
Single straggler, g GPUs/server in DP group (Thm. 3)
p
T0
ℓ1 + 2ℓ1p + O p12 T0 2 ℓ + 2ℓp + O p12 2
T0
Notes. (1) For m stragglers, the two-regime column header indicates the lower bound expression only, not the exact transition point; the precise transition depends on the heterogeneous ℓ1 , . . . , ℓm (see Appendix B.2). (2) For the single-straggler and multi-GPU/server settings, tighter bounds exist; we present these simplified forms for consistency across settings (see Appendix B.1, Theorem 6 and Appendix B.3, Theorem 13). For a complete summary of all theoretical results, see Appendix A.
Server 1
Server 2
Server 3
Server 4 DP group 1
DP group 2
DP group 3
DP group 4 TP group 1
TP group 2
TP group 3
TP group 4
Figure 1: 2D parallelism communication topology example for large-model training (4 servers × 4 GPUs). Each data-parallel (DP) group consists of one GPU per server; gradient synchronization is performed via AllReduce over the inter-node RDMA fabric (IB/RoCE). Each tensor-parallel (TP) group consists of the GPUs within a single server, executing collectives over intra-node NVLink.
pipeline can absorb this loss with an overhead of only O(1/p) relative to the fault-free optimum. This insight extends to the more common production scenario of multiple stragglers, as long as the total bandwidth lost across all degraded nodes remains sufficiently smaller than the healthy GPUs’ aggregate link bandwidth. In summary, we make three contributions: 1. Information-theoretic lower bound. We prove that the unavoidable overhead of bandwidth degradation is surprisingly small (Table 1): when the straggler retains at least half of its original bandwidth, the overhead over the fault-free optimum is only O(1/p)—less than 1% at p=128 GPUs. We extend the bound to more general multiple-straggler and multi-GPU-per-server scenarios (Section 3). 2. Algorithm achieving the lower bound. We design O PT CC, a four-stage pipelined AllReduce that achieves this lower bound with zero idle bubbles in the steady-state pipeline body. The schedule is a closed-form construction requiring no optimization solver, supporting online generation when a failure is detected (Section 4). 3. SimAI-based evaluation. On the SimAI1 network simulator [31], OptCC completes AllReduce within 2–6% of the fault-free NCCL ring under practical network failures, whereas existing approaches incur up to 57% overhead (Section 5). Code is available at https://anonymous. 4open.science/r/OPTCC_NeurIPS2026-1E87/.
2
Network Failure
Recovery
Congestion!
150Gb/s Shared NIC Pool 600 Gb/s in total 200Gb/s
Straggler
150Gb/s
200Gb/s
150Gb/s
200Gb/s
150Gb/s
150Gb/s
150Gb/s
200Gb/s
200Gb/s 200Gb/s
Figure 2: Network failure recovery: remaining NICs on Figure 3: The straggler lies on the critical this server form a shared NIC pool, turning the affected path of standard Ring AllReduce, bringing server into a straggler (e.g., losing 2 of 8 NICs gives congestion to the entire collective. slowdown factor ℓ = 4/3 ≈ 1.33).
2
Background and Motivation
AllReduce topology under hybrid parallelism. Modern LLM training combines multiple parallelism strategies [14, 8, 13, 34]—including tensor parallelism (TP), data parallelism (DP), and pipeline parallelism—of which TP and DP require AllReduce (Figure 1). Because TP demands an AllReduce at every layer during both the forward and backward passes, it is confined to GPUs within a single server to exploit the high-bandwidth NVLink fabric; DP AllReduce, which synchronizes gradients once per iteration, runs across servers over the inter-node RDMA network (IB/RoCE). Each DP group typically occupies only one (or a small number of) GPU and NIC per server, making DP AllReduce the collective directly exposed to inter-node network failures. Network failure recovery creates stragglers. When a network failure (e.g., NIC, cable, or port fault) occurs during training, there are two strategies to resume without interrupting training. The first is to exclude the failed server and continue with the remaining healthy servers [25, 33, 3, 26]; this preserves homogeneous bandwidth but wastes the excluded server’s GPUs. The second is to keep the failed server by rerouting its traffic through surviving network links (i.e., NICs) on the same server [30, 1, 10]. As illustrated in Figure 2, the PXN (PCI × NVLink) mechanism in NCCL [17] allows any GPU to access any NIC on the same server via NVLink, effectively pooling all local NICs into a shared bandwidth resource. This keeps all GPUs active, but leaves the GPUs on the affected server as stragglers with degraded network bandwidth. Ring AllReduce bottleneck under asymmetric bandwidth. When network bandwidth is the bottleneck—as is the case for large gradient buffers in data-parallel training2 —NCCL selects the Ring AllReduce algorithm [18, 15]. Ring AllReduce arranges all GPUs in a logical ring and performs a reduce-scatter followed by an allgather, with each GPU sending and receiving approximately twice the message size in total. This is information-theoretically optimal when all links have equal bandwidth [18]. However, when one server operates at reduced bandwidth, requiring every GPU— including the straggler—to send the same volume of data creates congestion at the straggler’s degraded link (Figure 3). The straggler becomes the bottleneck of the entire ring, and all healthy GPUs are throttled to its pace. Existing liveness-oriented systems do not address this: after failover, they resume the standard Ring AllReduce without reducing the straggler’s data obligation or restructuring the schedule. R2 CCL’s AllReduce optimization [30], the most sophisticated among these, still incurs up to 57% increase in AllReduce runtime when 50% of the bandwidth is lost on a single straggler. Generalpurpose schedule synthesis tools [24, 2, 29, 23] can in principle handle heterogeneous topologies, but their solver-based approach requires minutes to hours of computation even at moderate scale, making them unsuitable for online re-scheduling when a network failure occurs during training. Problem settings of AllReduce topology. The topology of the DP AllReduce depends on the parallelism configuration and the number of concurrent failures; we study three settings that cover the practical spectrum: 1 SimAI is a large-scale, production-level network simulator that models GPU clusters and communication libraries to evaluate distributed training and collective communication under realistic network conditions. 2We focus on the bandwidth term because (i) for the large gradient buffers in LLM training (hundreds of MB to several GB [5]), bandwidth dominates AllReduce cost—NCCL itself selects the bandwidth-optimal Ring algorithm above ∼256 KiB [15]—and (ii) per-hop network latency varies widely across GPU pairs in a data center and is difficult to model analytically [20].
3
• Single straggler, one GPU per server in DP group. In large-scale training of frontier models, all GPUs within a server are assigned to TP (and possibly PP), so each server contributes exactly one GPU to each DP AllReduce group. A single network failure degrades one server, creating one straggler in the AllReduce ring. • Multiple stragglers, one GPU per server in DP group. In large clusters with hundreds of servers, multiple servers may experience network failures and fall back to degraded networking [9]. This is the most common production scenario; it extends the above setting to handle heterogeneous slowdown factors across multiple degraded servers. • Single straggler, multiple GPUs per server in DP group. For medium-scale training or finetuning, TP may use only a subset of GPUs within a server (e.g., 2 or 4), leaving multiple GPUs per server in the same DP group. These GPUs share the server’s inter-node NIC bandwidth, so a network failure degrades the effective bandwidth for all of them simultaneously.
3
Theoretical Lower Bounds
We establish information-theoretic lower bounds on AllReduce time under degraded-NIC conditions, following the general methodology of communication lower bounds in distributed learning [7]. The results stated below correspond to the lower-bound entries in Table 1; all proofs are deferred to Appendix B. Problem setting. Let T (A) denote the end-to-end completion time of an AllReduce algorithm A on p ≥ 3 GPUs with n-element vectors, counted in the bandwidth-bound model: each healthy NIC transmits one element per time unit, a NIC with slowdown ℓ > 1 transmits one element in ℓ time units, and per-message latency, kernel launch, and cold-start overheads are excluded [18]. An algorithm is correct if (i) every transfer respects data dependencies—a GPU may transmit only Pp data it already holds—and (ii) upon termination every GPU holds the element-wise sum s = i=1 xi . An algorithm is bandwidth-optimal if it achieves min T over all correct AllReduce algorithms on the same bandwidth profile. In the fault-free homogeneous case with g GPUs per server, this minimum is known to equal3 2(p − 1) T0 = n, gp which reduces to 2n(p − 1)/p when g = 1, and is attained by Ring AllReduce [18]. We measure the overhead of all algorithms under degraded bandwidth relative to this T0 . One straggler. Exactly one GPU has slowdown factor ℓ, and the remaining p − 1 are healthy. Theorem 1 (Lower bound with one straggler). Any correct AllReduce algorithm A satisfies 2ℓ(p−1) ℓ−1 1 ℓ ℓ 1 T (A) ≥ max , ℓ · n = max 1+ +O 2 , + +O 2 · T0 . ℓ(p−1) + 1 ℓp p 2 2p p
Multiple stragglers. More generally, m GPUs are stragglers with heterogeneous slowdown factors ℓ1 ≥ ℓ2 ≥ · · · ≥ ℓm > 1; the remaining p − m are healthy (p is sufficiently larger than m). Theorem 2 (Lower bound with m stragglers). Any correct AllReduce algorithm A satisfies ( T (A) ≥ max
2(p−1) P , ℓ1 p−m+ i ℓ1i
)
( · n = max 1+
P ℓi −1 i
ℓi
p
1 +O 2 p
) ℓ1 ℓ1 1 , · T0 . + +O 2 2 2p p
Setting m = 1 recovers Theorem 1. Multiple GPUs per server. Now we consider each server holding g GPUs that share the same NIC bandwidth. Inside each server, the g GPUs are connected via NVLink whose bandwidth is at least (g−1) times the NIC bandwidth.4 The straggler server’s inter-server NIC is degraded by factor ℓ, while all NVLink connections remain healthy. 3When g > 1, each server runs g concurrent ring channels, each carrying n/g elements, so that all g NICs per server are fully utilized—this is the standard approach used by NCCL [15]. 4 On the NVIDIA DGX A100 [16], each GPU has 4800 Gbps aggregate NVLink bandwidth (2400 Gbps unidirectional) versus 200 Gbps inter-node NIC bandwidth (one HDR InfiniBand NIC per GPU), so this assumption holds by a wide margin.
4
Straggler
Straggler
Stage1: Reduce-scatter between healthy GPUs
Straggler
Stage 2: Upload to the straggler
Stage 3: Download from the straggler
Straggler
Stage 4: Allgather between healthy GPUs
Figure 4: 4-stage decomposition of O PT CC. Line thickness indicates bandwidth; arrows denote active links in each stage.
Theorem 3 (Lower bound with multi-GPU servers). Under the NVLink-rich assumption above, any correct AllReduce algorithm A satisfies T (A) ≥ max
ℓ 2ℓ(p − g) , g (ℓ(p − g) + g) g
2 2 g(ℓ − 1) g ℓ ℓg g · n = max 1 + +O 2 , + +O 2 · T0 . ℓp p 2 2p p
Setting g = 1 recovers Theorem 1. Takeaway. In all three settings, the lower bound has the form T ≥ max{1 + O(1/p), ℓ/2 + O(1/p)} · T0 . When the worst straggler loses more than half of its bandwidth, it bottlenecks the entire AllReduce and any algorithm requires at least (ℓ/2) T0 time. When no straggler loses more than half of its bandwidth (ℓ < 2), the lower bound approaches T0 as p grows, meaning the overhead from NIC degradation vanishes in large clusters.
4
Algorithm Design
Our algorithm partitions each GPU’s n-element vector into many small segments and, for every segment, decomposes the AllReduce into four logical stages: (1) reduce-scatter among the p−1 healthy GPUs, (2) upload partial sums to the straggler, (3) download global sums from the straggler, and (4) allgather among the healthy GPUs. Stages 2 and 3 use only the slow straggler link while Stages 1 and 4 use fast links between healthy GPUs—these are disjoint hardware resources. We exploit this by pipelining segments so that the slow Stages 2/3 of one segment run in parallel with Stages 1/4 of other segments, effectively hiding the straggler overhead. We present the algorithm for the single-straggler, one-GPU-per-server setting in this section; the algorithm designs for multiple stragglers (Appendix D) and multi-GPU-per-server (Appendix E) are deferred to the appendix. 4.1
Four-Stage Decomposition
We partition the n input elements into k segments, each containing p − 1 sections of size s = n/(k(p − 1)) elements. For each segment, the AllReduce proceeds through four stages (illustrated in Figure 4). We define a flow as a point-to-point transfer of one section between two GPUs, and enforce that each NIC receives at most one flow at a time; overlapping incoming flows would contend for bandwidth and cause unpredictable delays. Stage 1: Reduce-Scatter among healthy servers. The p − 1 healthy servers are arranged in a directed ring. Each section is reduce-scattered along this ring in exactly p − 2 hops: at each hop, a server receives a partial-sum flow from its predecessor, adds its own contribution, and forwards the result. After p − 2 hops, one designated healthy server holds the partial sum of all p − 1 healthy servers’ contributions for that section. Since all p − 1 servers send in parallel (each to its ring successor), and each hop transmits one section of s elements on a fast link, the time for Stage 1 is (p − 2) · s. Stage 2: Upload to the straggler. After Stage 1, the partial sum of a section resides on a healthy server but does not yet include the straggler’s data. In Stage 2, a healthy server sends the partial sum to the straggler (s elements on the slow link, taking ℓ · s time). 5
Stage 3: Download from the straggler. The straggler adds its local value to the received partial sum, producing the global sum, and sends it back to a healthy server (s elements, again ℓ · s time). Each segment has p − 1 sections, and the flow scheduling constraint forces the straggler to process them one at a time: no two flows may overlap at the straggler’s NIC. The total time for Stages 2 and 3 for one segment is therefore (p − 1) · ℓ · s each. Because the straggler can receive and send in full-duplex, Stage 2 and Stage 3 for different sections can be pipelined on the straggler’s link. Stage 4: Allgather among healthy servers. Once a section’s global sum returns to a healthy server via Stage 3, it is broadcast to all other healthy servers through an allgather along the same ring. This is structurally symmetric to Stage 1: p − 2 hops, each forwarding s elements, costing (p − 2) · s. Stage ordering and correctness. For a single section, the four stages must respect data dependencies: Stage 1 produces the partial sum consumed by Stage 2, Stage 2 feeds Stage 3, and Stage 3 produces the global sum consumed by Stage 4. Two orderings satisfy these constraints: (1) S1 → S2 → S3 → S4, and (2) S3 → S1 → S4 → S2. In ordering (1), the healthy servers first reduce-scatter among themselves, then upload the partial sum to the straggler, which completes the global sum and downloads it for allgather. In ordering (2), the straggler uploads its local value first; the healthy servers incorporate it during their reduce-scatter (which now produces the global sum directly), perform the allgather, and finally send the result back to the straggler. Both orderings compute a correct AllReduce. 4.2
Schedule Construction
A key observation is that Stages 2 and 3 communicate exclusively over the slow straggler link, whereas Stages 1 and 4 communicate exclusively over the fast ring links among healthy servers. Although individual GPUs may serve as endpoints in both types of transfer, the links involved are disjoint. This separation of resources makes it possible to overlap Stages 2/3 with Stages 1/4: if we execute them concurrently, each parallel body takes time proportional to max{ℓ, 2} · s, which aligns precisely with the lower bound established in Theorem 1. Four patterns. Exploiting the two valid stage orderings identified in Section 4.1, we design four patterns—distinct flow schedules that can be interleaved without violating the non-overlap constraint. We illustrate the construction for p = 5 and ℓ = 2 (Figure 5); the analysis generalizes to arbitrary p and ℓ. In this setting, GPU 0 is the straggler with 50% NIC throughput; GPUs 1–4 are healthy. Each Stage 2 or Stage 3 flow occupies ℓ s = 2s time units (two grid cells in the figure), while each Stage 1 or Stage 4 flow occupies s time units (one grid cell). With p − 1 = 4 healthy servers, Stage 1 (reducescatter among 4 GPUs) and Stage 4 (allgather among 4 GPUs) each consist of (p − 2)(p − 1) = 12 flows; Stage 2 and Stage 3 each consist of p − 1 = 4 flows. We reserve 2(p−1) = 8 time slots per stage (one grid cell equals the time for a healthy NIC to send or receive one flow; a straggler flow occupies two cells), for a total of 4 × 2(p−1) = 32 time slots per pattern across all four stages. The four patterns are: • Pattern A (Figure 5a): S1 → S2 → S3 → S4. • Pattern B (Figure 5b): S3 → S1 → S4 → S2. • Pattern C (Figure 5c): S1 → S2 → S3 → S4 (same stage ordering as A, but flows in Stages 1 and 3 are shifted by an offset). • Pattern D (Figure 5d): S3 → S1 → S4 → S2 (same ordering as B, with the same offset). Each pattern respects the data dependencies of its stage ordering, and the four patterns are staggered so that all four stages interleave across time—no NIC ever receives or sends two simultaneous flows. Pipelining four patterns. We now overlay the four patterns to form a complete schedule (Figure 6). We assume k is a multiple of 4, so that each pattern processes exactly k/4 segments. Superimposing the four patterns’ flow schedules yields a composite timeline in which each parallel body contains one instance of each stage from each pattern. 6
Stage 1
Stage 2
Stage 3 1
GPU 0
GPU 1 GPU 2 GPU 3 GPU 4
2 3 4
2 3 4 1
2 3
4 1
2
Stage 4
3
0
GPU 0
2 3 4
Flow sent from GPU 0 to GPU 1
0 1
Stage 3
4
0
2 3 4 1
0
4 1
1
2
1
Stage 2
GPU 1 2 GPU 2 3 GPU 3 4 GPU 4
1 2 3 4 1
2 3
4 1
2
Stage 4
3
GPU 0
2 3 4
0 0
1
2 3 4 1
0
3 4 1
Stage 3
4
0
2
2 3
4 1
2 3 4
Stage 2 2
3 4 1
1
2 3
4 1
0 0 0
1
0
(b) Pattern B (S3→S1→S4→S2)
Stage 3
GPU 0
Stage 4
4 2 3 4
(a) Pattern A (S1→S2→S3→S4) Stage 1
Stage 1
3
GPU 1 GPU 2 GPU 3 GPU 4
2 3
4 1
1
2
Stage 1
3
1
2 3 4
(c) Pattern C (S1→S2→S3→S4)
Stage 4
Stage 2
4
GPU 1 GPU 2 GPU 3 GPU 4
2 3
2 3 4 1
2 3
4 1
2 3 4
2 3 4 1
1
4 1
2 3
0 0 0
1
0
(d) Pattern D (S3→S1→S4→S2)
Figure 5: Flow schedules for the four patterns (p=5, ℓ=2). Rows are GPUs 0–4 (GPU 0 is the straggler, losing 50% bandwidth); columns are time slots. Each colored cell represents a flow; its label indicates the destination GPU. The four patterns occupy disjoint communication slots so that no NIC receives two flows simultaneously. Parallel body 1 Stage 1 Stage 3
Straggler GPU 0
1
2
Parallel body 2 Stage 2 Stage 1 Stage 1 Stage 3
3
4
Healthy GPU 1
2
Healthy GPU 2
3
3
Healthy GPU 3
4
4
4
1
1
Healthy GPU 4
2
1
2
Parallel body 3 Stage 3 Stage 4 Stage 2 Stage 1
3
2
2
3
3
3
3
3
4
4
4
4
4
4
1
1
1
1
1
0
0
2
4
2
2 0
1
2
3
2
2
2
3
3
3
3
3
3
4
4
4
4
4
4
1
1
1
1
1
1
0
2
4
2 0
0
Parallel body 5
Parallel body 4 Stage 4 Stage 2 Stage 3 Stage 4
2 0
1
2
Stage 4 Stage 2
3
2
2
2
3
3
3
3
3
3
4
4
4
4
4
4
1
1
1
1
0 1
1
0
0
2
4
2
2 0
2
2
2
3
3
3
3
4
4
4
1
1
0 1
1
0
0
2
2 0
3 0 1
Figure 6: Combining the four patterns from Figure 5 into a complete pipeline. p=5 GPUs, ℓ=2 (straggler lost 50% bandwidth), k=4 segments. Each parallel body contains all four stages (except the head and tail). Flows enclosed in a single rounded box share the same sender–receiver pair and have no data dependency, thus can be packed into one network transfer. When ℓ=2, the body has no idle bubbles.
Filling straggler-slot bubbles (ℓ < 2). When ℓ < 2, each Stage 2/3 flow (ℓ s) is shorter than the combined Stage 1/4 flows (2s), leaving a bubble of (2 − ℓ) s time in every straggler slot. Across one parallel body the straggler has p−1 such bubbles, and each healthy GPU also has one (in its Stage 2/3 slot). We reclaim these idle intervals by running a point-to-point allreduce between the healthy GPUs and the straggler (Figure 7): in parallel body b, each healthy GPU uses its bubble to send a partial sum to the straggler ( light gray cells); the straggler reduces these contributions during its own bubbles and, in body b+1, broadcasts the result back to the healthy GPUs ( dark gray cells). Because both directions reuse time that would otherwise be idle, a fraction of the data completes its allreduce at zero additional cost, bringing the effective runtime closer to the lower bound. 4.3
Time Analysis
Let s = n/(k(p − 1)) denote the section size. The composite schedule is formed by concatenating k/4 copies of the four-pattern group from Figure 6 (for ℓ ≥ 2) or Figure 7 (for ℓ < 2) end-to-end, where the last parallel body of one group overlaps with the first of the next. This produces k + 1 parallel bodies in total: k − 1 steady-state bodies that each contain one part from each of the four patterns, plus one startup body at the head and one drain body at the tail. The body duration depends on which resource—the healthy ring (Stages 1/4) or the straggler link (Stages 2/3)—is the bottleneck. Case ℓ ≥ 2 (straggler-bottlenecked). When ℓ ≥ 2, Stages 2/3 are the critical path. Each parallel body takes ℓ (p−1) s time. Summing over k + 1 bodies (including startup/drain), substituting s = n/(k(p − 1)), and recalling the fault-free baseline T0 = 2n(p−1)/p: k + 1 k→∞ ℓ ℓ 1 T = ℓn −−−−→ ℓ n = + +O 2 T0 , (1) k 2 2p p matching the lower bound of Theorem 1 (Table 1). When ℓ = 2, Stages 2/3 fit exactly within Stages 1/4 and every slot is occupied with zero idle time. When ℓ > 2, the straggler becomes the 7
Parallel body 1 Straggler GPU 0
1
2
Parallel body 2
3
4
Healthy GPU 1
2
Healthy GPU 2
3
3
Healthy GPU 3
4
4
4
1
1
Healthy GPU 4
0
0
2
1 2
0
3 0 1
1
2
2
0
0 2
Parallel body 3
3
3
2
2
3
3
3
3
4
4
4
4
4
4
0 1
1
1
1
0
2 0
4 2
4 2
0 3
3 0
1
0 1
1
1
2
2
0
0 2
3
2
2
3
3
3
3
4
4
4
4
4
4
0 1
1
1
1
0
Parallel body 5
Parallel body 4
3 2 0
4 2
4 2
0 3
3 0
1
0 1
1
1
2
2
3
0
0 2
3
2
2
3
3
3
3
4
4
4
4
4
4
0 1
1
1
1
0
2 0
4 2
4 2
0 3
1
0 1
2
2
3 0
1 0
3 2
3
3
4
4
4
1
1
0
4 2
0
3 0 1
Figure 7: Filling all bubbles with P2P allreduce between healthy GPUs and the straggler when ℓ < 2. p=5 GPUs, ℓ=1.5 (straggler lost 33% bandwidth), k=4 segments. Stage 2/3 flows (width 1.5) are shorter than Stage 1/4 flows (width 2), creating bubbles. Filling bubbles with: light gray (in parallel body i): healthy GPUs send partial sums to the straggler; dark gray (in parallel body i+1): straggler broadcasts reduced results back to the healthy GPUs. bottleneck, yet the schedule remains bandwidth-optimal without requiring p → ∞, confirming its optimality even for small clusters. Case ℓ < 2 (ring-bottlenecked, with bubble filling). When ℓ < 2, the bubble-filling technique of Section 4.2 reduces the section size from s to a smaller s′ , and uses up all the straggler’s bandwidth. The derivation of s′ and the resulting total time are given in Appendix C: k + ℓ − 1 k→∞ 2(p−1) ℓ n 2(ℓ−1) 1 2(p−1) ℓ n −−−−→ = 1+ +O 2 T0 . (2) T = (p−2)ℓ + 2 k (p−2)ℓ + 2 ℓp p At ℓ = 1 this reduces to T0 , the non-degraded optimum; at ℓ = 2 it gives 2n, approaching the lower bound of Theorem 1. For general ℓ ∈ [1, 2), the relative overhead satisfies pℓ/[(p−2)ℓ + 2] ≤ 1 + 1/(p−1). In fact, our algorithm always achieves bandwidth optimal without requiring p → ∞; see Appendix C for details. Schedule generation complexity. The complete flow schedule is determined by the closed-form rules of Sections 4.1–4.2 in O(pk) time, with no iterative optimization. For p=1024 GPUs on SimAI, the schedule is generated in under 1 ms on a single CPU core, making OptCC suitable for online deployment upon failure detection. 4.4
Extensions to Multiple Stragglers and Multi-GPU Servers
Multiple stragglers, one GPU per server in DP group (Appendix D). The key difference is that Stages 2/3 now serve m stragglers instead of one; the bottleneck is the slowest straggler (ℓ1 = maxi ℓi ), and flows to/from each straggler are assigned to disjoint time slots within each body. Single straggler, multiple GPUs per server in DP group (Appendix E). We treat each server’s g GPUs as a single logical GPU: before every outgoing NIC flow the g GPUs perform a local reduce over NVLink, and after every incoming flow the receiver broadcasts to the other g−1 GPUs. Because NVLink bandwidth is typically (g−1)× the NIC bandwidth, these intra-server transfers can be fully overlapped with inter-server NIC transfers of adjacent pipeline stages, so the NIC remains the sole bottleneck and intra-server communication adds no extra time to the critical path.
5
Evaluation
We evaluate OptCC on SimAI [31] (an NS-3-based network simulator that models the actual onthe-wire traffic between GPUs), using clusters of A100 servers, each equipped with 8 GPUs and 8 ConnectX-6 200 Gbps HDR InfiniBand NICs. We compare against three baselines: NCCLNoFailure , NCCL ring on a fully healthy topology (a fault-free reference); ICCL [1], NCCL ring on the NICbandwidth-degraded topology; and R2 CCL [30], a state-of-the-art NIC fault-tolerant AllReduce. We also plot the lower bounds from Section 3 as theoretical runtime guarantees.5 In the OptCC implementation, flow dependencies are enforced via per-GPU state tracking for intra-GPU ordering and necessary P2P synchronization messages for inter-GPU ordering. We simulate at productionrealistic GPU counts [12, 14] and message sizes [19, 28, 11]. SimAI is deterministic—the same 5 SimAI profiling shows that the NIC bandwidth term accounts for ∼86% of NCCL NoFailure ’s completion time, with the remaining ∼14% from fixed overhead (cold start, per-flow network latency). We plot the lower bound as its multiplier applied to the bandwidth fraction, plus the fixed overhead.
8
AllReduce time (ms)
configuration always produces the same result—so each data point is a single run with no error bars. Larger-message microbenchmarks are in Appendix F. NCCLNoFailure
OptCC (ours)
=1.14, N=1GiB
=1.14, p=64
250
200 150 100 50
110 100 100
GPU\# p
200
300
200
100
1500
Message size N (MiB)
2000
p=64, N=1GiB 400
400
150
1000
Lower bound =2, p=64
200
500
(a)
R2CCL
ICCL =2, N=1GiB
50
(b)
100 150 200 250
0
GPU\# p
200
500
1000
1500
Message size N (MiB)
(c)
2000
100
1.5
2.0
2.5
Slowdown factor
(d)
3.0
(e)
AllReduce time (ms)
Figure 8: Single straggler; DP group involves 1 GPU per server. (a,b) the straggler loses 1 out of 8 NICs (ℓ=1.14); (c,d) loses 4 out of 8 NICs (ℓ=2); (e) varying ℓ. 140
1=1.33, 2=1.14, N=1GiB
120 100 100
GPU\# p
200
1=1.33, 2=1.14, p=64
250
200
200
100
150
0
1000
1500
2000
1 = 2, p=64, N=1GiB
1=2, 2=1.33, p=64
400
400
300
200
100
500
Message size N (MiB)
(a)
1=2, 2=1.33, N=1GiB
50
(b)
100 150 200 250
0
GPU\# p
200
500
1000
1500
Message size N (MiB)
(c)
2000
100
1.5
2.0
2.5
Slowdown factor
(d)
3.0
(e)
AllReduce time (ms)
Figure 9: Multi-straggler (m=2); DP group involves 1 GPU per server. (a,b) two stragglers lose 2 and 1 out of 8 NICs respectively (ℓ1 =1.33, ℓ2 =1.14); (c,d) lose 4 and 2 out of 8 NICs (ℓ1 =2, ℓ2 =1.33); (e) ℓ1 =ℓ2 , varying ℓ. =1.14, N=8GiB 200
=2, N=8GiB
=1.14, p=128 400
300
190
300
200
180 170
400
100
200
400
GPU\# p
600
(a)
200
5
10
Message size N (GiB)
(b)
15
200
400
GPU\# p
(c)
600
800
800 600 400 200 0
p=256, N=8GiB
=2, p=128 600 400 200 5
10
Message size N (GiB)
(d)
15
1.5
2.0
2.5
Slowdown factor
3.0
(e)
Figure 10: Multi-GPU/server; DP group involves g=4 GPUs per server. (a,b) the straggler loses 1 out of 8 NICs (ℓ=1.14); (c,d) loses 4 out of 8 NICs (ℓ=2); (e) varying ℓ. OptCC runtime is close to NCCLNoFailure in both small and large clusters. OptCC stays within 6% of NCCLNoFailure across p ∈ [16, 256]. At small p (e.g., p=16) the gap is dominated by the stragglerinduced lower bound of Theorem 1 — fundamental, not an artifact of OptCC. Toward p=256 we observe a mild upward trend; we honestly acknowledge this as a limitation of our construction, since larger clusters require more point-to-point synchronization between healthy and straggler GPUs, whose overhead grows with p. Even so, at p=256 OptCC stays within 6% of NCCLNoFailure and beats R2 CCL/ICCL by 29%/58%. Note that ICCL’s overhead exceeds the slowdown factor ℓ itself: because ICCL does not restructure the ring schedule, the straggler’s degraded NIC must carry the same volume of traffic as a healthy NIC, causing network congestion at the straggler that amplifies the bandwidth penalty beyond the raw ℓ× slowdown. OptCC approaches NCCLNoFailure across all AllReduce message sizes. As long as the worst NIC retains at least 50% of its bandwidth, OptCC matches the NCCLNoFailure rate to within 2% (single straggler), 8.5% (multi-straggler m=2), and 4% (multi-GPU/server), in each case beating R2 CCL by 27% and ICCL by 55% at the same N . The constant-factor gap translates linearly into wall-clock savings as gradient buffers grow. OptCC approaches NCCLNoFailure whenever the worst NIC loses at most 50% of its bandwidth. For ℓ ≤ 2 the OptCC curve sits flat against NCCLNoFailure : bubble filling (Section 4.2) hides the entire straggler overhead inside slack on the healthy ring. Once ℓ crosses 2 the straggler’s NIC becomes the binding bottleneck and OptCC grows linearly in ℓ at exactly the rate of Theorem 1’s ℓ n branch; even here OptCC stays strictly faster than ICCL and R2 CCL, both of which pay a slowdown penalty from ℓ=1 onward.
6
Conclusion
Network failures are an operational reality in large GPU clusters, yet their impact on collective communication has lacked a principled theoretical treatment. This paper closes that gap for AllReduce: 9
we derive tight information-theoretic lower bounds showing that, when the straggler retains at least half of its bandwidth, the unavoidable overhead is only O(1/p)—fundamentally negligible in large clusters—and we design OptCC, an algorithm that achieves these bounds. The key insight is that healthy GPUs carry enough spare bandwidth to absorb a straggler’s deficit through careful pipeline interleaving, so that near-optimal performance is attainable without any hardware redundancy, job restart, or offline pre-computation. SimAI-based evaluation confirms 2–6% overhead relative to the fault-free NCCL ring, compared with up to 57% for existing schemes. Extending the bounds to latency-sensitive settings and dynamic bandwidth fluctuations is left to future work.
References [1] Ziteng Chen, Xiaohe Hu, Menghao Zhang, Yanmin Jia, Yan Zhang, Mingjun Zhang, Da Liu, Fangzheng Jiao, Jun Chen, He Liu, Aohan Zeng, Shuaixing Duan, Ruya Gu, Yang Jing, Bowen Han, Jiahao Cao, Wei Chen, Wenqi Xie, Jinlong Hou, Yuan Cheng, Bohua Xu, Mingwei Xu, and Chunming Hu. An efficient, reliable and observable collective communication library in large-scale gpu training clusters. arXiv preprint arXiv:2510.00991, 2025. [2] Meghan Cowan, Saeed Maleki, Madanlal Musuvathi, Olli Saarikivi, and Yifan Xiong. GC3: An optimizing compiler for GPU collective communication. arXiv preprint arXiv:2201.11840, 2022. [3] Arjun Devraj, Eric Ding, Abhishek Vijaya Kumar, Robert Kleinberg, and Rachee Singh. Efficient AllReduce with stragglers. arXiv preprint arXiv:2505.23523, 2025. [4] Michael Diskin, Alexey Bukhtiyarov, Max Ryabinin, Lucile Saulnier, quentin lhoest, Anton Sinitsin, Dmitry Popov, Dmitry V. Pyrkin, Maxim Kashirin, Alexander Borzunov, Albert Villanova del Moral, Denis Mazur, Ilia Kobelev, Yacine Jernite, Thomas Wolf, and Gennady Pekhimenko. Distributed deep learning in open collaborations. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 7879–7897. Curran Associates, Inc., 2021. URL https://proceedings.neurips.cc/paper_files/paper/2021/file/ 41a60377ba920919939d83326ebee5a1-Paper.pdf. [5] Andrew Gibiansky. Bringing HPC techniques to deep learning. https://andrew.gibiansky. com/blog/machine-learning/baidu-allreduce/, 2017. [6] Haryadi S. Gunawi, Riza O. Suminto, Russell Sears, Casey Golliher, Swaminathan Sundararaman, Xing Lin, Tim Emami, Weiguang Sheng, Nematollah Bidokhti, Caitie McCaffrey, Deepthi Srinivasan, Biswaranjan Panda, Andrew Baptist, Gary Grider, Parks M. Fields, Kevin Harms, Robert B. Ross, Andree Jacobson, Robert Ricci, Kirk Webb, Peter Alvaro, H. Birali Runesha, Mingzhe Hao, and Huaicheng Li. Fail-slow at scale: Evidence of hardware performance faults in large production systems. ACM Trans. Storage, 14(3), October 2018. ISSN 1553-3077. doi: 10.1145/3242086. URL https://doi.org/10.1145/3242086. [7] Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 18955–18969. Curran Associates, Inc., 2022. URL https://proceedings.neurips.cc/paper_files/paper/2022/file/ 77f2d0c271e508278ea13e24cd8773d5-Paper-Conference.pdf. [8] Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Chen, HyoukJoong Lee, Jiquan Ngiam, Quoc V Le, Yonghui Wu, and Zhifeng Chen. GPipe: Efficient training of giant neural networks using pipeline parallelism. In Advances in Neural Information Processing Systems, volume 32, 2019. [9] Apostolos Kokolis, Michael Kuchnik, John Hoffman, Adithya Kumar, Parth Malani, Faye Ma, Zachary DeVito, Shubho Sengupta, Kalyan Saladi, and Carole-Jean Wu. Revisiting reliability in large-scale machine learning research clusters. In 2025 IEEE International Symposium on High Performance Computer Architecture (HPCA), pages 1259–1274, 2025. doi: 10.1109/HPCA61900.2025.00096. 10
[10] Shengkai Lin, Kairui Zhou, Hongtao Zhang, Yibo Wu, Yi Pan, Yihan Yang, Qinwei Yang, Wei Zhang, Arvind Krishnamurthy, and Shizhen Zhao. SHIFT: Exploring the boundary of RDMA network fault tolerance. arXiv preprint arXiv:2512.11094, 2025. [11] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In International Conference on Learning Representations (ICLR), 2018. [12] Llama Team, AI @ Meta. The Llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024. [13] Deepak Narayanan, Aaron Harlap, Amar Phanishayee, Vivek Seshadri, Nikhil R Devanur, Gregory R Ganger, Phillip B Gibbons, and Matei Zaharia. PipeDream: Generalized pipeline parallelism for DNN training. In Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP), 2019. [14] Deepak Narayanan, Mohammad Shoeybi, Jared Casper, Patrick LeGresley, Mostofa Patwary, Vijay Anand Korthikanti, Dmitri Vainbrand, Prethvi Kashinkunti, Julie Bernauer, Bryan Catanzaro, Amar Phanishayee, and Matei Zaharia. Efficient large-scale language model training on GPU clusters using Megatron-LM. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2021. [15] NVIDIA. NCCL tests. https://github.com/NVIDIA/nccl-tests, 2024. [16] NVIDIA Corporation. NVIDIA DGX A100 system architecture. https://images.nvidia. com/aem-dam/Solutions/Data-Center/nvidia-dgx-a100-datasheet.pdf, 2020. Accessed: 2026-05-03. [17] NVIDIA Corporation. Doubling all2all performance with NVIDIA collective communication library 2.12. https://developer.nvidia.com/blog/doubling-all2all-performancewith-nvidia-collective-communication-library-2-12/, 2022. Accessed: 2026-0331. [18] Pitch Patarasuk and Xin Yuan. Bandwidth optimal all-reduce algorithms for clusters of workstations. Journal of Parallel and Distributed Computing, 69(2):117–124, 2009. [19] PyTorch Contributors. PyTorch issue #118421: Increase DDP default bucket_cap_mb. https: //github.com/pytorch/pytorch/issues/118421, 2024. Accessed: 2026-05-01. [20] Kun Qian, Yongqing Xi, Jiamin Cao, Jiaqi Gao, Yichi Xu, Yu Guan, Binzhang Fu, Xuemei Shi, Fangbo Zhu, Rui Miao, Chao Wang, Peng Wang, Pengcheng Zhang, Xianlong Zeng, Eddie Ruan, Zhiping Yao, Ennan Zhai, and Dennis Cai. Alibaba HPN: A data center network for large language model training. In Proceedings of the ACM SIGCOMM 2024 Conference, ACM SIGCOMM ’24, page 691–706, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400706141. doi: 10.1145/3651890.3672265. URL https://doi.org/ 10.1145/3651890.3672265. [21] Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. Zero: memory optimizations toward training trillion parameter models. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’20. IEEE Press, 2020. ISBN 9781728199986. [22] Max Ryabinin, Eduard Gorbunov, Vsevolod Plokhotnyuk, and Gennady Pekhimenko. Moshpit SGD: Communication-efficient decentralized training on heterogeneous unreliable devices. In Advances in Neural Information Processing Systems, volume 34, 2021. [23] Amedeo Sapio, Marco Canini, Chen-Yu Ho, Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, Masoud Moshref, Dan Ports, and Peter Richtarik. SwitchML: Scaling distributed machine learning with in-network aggregation. In Proceedings of the 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2021. [24] Aashaka Shah, Vijay Chidambaram, Meghan Cowan, Saeed Maleki, Madan Musuvathi, Todd Mytkowicz, Jacob Nelson, Olli Saarikivi, and Rachee Singh. TACCL: Guiding collective algorithm synthesis using communication sketches. In Proceedings of the 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2023. 11
[25] Min Si, Pavan Balaji, Yongzhou Chen, Ching-Hsiang Chu, Adi Gangidi, Saif Hasan, Subodh Iyengar, Dan Johnson, Bingzhe Liu, Regina Ren, Deep Shah, Ashmitha Jeevaraj Shetty, Greg Steinbrecher, Yulun Wang, Bruce Wu, Xinfeng Xie, Jingyi Yang, Mingran Yang, Kenny Yu, Minlan Yu, Cen Zhao, Wes Bland, Denis Boyda, Suman Gumudavelli, Prashanth Kannan, Cristian Lumezanu, Rui Miao, Zhe Qu, Venkat Ramesh, Maxim Samoylov, Jan Seidel, Srikanth Sundaresan, Feng Tian, Qiye Tan, Shuqiang Tan, Yimeng Zhang, Shengbao Zhao, Art Zheng, James Hongyi Zhu, and James Hongyi Zeng. Collective communication for 100k+ GPUs. arXiv preprint arXiv:2510.20171, 2025. [26] Rashish Tandon, Qi Lei, Alexandros G. Dimakis, and Nikos Karampatziakis. Gradient coding: Avoiding stragglers in distributed learning. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 3368–3376, 2017. [27] Rajeev Thakur, Rolf Rabenseifner, and William Gropp. Optimization of collective communication operations in MPICH. International Journal of High Performance Computing Applications, 19(1):49–66, 2005. [28] Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization. In Advances in Neural Information Processing Systems, volume 32, 2019. [29] Guanhua Wang, Shivaram Venkataraman, Amar Phanishayee, Nikhil Devanur, Jorgen Thelin, and Ion Stoica. Blink: Fast and generic collectives for distributed ML. In Proceedings of Machine Learning and Systems (MLSys), 2020. [30] Wei Wang et al. Reliable and resilient collective communication library for LLM training and serving. arXiv preprint arXiv:2512.25059, 2025. [31] Xizheng Wang, Qingxu Li, Yichi Xu, Gang Lu, Dan Li, Li Chen, Heyang Zhou, Linkang Zheng, Sen Zhang, Yikai Zhu, Yang Liu, Pengcheng Zhang, Kun Qian, Kunling He, Jiaqi Gao, Ennan Zhai, Dennis Cai, and Binzhang Fu. SimAI: Unifying architecture design and performance tuning for Large-Scale large language model training with scalability and precision. In 22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI 25), pages 541–558, Philadelphia, PA, April 2025. USENIX Association. ISBN 9781-939133-46-5. URL https://www.usenix.org/conference/nsdi25/presentation/ wang-xizheng-simai. [32] Liangyu Zhao, Saeed Maleki, Yuanhong Wang, Zezhou Wang, Ziyue Yang, Hossein Pourreza, and Arvind Krishnamurthy. ForestColl: Throughput-Optimal collective communications on heterogeneous network fabrics. In 23rd USENIX Symposium on Networked Systems Design and Implementation (NSDI 26), pages 2067–2093, Renton, WA, May 2026. USENIX Association. ISBN 978-1-939133-54-0. URL https://www.usenix.org/conference/nsdi26/ presentation/zhao-liangyu. [33] Xiaoyang Zhao, Zhilong Zhang, and Chuan Wu. AdapCC: Making collective communication in distributed machine learning adaptive. In Proceedings of the 44th IEEE International Conference on Distributed Computing Systems (ICDCS), 2024. doi: 10.1109/ICDCS60910.2024.00012. [34] Lianmin Zheng, Zhuohan Li, Hao Zhang, Yonghao Zhuang, Zhifeng Chen, Yanping Huang, Yida Wang, Yuanzhong Xu, Danyang Zhuo, Joseph E Gonzalez, and Ion Stoica. Alpa: Automating inter- and intra-operator parallelism for distributed deep learning. In Proceedings of the 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2022.
A
Summary of Optimality Results
This appendix collects the theoretical lower bounds, algorithm time complexities, and optimality results presented throughout the paper. Table 2 summarizes the lower bounds, Table 3 summarizes the algorithm time complexities, and Table 4 summarizes the optimality results. Recall the problem setting. Let p be the total number of GPUs, each holding an n-element vector. A healthy NIC transmits one element per time unit, while a NIC with slowdown factor ℓ > 1 requires ℓ 12
Pp time units per element. Upon termination, every GPU holds the element-wise sum s = i=1 xi . Let g be the number of GPUs per server—interconnected via NVLink with g−1 times the bandwidth of a single NIC—and let m be the number of straggler servers. By the PXN mechanism (Section 2), all NICs on a given server share the same slowdown factor. We consider three scenarios: 1. single straggler, one GPU per server (m=1, g=1); 2. multiple stragglers, one GPU per server (fixed m, g=1), with slowdown factors ℓ1 ≥ ℓ2 ≥ · · · ≥ ℓm > 1; 3. single straggler, multiple GPUs per server (fixed g, m=1), where the total number of servers is q = p/g. A.1
Best Lower Bounds
The best known lower bounds for these three scenarios are given by Theorems 6, 2, and 13, respectively; with full proofs deferred to Appendix B. We summarize these results in Table 2. Table 2: Best known lower bounds on the AllReduce time T for three straggler settings. Each bound takes the of two branches; the column headers indicate the dominant branch. Here maximumP m y0 := 2(p−1) (p − m + i=1 1/ℓi . Setting Single straggler One GPU per server Theorem 6
Multiple stragglers One GPU per server Theorem 2
Single straggler Multiple GPUs per server Theorem 13
Small-ℓ regime
Large-ℓ regime
(1 < ℓ < 2) 2ℓ(p − 1) T ≥ ·n ℓ(p − 2) + 2
(ℓ ≥ 2)
(1 ≤ ℓ1 < y0 ) 2(p − 1) Pm ·n T ≥ p − m + i=1 ℓ1i (1 < ℓ < 2) 2ℓ(q − 1) n T ≥ · ℓ(q − 2) + 2 g
T ≥ ℓ·n (ℓ1 ≥ y0 ) T ≥ ℓ1 · n (ℓ ≥ 2) T ≥ ℓ·
n g
Notes. (1) For the single-straggler cases (rows 1 and 3), the two branches coincide at ℓ = 2. (2) For m stragglers, the transition point ℓ1 = y0 depends jointly on all ℓ1 ≥ ℓ2 ≥ · · · ≥ ℓm and p. (3) The bounds in rows 1 and 3 are tight: matching algorithms exist for all p (resp. q); see Table 3.
A.2
Algorithm Time Complexities
The algorithms for the three scenarios are presented in Section 4, Appendix D, and Appendix E, respectively. Their time analyses appear in Section 4.3 (together with Appendix C), Appendix D.3, and Appendix E.4, respectively. We summarize these in Table 3. A.3
Optimality Results
Combining the lower bounds from Table 2 with the algorithm times from Table 3 yields the optimality results summarized in Table 4. Here, optimal means that as k → ∞ with p, m, g, and all ℓi held constant, the algorithm achieves bandwidth optimality, confirming its optimality even for small clusters. Near-optimal means that as k → ∞ and p → ∞ with m, g, and all ℓi held constant, the algorithm approaches bandwidth optimality, confirming near-optimality in large clusters.
B
Proof of Information-theoretic Lower Bounds
In this appendix, we prove all the theoretical lower bounds introduced in Section 3: Theorem 1 (Appendix B.1), Theorem 2 (Appendix B.2), and Theorem 3 (Appendix B.3). We further derive 13
Table 3: Achieved AllReduce time T (as k → ∞) for the three algorithm variants. Each column shows the dominant regime; the transition occurs at ℓ = 2 in all cases. Setting Single straggler One GPU per server Section 4.3, Appendix C
Multiple stragglers One GPU per server Appendix D.3
Single straggler Multiple GPUs per server Appendix E.4
Small-ℓ regime
Large-ℓ regime
(1 < ℓ < 2) 2(p − 1) ℓ T → ·n (p − 2)ℓ + 2
(ℓ ≥ 2) T → ℓ·n
(1 < ℓ1 < 2) 2(p − 1) T → ·n p−m
(ℓ ≥ 2) 1 2(m − 1) T → ℓ1 + ·n p−m
(1 < ℓ < 2) ∗ n 2ℓ(q − 1) n T → 2· or · g ℓ(q − 2) + 2 g
(ℓ ≥ 2) T → ℓ·
n g
∗ The second time complexity is achieved via the bubble-filling technique described in Appendix E.4. Although theoretically
possible, bubble filling is not implemented in practice.
Table 4: Optimality of the three algorithm variants (as k → ∞). Setting
Small-ℓ regime
Large-ℓ regime
Single straggler One GPU per server
(1 < ℓ < 2)
(ℓ ≥ 2)
Optimal
Optimal
Multiple stragglers One GPU per server
(1 < ℓ1 < 2)
Single straggler Multiple GPUs per server
(ℓ1 ≥ 2)
†
Near-optimal†
Near-optimal
(ℓ ≥ 2)
(1 < ℓ < 2) ∗
Near-optimal (or Optimal)
Optimal
† For Row 2, we expect that both the current algorithm and the lower bound in the small-ℓ regime of Table 2 can be further
improved, and the branching point may change accordingly. The lower bound in the large-ℓ regime is expected to be tight for sufficiently large ℓ1 . ∗ The optimality result is achieved via the bubble-filling technique described in Appendix E.4. Although theoretically possible, bubble filling is not implemented in practice.
tighter bounds for the single-straggler case and the multi-GPU server setting: Theorem 6 sharpens Theorem 1, and Theorem 13 sharpens Theorem 3. B.1
Single Straggler Case
We first prove the bounds for the single-straggler case: Theorem 1 and its tightened version, Theorem 6. Consider p ≥ 3 GPUs performing an AllReduce on vectors of n elements. Exactly one GPU—the straggler Ps —has a degraded NIC with slowdown factor ℓ > 1: it transmits one element in ℓ time units. The remaining p − 1 GPUs are healthy, each transmitting one element in one time unit. Let F denote the total number of element-transfers during an execution. Let Fssend and Fsrecv denote the total number of elements sent and received by the straggler GPU Ps . 14
Theorem 1 (restated). Any correct AllReduce algorithm satisfies 2ℓ(p − 1) T ≥ max , ℓ · n. 1 + ℓ(p − 1) Lemma 4 (Total traffic). Any correct AllReduce algorithm satisfies F ≥ 2(p − 1) n. Proof. Apply Lemma 10 to the special case where each GPU forms its own group, i.e., q = p. Lemma 5 (Straggler incident volume). Any correct AllReduce algorithm satisfies Fssend ≥ n and Fsrecv ≥ n. Proof. For each P coordinate j ∈ [n], xPs ,j is initially known only to Ps while every other GPU must obtain sj = i xi,j ; hence information about coordinate j must leave Ps at least once. Also, Ps must output sj , which depends on inputs initially outside Ps ; hence information about coordinate j must enter Ps at least once. Summing over j gives the claim. Proof of Theorem 1. Let Fssend = x n,
Fsrecv = y n,
with x ≥ 1 and y ≥ 1 by Lemma 5. Let Fh→h be the total number of element-transfers from healthy GPUs to healthy GPUs (counted as directed transfers), and define Fh→s and Fs→h analogously. Then F = Fh→h + Fh→s + Fs→h , Straggler bottlenecks.
Fh→s = Fsrecv = y n,
Fs→h = Fssend = x n.
Every transfer incident to Ps costs ℓ, hence T ≥ ℓ Fssend = ℓx n.
(3)
T ≥ ℓ Fsrecv = ℓy n.
(4)
Similarly,
Healthy bottlenecks. Ignoring the extra time cost of healthy–straggler transfers on the healthy side, the total sending work across the p − 1 healthy GPUs is at least Fh→h + Fh→s , so T ≥
F − Fs→h Fh→h + Fh→s = . p−1 p−1
Using F ≥ 2(p − 1)n (Lemma 4) and substituting Fs→h = xn yields T x ≥2− . n p−1
(5)
Similarly, the total receiving work across healthy GPUs is at least Fh→h + Fs→h , which implies T y ≥2− . n p−1
(6)
Min–max form and symmetry reduction. Combining (3), (4), (5), and (6), for all x ≥ 1, y ≥ 1, T x y ≥ max 2 − , 2− , ℓx, ℓy . n p−1 p−1 Let g(x, y) denote the right-hand side. It is convex (a max of affine functions) and symmetric under swapping x and y, hence the minimum over x ≥ 1, y ≥ 1 is attained on the diagonal x = y = z ≥ 1. Substituting x = y = z, T z ≥ min max 2 − , ℓz . z≥1 n p−1 15
Solving the 1-D minimization. The first branch is decreasing in z, while the second is increasing. Their intersection is given by z 2− = ℓz, p−1 namely 2(p − 1) z⋆ = . 1 + ℓ(p − 1) 1 If z ⋆ ≥ 1, equivalently ℓ ≤ 2 − p−1 , then the minimum is attained at z ⋆ and T 2ℓ(p − 1) ≥ ℓz ⋆ = . n 1 + ℓ(p − 1) 1 If z ⋆ < 1, equivalently ℓ > 2 − p−1 , then over the feasible region z ≥ 1 the minimum is attained at z = 1, which gives T 1 ≥ max 2 − , ℓ = ℓ. n p−1 Therefore, 1 2ℓ(p − 1) , 1<ℓ≤2− , p−1 T ≥ n · 1 + ℓ(p − 1) 1 ℓ, . ℓ>2− p−1 Equivalently, 2ℓ(p − 1) T ≥ max , ℓ · n. 1 + ℓ(p − 1) □ Note: Theorem 1 ignores the extra time cost of healthy–straggler transfers on the healthy side. Accounting for this cost yields a strictly stronger lower bound, which is in fact tight with respect to p; see Appendix C for the matching upper bound and discussion. Theorem 6 (Tight Lower Bound: Single Straggler, One GPU per Server). Any correct AllReduce algorithm satisfies 2ℓ(p − 1) T ≥ max , ℓ · n. ℓ(p − 2) + 2 Proof of Theorem 6. We follow the notation introduced in the proof of Theorem 1. Thus, Fssend = x n,
Fsrecv = y n,
with x ≥ 1 and y ≥ 1, and F = Fh→h + Fh→s + Fs→h ,
Fh→s = y n,
Straggler bottlenecks. Similarly,
Fs→h = x n.
Every transfer incident to Ps costs ℓ, hence T ≥ ℓ Fssend = ℓx n.
(7)
T ≥ ℓ Fsrecv = ℓy n.
(8)
Healthy bottlenecks (time-weighted). Healthy→healthy transfers cost 1 per element, while any transfer between a healthy GPU and the straggler costs ℓ per element. Therefore the total sending work across the p − 1 healthy GPUs is at least Fh→h + ℓFh→s , so F − Fs→h + (ℓ − 1)Fh→s Fh→h + ℓFh→s = . T ≥ p−1 p−1 Using F ≥ 2(p − 1)n and substituting Fs→h = xn, Fh→s = yn yields T (ℓ − 1)y − x ≥2+ . (9) n p−1 Similarly, the total receiving work across healthy GPUs is at least Fh→h + ℓFs→h , which implies T (ℓ − 1)x − y ≥2+ . (10) n p−1 16
Min–max form and symmetry reduction. Combining (7), (8), (9), and (10), for all x ≥ 1, y ≥ 1, T (ℓ − 1)y − x (ℓ − 1)x − y ≥ max 2 + , 2+ , ℓx, ℓy . n p−1 p−1 Let g(x, y) denote the right-hand side. It is convex (a max of affine functions) and symmetric under swapping x and y, hence the minimum over x ≥ 1, y ≥ 1 is attained on the diagonal x = y = z ≥ 1. Substituting x = y = z, (ℓ − 2)z T ≥ min max 2 + , ℓz . z≥1 n p−1 Solving the 1-D minimization. If ℓ ≥ 2, both branches are nondecreasing in z, so the minimum is at z = 1 and Tn ≥ ℓ. If 1 < ℓ ≤ 2, the minimum is attained at the intersection 2 + (ℓ−2)z p−1 = ℓz, i.e., 2(p − 1) , ℓ(p − 2) + 2
z⋆ =
T 2ℓ(p − 1) ≥ ℓz ⋆ = . n ℓ(p − 2) + 2
Therefore, T ≥ n·
ℓ,
ℓ ≥ 2,
2ℓ(p − 1) , ℓ(p − 2) + 2
1 < ℓ ≤ 2.
Equivalently, 2ℓ(p − 1) T ≥ max , ℓ · n. ℓ(p − 2) + 2 □ B.2
Multiple Stragglers Case
Here we prove the bound for the multiple-straggler case, Theorem 2. Consider the same setting as above, but now m of the p GPUs are stragglers with heterogeneous slowdown factors ℓ1 ≥ ℓ2 ≥ · · · ≥ ℓm > 1; the remaining p − m are healthy. Let F denote the total send number of element-transfers, and let Fs,i denote the total elements sent by straggler i. Theorem 2 (restated). Any correct AllReduce algorithm satisfies ) ( 2(p − 1) Pm , ℓ1 · n . T ≥ max p − m + i=1 ℓ1i The proof relies on the following two lemmas. Lemma 7 (Total traffic bound). Any correct AllReduce algorithm satisfies F ≥ 2(p − 1) n. Proof. Identical to Lemma 4. Lemma 8 (Straggler send volume bound). For each straggler i, any correct AllReduce algorithm send satisfies Fs,i ≥ n. Proof. Identical to Lemma 5: each straggler’s private data must leave it via at least n transfers. send Proof of Theorem 2. Write Fs,i = xi n with xi ≥ 1 (by Lemma 8). We derive m + 1 bottleneck inequalities on T .
Straggler bottlenecks.
Each straggler i sends xi n elements at rate 1/ℓi : T ≥ ℓi xi n
for each i = 1, . . . , m . 17
(11)
Healthy-GPUP bottleneck. The p − m healthy GPUs collectively send at least F − 2(p − 1) n − ( i xi ) n elements (by Lemma 7). Averaging, Pm 2(p − 1) − i=1 xi n T ≥ . p−m
P
i xi n ≥
(12)
Taking the maximum of all m + 1 bottlenecks, ( ) P 2(p − 1) − i xi n T ≥ g(x1 , . . . , xm ) := max , ℓ1 x1 n, . . . , ℓm xm n . p−m
Combining.
This holds for every (x1 , . . . , xm ) with xi ≥ 1. Define y0 :=
2(p − 1) Pm 1 p − m + i=1 ℓi
and x⋆i := y0 /ℓi . These are obtained by equating P all m + 1 terms of g: setting ℓi xi = y for all i (giving xi = y/ℓi ) and solving [2(p − 1) − y i 1/ℓi ]/(p − m) = y yields y = y0 . The condition x⋆i ≥ 1 for all i reduces to y0 ≥ ℓ1 (since ℓ1 ≥ ℓi , if x⋆1 = y0 /ℓ1 ≥ 1 then x⋆i ≥ 1 for all i). Case 1 (y0 ≥ ℓ1 , i.e., all x⋆i ≥ 1): The minimum of g on {xi ≥ 1} is attained at (x⋆1 , . . . , x⋆m ) with value y0 n. Case 2 (y0 < ℓ1 , i.e., x⋆1 < 1): The balanced solution is infeasible. Since g is a max of terms including ℓ1 x1 n ≥ ℓ1 n, the minimum of g on {xi ≥ 1} is at least ℓ1 n. Combining both cases, (
2(p − 1) Pm T ≥ min g(x1 , . . . , xm ) = max , ℓ1 xi ≥1 p − m + i=1 ℓ1i
) · n, □
completing the proof.
Remark 9. Unlike the other two subsections in this section, the refinement of the healthy-side bottleneck does not extend directly to the present setting with multiple bad servers. The reason is that, once the inter-server traffic is decomposed according to healthy and bad endpoints, one now obtains four directed classes, Fh→h , Fh→b , Fb→h , Fb→b , rather than three. In particular, the additional bad-to-bad traffic Fb→b is not captured, so the same strengthening trick used in the previous two subsections cannot be applied here in a direct way. Consistency with the single-straggler bound. Setting m = max{2ℓ(p−1)/(ℓ(p−1) + 1), ℓ} · n, which coincides with Theorem 1. B.3
1 recovers T
≥
Multi-GPU per Server Case
Finally, we prove the bounds for the multi-GPU server setting with a single straggler: Theorem 3 and its tightened version, Theorem 13. Write q := p/g for the number of servers. We treat each server as a supernode. Inter-server communication uses NICs; intra-server communication uses NVLink. After normalization, each healthy NIC has unit rate, so each healthy server has aggregate NIC capacity g. One server Ss is slow: each of its NICs is degraded by factor ℓ, hence Ss has aggregate NIC capacity g/ℓ. Let F be the total traffic, Fnic the inter-server NIC traffic, Fssend the NIC traffic sent by Ss , and Fnv = F − Fnic the NVLink traffic. (We do not need a lower bound on Fnv ; ignoring NVLink can only weaken a lower bound on the runtime.) 18
NIC-time model. We count directed element-transfers. Any inter-server element-transfer that is incident to Ss takes ℓ time units; any inter-server transfer between healthy servers takes 1 time unit. Each server can send/receive at aggregate rate g (healthy) or g/ℓ (slow). Therefore, the total time T must be at least the corresponding (time-weighted) NIC workload divided by the relevant aggregate capacity. Theorem 3 (restated). Any correct AllReduce algorithm satisfies n 2ℓ(q − 1) T ≥ · max , ℓ . g 1 + ℓ(q − 1) Lemma 10 (Inter-group traffic per coordinate via supernodes). Partition the p GPUs into q ≥ 1 disjoint groups G1 , . . . , Gq . Count only inter-group element-transfers: a transfer contributes 1 to coordinate j iff it carries the j-th coordinate from some GPU in Gu to some GPU in Gv with u ̸= v. Then any correct AllReduce algorithm satisfies that for every coordinate j ∈ [n], the number of inter-group element-transfers carrying coordinate j is at least 2(q − 1). Consequently, the total inter-group traffic satisfies Finter ≥ 2(q − 1)n. Proof. Fix a coordinate j ∈ [n] and let sj =
Pp
i=1 xi,j . (j)
Supernode flow graph. For each time t, define a directed multigraph H≤t on vertex set [q] = {1, . . . , q} (the groups as supernodes) as follows: for every inter-group element-transfer of coordinate j that completes by time t from a sender in group Gu to a receiver in group Gv , add a directed edge u → v. For a group index r ∈ [q] and time t, say that group r can compute sj at time t if there exists some GPU in Gr whose local state at time t uniquely determines sj (equivalently, there exists a decoding function of its local state that outputs sj for all inputs). Let tj = inf{t : ∃r ∈ [q] such that group r can compute sj at time t}, and define the set of roots at the first completion time Aj = {r ∈ [q] : group r can compute sj at time tj }, aj = |Aj | (≥ 1). Key reachability property. Fix r ∈ Aj . Then every group u ∈ [q] must have a directed path (j) u ⇝ r in H≤tj ; otherwise the state within group r at time tj is independent of the inputs from Gu (for coordinate j), so by an indistinguishability argument r cannot uniquely determine sj at time tj . In particular, for any chosen r0 ∈ Aj , all u reach r0 . Choose an arbitrary r0 ∈ Aj . Since all vertices (j) reach r0 in H≤tj , the graph contains a spanning in-arborescence Tin rooted at r0 , hence |E(Tin )| ≥ q − 1. “Last-hop at tj ” into each root and disjointness. For every r ∈ Aj , there exists an inter-group edge er completing exactly at time tj whose head is r; otherwise group r would receive no new inter-group information about coordinate j at time tj , so r would already be able to compute sj at some t < tj , contradicting minimality of tj . The edges {er }r∈Aj are pairwise distinct (different heads). Any edge of Tin whose head is not r0 must complete at time < tj (otherwise information could not continue onward to reach r0 by time tj ). Therefore, {er : r ∈ Aj \ {r0 }} ∩ E(Tin ) = ∅. Hence the number of inter-group j-edges completed by time tj satisfies (j)
|E(H≤tj )| ≥ |E(Tin )| + {er : r ∈ Aj \ {r0 }} ≥ (q − 1) + (aj − 1). Edges after tj . For any group v ∈ / Aj , correctness implies it must eventually compute sj . If v received no inter-group j-edge after tj , its inter-group information about coordinate j would never change after tj , so it could never become able to compute sj , a contradiction. Thus each v ∈ / Aj must be the head of at least one inter-group j-edge completing after tj . These edges are distinct across different v, giving at least q − aj further edges. 19
Per-coordinate bound and summation. carrying coordinate j. Combining,
(j)
Let Finter be the number of inter-group element-transfers
(j) Finter ≥ (q − 1) + (aj − 1) + (q − aj ) = 2(q − 1). Summing over j ∈ [n] yields Finter ≥ 2(q − 1)n. Lemma 11 (Inter-server NIC traffic). Fnic ≥ 2(q − 1)n. Proof. Apply Lemma 10 with the q servers as groups (supernodes). Lemma 12 (Slow-server incident NIC volume). Let Fssend := Fssend be the total NIC traffic sent by Ss , and let Fsrecv be the total NIC traffic received by Ss . Then Fssend ≥ n, Proof. Fix a coordinate j ∈ [n] and write sj =
Fsrecv ≥ n. Pp
i=1 xi,j .
If no inter-server transfer carrying coordinate j is ever sent from Ss , then all other servers’ views (restricted to inter-server information) are independent of the inputs in Ss for coordinate j, so by indistinguishability they cannot uniquely determine sj for all inputs, contradicting correctness. Hence for each j, at least one j-element must be sent from Ss , giving Fssend ≥ n. Similarly, we have Fsrecv ≥ n. Proof of Theorem 3. Decompose the directed NIC traffic as Fnic = Fh→h + Fh→s + Fs→h ,
Fs→h = Fssend ,
Fssend = x n, so x ≥ 1 and y ≥ 1 by Lemma 12.
Fsrecv = y n,
Let
Slow-server NIC bottlenecks.
Fh→s = Fsrecv .
Since Ss has aggregate NIC rate g/ℓ, T ≥
Fssend ℓx n = . g/ℓ g
(13)
T ≥
Fsrecv ℓy n = . g/ℓ g
(14)
Similarly,
Healthy-server NIC bottlenecks. Ignoring the extra time cost of healthy–slow transfers on the healthy side, the total sending work across the q − 1 healthy servers is at least Fh→h + Fh→s , so Fh→h + Fh→s Fnic − Fs→h T ≥ = . (q − 1)g (q − 1)g Using Lemma 11 and substituting Fs→h = xn gives T 1 x ≥ 2− . (15) n g q−1 Similarly, the total receiving work across healthy servers is at least Fh→h + Fs→h , hence T 1 y ≥ 2− . (16) n g q−1 Combining (13), (14), (15), and (16), for all x, y ≥ 1, T 1 x y ≥ max 2 − , 2− , ℓx, ℓy . n g q−1 q−1 By symmetry in x, y (and convexity of the max of affine functions), the minimum over x, y ≥ 1 is attained at x = y = z ≥ 1, yielding T 1 z ≥ min max 2 − , ℓz . n g z≥1 q−1 Min–max and symmetry.
20
Solving the 1-D minimization.
The two branches intersect at 2−
z = ℓz, q−1
z⋆ =
2(q − 1) . 1 + ℓ(q − 1)
namely
1 , then the minimum is attained at z ⋆ and If z ⋆ ≥ 1, equivalently ℓ ≤ 2 − q−1
T ℓz ⋆ 1 2ℓ(q − 1) ≥ = · . n g g 1 + ℓ(q − 1) 1 If z ⋆ < 1, equivalently ℓ > 2 − q−1 , then over the feasible region z ≥ 1 the minimum is attained at z = 1, which gives T 1 1 ℓ ≥ max 2 − , ℓ = . n g q−1 g
Therefore, 1 2ℓ(q − 1) n 1 + ℓ(q − 1) , 1 < ℓ ≤ 2 − q − 1 , · T ≥ 1 g ℓ, ℓ>2− . q−1 Equivalently, T ≥
n 2ℓ(q − 1) · max , ℓ . g 1 + ℓ(q − 1) □
Similarly, Theorem 3 ignores the extra time cost of healthy–slow transfers on the healthy side. Accounting for this cost yields a strictly stronger lower bound, which is in fact tight; see Appendix E for the matching upper bound and discussion. Theorem 13 (Tight Lower Bound: Single Straggler, Multiple GPU per Server). Any correct AllReduce algorithm satisfies 2ℓ(q − 1) n · max , ℓ . T ≥ g ℓ(q − 2) + 2 Proof of Theorem 13. We follow the notation introduced in the proof of Theorem 3. Thus, Fnic = Fh→h + Fh→s + Fs→h ,
Fs→h = Fssend ,
Fssend = x n,
Fsrecv = y n,
Fh→s = Fsrecv ,
and with x ≥ 1 and y ≥ 1. Slow-server NIC bottlenecks.
Since Ss has aggregate NIC rate g/ℓ, T ≥
Fssend ℓx n = . g/ℓ g
(17)
T ≥
Fsrecv ℓy n = . g/ℓ g
(18)
Similarly,
21
Healthy-server NIC bottlenecks (time-weighted). Across the q − 1 healthy servers, the aggregate send rate is (q − 1)g. Sending healthy→healthy elements costs 1 time unit each, while any element sent to (or received from) Ss costs ℓ time units (the slow NIC throttles the transfer). Thus the total sending work across healthy servers is at least Fh→h + ℓFh→s , implying Fh→h + ℓFh→s Fnic − Fs→h + (ℓ − 1)Fh→s = . T ≥ (q − 1)g (q − 1)g Using Lemma 11 and substituting Fs→h = xn, Fh→s = yn gives 1 (ℓ − 1)y − x T ≥ 2+ . (19) n g q−1 Similarly, the total receiving work across healthy servers is at least Fh→h + ℓFs→h , hence T 1 (ℓ − 1)x − y ≥ 2+ . (20) n g q−1 Min–max and symmetry. Combining (17), (18), (19), (20), for all x, y ≥ 1, 1 (ℓ − 1)y − x (ℓ − 1)x − y T ≥ max 2 + , 2+ , ℓx, ℓy . n g q−1 q−1 By symmetry in x, y (and convexity of the max of affine functions), the minimum over x, y ≥ 1 is attained at x = y = z ≥ 1, yielding T 1 (ℓ − 2)z ≥ min max 2 + , ℓz . n g z≥1 q−1 Solving the 1-D minimization. If ℓ ≥ 2, both branches are nondecreasing in z, so the minimum is at z = 1 and Tn ≥ gℓ . If 1 < ℓ ≤ 2, the minimum is attained at the intersection 2+ i.e., z⋆ = Therefore,
(ℓ − 2)z = ℓz, q−1
2(q − 1) T ℓz ⋆ 1 2ℓ(q − 1) , ≥ = · . ℓ(q − 2) + 2 n g g ℓ(q − 2) + 2 ℓ ≥ 2, ℓ, n T ≥ · 2ℓ(q − 1) g , 1 < ℓ ≤ 2. ℓ(q − 2) + 2
Equivalently, T ≥
n 2ℓ(q − 1) · max , ℓ . g ℓ(q − 2) + 2
□ Remark 14 (Dropping the NVLink term). In addition to the NIC constraints, we also have the NVLink-time constraint Fnv T ≥ , qv since the q servers have total aggregate NVLink capacity qv. Using the global traffic bound F ≥ 2(p − 1)n and Fnv = F − Fnic , we get Fnv ≥ 2(p − 1)n − Fnic . Plugging in the minimum possible inter-server traffic Fnic = 2(q − 1)n (from Lemma 10) yields 2(p − q)n 2(g − 1)n 2(p − 1)n − 2(q − 1)n = = , T ≥ qv qv v where we used p = gq. Under our NVLink-rich assumption v ≥ g(g − 1), this term is at most 2n/g, and hence it does not affect the main results of this section. Intuitively, in NVLink-poor settings (e.g., per-GPU NVLink bandwidth is not at least (g − 1) times the NIC bandwidth, i.e., v < g(g − 1) in our normalization), then Fnv /(qv) can become the dominant bottleneck and should be kept explicitly. Conversely, when NVLink is at least this (g − 1)-fold “multiplier,” intra-server aggregation is never the limiter. 22
C
Time Analysis for Bubble Filling (ℓ < 2)
When ℓ < 2, each Stage 2/3 flow occupies ℓ s time on the straggler link while the corresponding ring slot takes 2s. Bubble filling enlarges every Stage 2/3 flow to carry an additional (2−ℓ) s′ /ℓ elements of a point-to-point AllReduce between the healthy servers and the straggler, where s′ denotes the new section size. The enlarged flow has duration (1 + (2−ℓ)/ℓ) · ℓ s′ = 2s′ , matching the ring slot exactly. Data accounting.
Each group of four segments (one per pattern) processes two kinds of data:
• Ring path: (p−1) sections of size s′ , totalling (p−1) s′ elements. • P2P path: (2−ℓ) s′ /ℓ additional elements allreduced via the straggler bubbles. With k/4 groups (i.e. k segments total) the constraint n = k (p−1) s′ + (2−ℓ) s′ /ℓ gives s′ =
nℓ . k (p−2)ℓ + 2
Total time. Because every slot now has duration 2s′ , each middle body takes 2(p−1) s′ . The straggler’s serialized recv chain across all k+1 bodies takes 2k(p−1) s′ (the HEAD bub-up and TAIL Stage 2 flows are shorter than middle Stage 2 flows, but their durations sum to exactly 2k(p−1) s′ ). In addition, ring-flow dependencies at the HEAD and TAIL add a startup/drain overhead of 2(ℓ−1)(p−1) s′ (at ℓ = 1 the HEAD/TAIL flows are short enough to hide entirely within the straggler chain; at ℓ = 2 they contribute a full extra body). Hence 2(p−1) ℓ n k + ℓ − 1 T = 2k + 2(ℓ−1) (p−1) s′ = (p−2)ℓ + 2 k 2(p−1) ℓ n k→∞ . −−−−→ (p−2)ℓ + 2 Comparing with Theorem 6, we see that our algorithm achieves bandwidth optimality without requiring p → ∞, confirming its optimality even for small clusters. Overhead bound. Compared with the non-degraded baseline T0 = 2(p−1) n/p (single GPU per server, g=1), T pℓ . = T0 (p−2)ℓ + 2 This ratio is increasing in ℓ on [1, 2] and attains its maximum p/(p−1) = 1 + 1/(p−1) at ℓ = 2, so the overhead is at most 1 + 1/(p−1) for all ℓ ∈ [1, 2].
D
Algorithm Construction for Multiple Stragglers
We extend the four-stage pipelined algorithm of Section 4 from one straggler to m ≥ 2 stragglers. Throughout, p denotes the total number of GPUs (one per server), of which GPUs 0, . . . , m−1 are stragglers with slowdown factors ℓ1 ≥ · · · ≥ ℓm > 1, and GPUs m, . . . , p−1 are healthy. D.1
Four-Stage Decomposition
As in Section 4.1, we partition the n input elements into k segments, each containing p−m sections of size s = n/(k(p−m)). Each segment undergoes four stages: 1. Stage 1 (Reduce-Scatter): The p−m healthy GPUs perform a reduce-scatter of the segment along a directed ring, accumulating partial sums over p−m−1 hops. 2. Stage 2 (Upload): Each healthy GPU sends its partial sum to every straggler. Each straggler receives p−m uploads over its slow NIC. 3. Stage 3 (Download): Each straggler folds in its local contribution and sends the result back to every healthy GPU. Each straggler sends p−m downloads. 23
Stage 3 0 1 2 3 4 5 6
2 3
3 4
4 5
5 6
Stage 1
Stage 4
Stage 2
Stage 3 0 1 2 3 4 5 6
6 2 3 4 5 6
5 6 2
6 2
3 4
3 4 5
2
3 4 5 6 2
3 4 5 6
5 6 2
6 2
3 4
3 4 5
2
3 4 5 6 2
1
0 1
0 1
0 1
0
0 1
2 3
3 4
4 5
5 6
3 4 5 6
(a) Pattern B (S3→S1→S4→S2) Stage 3 0 1 2 3 4 5 6
2 3
3 4
4 5
5 6
Stage 1
Stage 4
3 5 6 2
6 2
3 4
3 4 5
2
3 4 5 6 2
3 4 5 6
5 6 2
6 2
3 4
2
3 4 5
3 4 5 6 2
1
0 1
0
Stage 4
Stage 2
5 6 2
6 2
3 4
3 4 5
2
3 4 5 6 2
3 4 5 6
5 6 2
6 2
3 4
3 4 5
2
3 4 5 6 2
1
0 1
0 1
0 1
0
0 1
(b) Pattern D (S3→S1→S4→S2) Stage 2
Stage 3 0 1 2 3 4 5 6
6 2 4 5 6
Stage 1 6 2
0 1
0 1
0 1
′
2 3
3 4
4 5
5 6
Stage 1
Stage 4
Stage 2
6 2 3 4 5 6
5 6 2
6 2
3 4
3 4 5
2
3 4 5 6 2
3 4 5 6
5 6 2
6 2
3 4
2
3 4 5
3 4 5 6 2
1
0 1
0
0 1
0 1
0 1
′
(c) Pattern A (S1→S2→S3→S4)
(d) Pattern C (S1→S2→S3→S4)
Figure 11: Flow schedules for the four multi-straggler patterns (p=7, m=2). Rows 0–1 (red labels) are stragglers; rows 2–6 are healthy. Each cell’s label indicates the destination GPU. Colored cells belong to the named pattern; uncolored cells belong to other patterns. 4. Stage 4 (Allgather): The healthy GPUs allgather the global sums along the ring in p−m−1 hops. The same two stage orderings from Section 4.1 remain valid, and the disjoint-resource principle still holds: Stages 2/3 use only the straggler NICs while Stages 1/4 use only the healthy ring links. D.2
Schedule Construction
We design four patterns—B, D, A′ , C′ —analogous to the single-straggler patterns of Section 4.2, but adapted to multiple stragglers. We illustrate the construction for p = 7, m = 2 (GPUs 0–1 are stragglers; GPUs 2–6 are healthy). Window structure. Each parallel body is divided into p−1 windows, each comprising two subslots. Of these, p−m−1 windows carry merged ring flows (S1+S4 or S1+S3, as in the single-straggler case), and m windows carry straggler communication (one per straggler). The body duration is 2(p−1) s when all straggler flows fit inside a 2s-wide window, which holds whenever ℓi ≤ 2 for all i. Four patterns.
The patterns are defined as follows:
• Pattern B: S3 → S1 → S4 → S2. • Pattern D: S3 → S1 → S4 → S2 (same ordering as B, with the same offset). • Pattern A′ : S1 → S2 → S3 → S4. • Pattern C′ : S1 → S2 → S3 → S4 (same ordering as A′ , with flows in Stages 1 and 3 shifted). Figure 11 shows the four individual patterns for p = 7, m = 2. Pipelining. Overlaying the four patterns produces the composite schedule of Figure 12. With k a multiple of 4, each pattern processes k/4 segments. Every parallel body in the steady state contains one instance of each stage from each pattern, fully utilizing both the healthy ring and all straggler links. D.3
Time Analysis
Each segment has p−m sections of size s = n/(k(p−m)). In each parallel body, the healthy GPUs occupy p−1 windows of 2s each, for a total of 2(p−1) s. Each straggler i must send or receive p−m flows, each of duration ℓi s, giving a straggler chain of ℓi (p−m) s. In the current schedule, additional 2(m − 1) sections between healthy servers will be sent after the healthy servers finish communication with stragglers. The body duration is therefore Tbody = max{ 2(p−1) s, (ℓ1 (p−m) + 2(m − 1)) s } . With k/4 groups (each spanning four patterns) plus startup/drain equivalent to one body, the total time is k T = + 1 · 4 Tbody = (k + 4) Tbody . 4 24
Parallel body 1
Parallel body 2
Stage 3
0 2
straggler 1
2 3 healthy 4 5 6
3
3 4
4 5
5 6
Parallel body 3
Stage 1 Stage 3
6 2
2 3
3 4 4 5 6
4 5
5 6 3
5 6 2
6 2 3 4
6 2
Parallel body 4
Stage 4 Stage 1 Stage 3
Stage 2 Stage 4 Stage 1 Stage 3
2 3 4 5 6 2 3 4 5 6 3 4 5 6 2 3 4 5 6 2 3 3 3 3 3 3 3 3 3 1 0 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 1 0 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 1 0 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 1 0 6 6 2 2 2 2 2 2 2 2 2 0 2 2 2 2 2 2 1 2 2
3 4 5
2
Parallel body 5
Parallel body 6
Parallel body 7
Stage 2 Stage 4 Stage 1
Stage 2 Stage 4
Stage 2
0 1 0 3 3 3 3 3 3 3 3 2 1 0 4 4 4 4 4 4 3 4 4 1 1 0 5 5 5 5 healthy 4 5 5 5 5 0 6 6 5 6 6 6 6 6 6 1 6 0 2 2 2 2 2 2 1 2 2
straggler
1 4 5 6 0
0 1
3 0 1
5 6 2
6 2
3 4 0 1 2
3 4 5 0 1
3 4 5 6 2
1
0 1
0 1
0 1
0
0 1
Figure 12: Combining the four multi-straggler patterns into a complete pipeline (p=7, m=2). Rows 0–1 are stragglers; rows 2–6 are healthy. The schedule has 7 parallel bodies; each steady-state body interleaves all four stages across the four patterns. No NIC sends or receives two flows simultaneously. Case ℓ1 < 2 (ring-bottlenecked). The body is determined by the healthy GPUs: Tbody = 2(p−1) s. Substituting s: T = (k + 4) · 2(p−1) s = k→∞
−−−−→
2(p−1) k + 4 n p−m k
2(p−1) n. p−m
Case ℓ1 ≥ 2 (straggler-bottlenecked). The body is determined by the worst straggler: Tbody = (ℓ1 (p−m) + 2(m − 1)) s. Substituting: T = (k + 4) · (ℓ1 (p−m) + 2(m − 1)) s = 2(m − 1) k→∞ −−−−→ ℓ1 + n. p−m
ℓ1 (p−m) + 2(m − 1) k + 4 n p−m k
Comparison with the P lower bound. From Theorem 2, the lower bound (for p ≫ m) is T ≥ max{2(p−1)/(p−m+ 1/ℓi ), ℓ1 } · n. Our algorithm achieves 2(p−1) 2(m − 1) k→∞ , ℓ1 + · n. T −−−−→ max p−m p−m In both cases, the ratio of the achieved time to the lower bound approaches 1 as p → ∞ with m fixed (or as m/p → 0), confirming near-optimality in large clusters.
E
Algorithm Design for Multi-GPU Servers
As outlined in Section 4.4, we now consider the practical setting where each server hosts multiple GPUs. Let p be the total number of GPUs, g the number of GPUs per server (typically g ∈ 25
{1, 2, 4, 8}), and q = p/g the total number of servers. Each GPU within a server has its own dedicated NIC for inter-server communication, and the g GPUs are additionally connected to each other through a high-bandwidth NVLink fabric. Notation. We adopt the same symbols as Section 4. The total input of n elements is first split into g parts of size n/g, one per leading-GPU position; the cycle anchored at each leading GPU operates on its own part. Each part is then split into k segments, and each segment into q−1 sections of size n s = g k (q−1) elements. A healthy NIC therefore takes s time units to transmit one section, and an NVLink hop on one local ring (running at (g−1)× NIC speed) takes s/(g−1) time. The pattern-overlay construction of Section E.2 requires 8 | k (so that the four patterns each receive an integer number of segments) and k ≥ 24 (so that the head, the steady-state interior, and the tail of the schedule do not overlap); we assume both throughout. Throughout this appendix we adopt the following bandwidth model for the NVLink fabric, which reflects the configuration commonly deployed in practice: • Each GPU has its own pair of NVLink up/down links, with per-direction bandwidth equal to (g−1) times the NIC bandwidth, enough to keep one GPU communicating with all of its g−1 siblings at full NIC speed simultaneously. • Different GPUs’ NVLink lanes do not interfere, so all g local GPUs can send and receive at (g−1)× the NIC speed in parallel. In particular, when one GPU broadcasts (or reduces) a value across the remaining g−1 GPUs, the operation completes in the same time that a single healthy NIC flow of equal size would take. At g = 1 the NVLink term disappears and the model degenerates to the single-GPU case of Section 4. Thanks to PXN [17] (Section 2), all g NICs on a degraded server pool their bandwidth equally, so we may assume without loss of generality that they share the same slowdown factor ℓ. We extend our algorithm to this setting in a way that closely parallels the classical AllReduce with NVLink: the data circulates over NVLink inside each server in addition to crossing the inter-server NIC ring. Our scheduler then overlaps the NVLink work with the NIC work so that the intra-server traffic does not extend the critical path. The cleanest mental model is to run g concurrent copies of the single-GPU schedule, one per local GPU index. Inside every server the g GPUs are connected as an NVLink ring; each ring instance is “led” by a different local GPU position, and the g rings operate in parallel without interfering with the inter-server schedule. The leading GPU of each ring uses that ring to collect its server’s data on NVLink before each NIC send and to disperse the received data on NVLink after each NIC receive. Figure 13 sketches the topology: each server holds g GPUs that talk to each other over NVLink, and each GPU uses its own NIC to communicate with the corresponding GPU on every other server, so the leading GPUs across servers form g independent inter-server rings. E.1
NVLink Phases Around the Four Stages
Each of the four stages of Section 4.1 now requires NVLink work in addition to its NIC traffic. Before a section is sent out over the NIC, the g local GPUs must collect it on NVLink so the leading GPU holds the value to be transmitted; after a section arrives on the NIC, the leading GPU must distribute it to the other g−1 GPUs over NVLink. We rename the four original inter-server stages S1, S2, S3, S4 and label the new intra-server stages N1, N2, N3, N4: each Sk is paired with a matching Nk placed either immediately before or immediately after it, and the linear dependencies among these N and S stages admit the two possible orderings shown in Figure 14. An N stage uses only NVLink and an S stage uses only the NIC. The role of each N phase mirrors the corresponding S phase, and the ordering N ↔ S is fixed by data dependencies: • N1 (collect): before S1, each healthy server reduces its local segment over NVLink onto the leading GPU, so that the leading GPU holds the value about to be sent over the NIC. • N2 (distribute): after S2, the straggler’s leading GPU passes the just-received partial sum over NVLink to the other g−1 local GPUs. Under Schedule type 2 this is a plain broadcast; under 26
Single-GPU Server Optimal Algorithm
Server 1
GPU
Server 2
Leader GPU
Server 3
NIC
Broken NIC
Server 0 (NIC fault)
NVLink
NVLink flow
Inter-server flow
Figure 13: Multi-GPU servers: GPUs inside the same server communicate over NVLink, while GPUs on different servers communicate over the NIC. Each server hosts g GPUs and each GPU has its own NIC for inter-server traffic. We run g instances of the single-GPU schedule in parallel, anchored at each local GPU index in turn; intra-server NVLink transfers aggregate data before each NIC send and disperse it after each NIC receive. Each NVLink lane is provisioned at (g−1)× NIC bandwidth and operates independently per GPU and per direction.
Schedule type 1
N1
S1
S2
N2
N3
S3
S4
N4
Schedule type 2
N3
S3
N1
S1
S4
N4
S2
N2
Stage 1 Straggler server 0 Healthy server 1
2
2
Healthy server 2
3
3
Healthy server 3
4
4
4
1
1
Healthy server 4
2 3
1
Internal structure of one S block (here: S1 of Schedule type 2)
Figure 14: Schedule schematic showing the two possible orderings of NVLink (N) and NIC (S) stages that augment the four-stage decomposition of Section 4.1. The two schedule types correspond to the two stage orderings discussed therein.
27
Schedule type 1 the data instead traverses the local NVLink ring in one direction, with each GPU folding in its own contribution as it passes through, so that the GPU at the end of the ring accumulates the full partial sum. • N3 (collect): before S3, the straggler’s leading GPU obtains over NVLink the value about to be sent over the NIC. Under Schedule type 2 this is a plain reduce of the local copies onto the leader; under Schedule type 1 the accumulated partial sum left at the end of the N2 ring traverses the same ring in the reverse direction, depositing the value onto every local GPU along the way before arriving at the leading GPU. • N4 (distribute): after S4, each healthy server’s leading GPU broadcasts the just-received global sum over NVLink to the other g−1 local GPUs. Data dependencies constrain the order of the eight phases within one loop iteration; Figure 14 shows two viable orderings. E.2
Alternating N and S
Schedule types in Figure 14 do not parallelise cleanly across the four patterns: in some places two S phases sit next to each other while in others a single S is separated from the next S by an N, so no cyclic shift of the eight-phase sequence can align the four patterns into columns containing four distinct S phases or four N phases. To obtain such an alignment we defer selected phases to a later loop iteration, carrying along every phase that depends on them so that the relative order required by the data dependencies is preserved. This gives the strict N–S alternation of Figure 15. Patterns A and C use the Schedule-type-1 sequence and patterns B and D use the Schedule-type-2 sequence. The figure has eight rows: rows 1–4 list patterns A, B, C, D once each, and rows 5–8 repeat the same four patterns shifted by one column, so that the eight rows together fill every NIC and every NVLink slot. Reading only the S phases of the first four rows recovers the order and overlay of the four single-GPU patterns in Figure 6. A primed label (e.g., N3′ ) marks a phase whose data comes from the previous loop iteration; a doubly-primed label (e.g., N4′′ ) marks data from two iterations earlier. N1
Healthy I leading
Pattern A
N1
S1
N3'
S2
N4''
S3'
N2
S4'
Pattern B
N3
S3
N1
S1
N2'
S4
N4
S2
Pattern C
N1
S1
N3'
S2
N4''
S3'
N2
S4'
Pattern D
N3
S3
N1
S1
N2'
S4
N4
S2
S1
N3'
S2
N4''
S3'
N2
S4'
Pattern A Pattern B Pattern C Pattern D
N1 N3
S3
N1
S1
N2'
S4
N4
S2
N1
S1
N3'
S2
N4''
S3'
N3
S3
N1
S1
N2'
S4
N2 N4
S4'
Healthy All running
I II III IV
Straggler I leading
I II III IV
Straggler All running
S2
Figure 15: Eight-row N–S schedule built from schedule types of Figure 14. A primed label (e.g., N3′ ) marks a phase whose data comes from the previous iteration; a doubly-primed label (e.g., N4′′ ) marks data from two iterations earlier.
I II III IV
I II III IV
N3'
N4''
N2
II I
III
II
IV
III IV IV IV
II
II
II
I
I
I
III
III
III
II
II
II
IV IV IV
III
III
III
I
I
I II
I
III
II
IV
III IV IV IV
II
II
II
I
I
I
III
III
III
II
II
II
IV IV IV
III
III
III
I
I
I
Figure 16: NVLink data flow, shown for Pattern A (other patterns follow the same template). Rows index the local GPUs on a server (g = 4). Each cell is one NVLink hop, labelled by the destination GPU; one hop carries (p−1) s elements.
Inside a single N body the intra-server work itself runs as a small NVLink ring across the g local GPUs. Figure 16 illustrates the traffic for Pattern A: the healthy and straggler servers each contribute an g-row panel, and each cell labels the destination GPU on the local ring. (We set g = 4 in the figure for illustration and label the four GPUs I/II/III/IV; the construction generalises to arbitrary g.) The collect phases (N1, N3) and the distribute phases (N2, N4) run the NVLink ring in opposite directions: collect uses the backward ring IV → III → II → I (leader receives, never sends), and distribute uses the forward ring I → II → III → IV (leader sends first). Combining the data flows from all g choices of leading GPU exactly fills the ring: at every sub-slot every GPU is sending to its ring neighbour, so all g NVLink links are saturated in parallel. Because NVLink is a factor of g−1 faster than the NIC, and one pattern inside a GPU-led cycle carries (q−1) s = n/(gk) elements, the 28
NVLink ring can cycle the data of all g leadings to every local GPU in just s time units, i.e. half a body, as shown in Figure 16. Putting the four patterns together, both transports (NIC and NVLink) and both server types (healthy and straggler) combine into the composite schedule of Figure 17. The Inter-server panel is identical to the single-GPU composite of Section 4.2 (Figure 6); the two NVLink panels show how the local rings at each server type are kept busy in parallel. When ℓ = 2, joining body 1 to body 9 turns Figure 17 into a closed cycle in which the NVLink bandwidth saturates in every odd body and the NIC bandwidth saturates in every even body; overlaying a second copy of the cycle shifted by one body then keeps both transports saturated at every instant. E.3
Tail Optimization
Since the primed phases cross iteration boundaries (N3′ , S3′ , S4′ reach back one iteration and N4′′ two), the schedule is not yet periodic at its endpoints. At the head, the first cycle (first 8 bodies of each pattern as shown in Figure 17) must leave every primed and doubly-primed phase empty and the second cycle must leave every doubly-primed phase empty, giving a head of 16 bodies; one can check that no further compression is possible. From body 17 onward every parallel body is filled. At the tail, the matching leftovers — one cycle that runs only the primed and doubly-primed phases, plus one cycle that runs only the doubly-primed ones — can be packed much more tightly: by merging remaining phases whenever the two can share a parallel body (e.g., a body labelled “S4/N4” carries both a Stage-4 NIC flow and the matching N4 step at the same time), the entire tail fits in at most 6 bodies, as shown in Figure 18. The last tail body is physically shorter than the others because its remaining inter-server work — a sole S4 phase of duration s(q − 2)/(q − 1) — takes less than half of a normal 2s body. This design applies to any value of ℓ, and the bottleneck is set by which resource saturates first. For ℓ > 2 the straggler NIC is the bottleneck and the healthy NICs and both NVLink rings still have spare capacity; for ℓ < 2 only the straggler NIC is under-utilised, while every healthy NIC and both NVLink rings run fully loaded. E.4
Time Analysis
Recall that one healthy NIC hop on a section of s elements takes s time units. Under our bandwidth model each NVLink lane runs at (g−1)× NIC speed, so a single NVLink hop on one local ring takes s/(g−1) time. Each N body actually performs two ring traversals — one collect and one distribute — for a total of 2(g−1) hops, costing 2(g−1) · s/(g−1) = 2s. For ℓ ≤ 2 this matches the 2s duration of the S body exactly, and for ℓ > 2 it is strictly shorter than the ℓs-long S body, so within the steady-state cycle the NVLink work always fits and adds no new critical path; the head and tail need a separate accounting. The remaining accounting then follows the single-GPU analysis of Section 4.3 without the bubblefilling optimization; the bubble-filling subtlety is addressed in Case ℓ < 2 below. Counting bodies is now straightforward (using the head/tail decomposition of Section E.3). With k segments in total, the steady-state interior runs from body 17 through body k, for k − 16 fully filled bodies; the head spans the first 16 bodies but is effectively only 15.5 body-lengths since the first half of body 1 is empty; the tail occupies at most 6 bodies. The total schedule length is therefore at most (k − 16) + 15.5 + 6 = k + 5.5 body-lengths. Case ℓ ≥ 2 (straggler-bottlenecked). Each parallel body takes ℓ (q−1) s = ℓn/(gk) time. Multiplying by the body count k + 5.5 derived above, T ≤ ℓ (q−1) s (k + 5.5) =
ℓ n (k + 5.5) k→∞ ℓ n −−−−→ , gk g
(21)
i.e. the g leading-GPU cycles, each handling n/g elements via its own ring of NICs, jointly recover a g× speed-up over the single-GPU schedule of Equation (1). This matches the ℓn/g lower bound from Theorem 3 and Theorem 13 in this regime, so the algorithm is bandwidth optimal without requiring p → ∞. 29
Case ℓ < 2 (ring-bottlenecked). time regardless of ℓ, giving
Without bubble filling each body takes 2 (q−1) s = 2n/(gk)
T ≤ 2 (q−1) s (k + 5.5) =
2 n (k + 5.5) k→∞ 2 n −−−−→ . gk g
(22)
Recall that Theorem 13 (strictly tighter than Theorem 3) gives the lower bound TLB =
2ℓ(q − 1) n · g ℓ(q − 2) + 2
for ℓ < 2. The ratio of our T = 2n/g to this bound is T ℓ(q − 2) + 2 q = < . TLB ℓ(q − 1) q−1 so the algorithm is within a factor q/(q−1) of the theoretical lower bound across the whole ℓ < 2 range. As q → ∞, this factor approaches 1, confirming near-optimality in large clusters. Bubble-filling in the multi-GPU server case. The bubble-filling technique of Section 4.2 cannot be directly applied here: for ℓ ≤ 2, each body already saturates the local NVLink ring, leaving no spare NVLink bandwidth to carry the additional P2P traffic that bubble filling would inject. In principle, one could slice each straggler bubble into g pieces and distribute them across the g leading-GPU cycles to recover that bandwidth. This would close the remaining q/(q−1) gap and match the lower bound of Theorem 13 exactly without requiring q → ∞ (following a time analysis similar to Appendix C); however, the resulting savings are marginal and do not justify the added scheduling complexity. E.5
Potential Extension to Multiple Straggler Multiple GPU per Server Case
The alternating N-S phase construction here can be combined with the new S phase developed in Appendix D. The only obstacle is that patterns A and C are now replaced by patterns A’ and C’, which also alters the alternating N-S schedule. A modified schedule is provided in Figure 19. Due to space constraints, we omit the full construction details, time analysis, and corresponding theoretical lower bound.
F
Large-Message Evaluation (N =8 GiB)
This appendix repeats the three sweeps of Section 5 at the much larger message size N =8 GiB — well beyond the buffer sizes that real DDP/FSDP implementations use, but useful as a stress test that exposes the asymptotic per-byte rate of each algorithm. Single-straggler results are in Figure 20, multi-straggler in Figure 21, and multi-GPU-per-server in Figure 22. All trends discussed in the main text (OptCC tracking NCCLNoFailure within 1+1/(p−1) overhead, linear scaling in N , and the ℓ ≤ 2 plateau) persist at this larger message size.
30
Parallel body 1
Parallel body 2
N1 N3
0 1 2 3 4 I NVLink II healthy III IV I NVLink II straggler III IV
Parallel body 3
S1 S3
1
Interserver
2
2 3 4
3 3 4 1
4
2
S2 S1 S1 S3
2 3
4 1
Parallel body 5
Parallel body 4
N3' N1 N1 N3
2 3 4
1
1
0
2 3 4
3 4 1
2 0
2
3 4 1
4 1
3
N4'' N2' N3' N1
2
0
2 3
4 1
1
4 0
2 3 1
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
II III IV I
II III IV I
II III IV I
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
II III IV I
II III IV I
II III IV I
Parallel body 7
Parallel body 6 S3' S4 S2 S1
Parallel body 8
N2 N4 N4'' N2'
0 1 2 3 4 1 2 2 0 2 2 2 2 Inter2 3 3 3 3 0 3 3 server 3 4 4 4 4 4 4 0 4 0 1 1 1 1 1 1 I NVLink II healthy III IV I NVLink II straggler III IV
S4' S2 S3' S4
1
2 3 4
0
2 3 4
3 4 1
2 0
2
3 4 1
4 1
3 0
2
4
2 3
4 1
0
1
Parallel body 9
Parallel body 10
N2 N4
S4' S2
2 3
2 3 4
1
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
3 4 1
0
0
2 4 1
2 3
0
1
0
Figure 17: Composite multi-GPU schedule, drawn for ℓ = 2. Each parallel body is either an N body (NVLink active, NIC idle) or an S body (NIC active, NVLink idle); N and S alternate strictly. The Inter-server table matches Figure 6; the NVLink healthy and NVLink straggler tables show how the local rings at each server type are filled. Closing this schedule into a cycle (body 1 glued to body 9) and overlaying a second copy shifted by one body fills every parallel body.
A1 B1 C1 Pattern D1 A2 B2 C2 D2 1 0 1 2 2 Inter2 3 3 server 3 4 4 0 4
Tail body 1
Tail body 2
N2 N4 S4' S2 S3' S4
S4' S2 N3/N4'
N3/N4'
2 0 3 4 1
Tail body 3
S3
S4 N2 N3/N4'
2 3 4 1
4 1
4 2
2 3
0 4 1
1 2 3
0 1
2 0
2 3 4
1
4
2
1
2 3
0 4 1
2 3 4
0 1
2 0
S4 N2 N3/N4'
2 3 4
3 2
3 4 1
0
3 4 1
I II II III III IV IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
I II NVLink II III straggler III IV IV I
II III IV I
II III IV I
IV I II III
IV I II III
IV I II III
II III IV I
II III IV I
II III IV I
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
IV I II III
NVLink healthy
S4/N4 N2 N4
S4' S2 3
3 4 1
0
Tail body 5
S3
N4
S3
N2 N4 3
Tail body 4
4 2
2 3
0 4 1
II III IV I
1
4 1
2 3
2 3 4 1
0 1
II III IV I
1
II III IV I
2 2 3 4 1
Tail body 6
S3 3
4
1
2 3 4 1
2 3 4 1
S4/N4 N2
2 2 3 4 1
3
4
2 3 4 1
2 3 4 1
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
IV I II III
IV I II III
IV I II III
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
2 3 4 1
2 3 4 1
II III IV I
II III IV I II III IV I
II III IV I
II III IV I
II III IV I
II III IV I
Figure 18: Tail schedule for the multi-GPU algorithm, drawn for ℓ = 2. The eight stage-label rows (A1–D2) are exactly the four pattern rows of Figure 17 together with the same four rows shifted by one body — the two copies whose overlay fills the steady-state schedule. A label of the form “Sk/Nk” marks a tail body in which two phases are fused.
Pattern B
N3
S3
Pattern D
N1
S1 N2' S4
N3
S3
Pattern A'
Pattern D Pattern A'
N3
S3
S2
S1 N2' S4
N3
S3
N4
S2
N1
S1 N2' S4
N3
S3
N1
N1
S1 N2' S4
N4
S2
N3
S3
Pattern C' Pattern B
N4
N1
N1
S1 N2' S4
N3
S3
Pattern C'
N4
S2
S1 N2' S4
N4
S2
S2
N1
S1 N2' S4
N3
S3
N1
N4
N4
S2
S1 N2' S4
N4
S2
Figure 19: Eight-row alternating N–S schedule with patterns A′ and C′ substituted for patterns A and C.
31
N=8 GiB, =2
p=64, =2
400 350 300 250 200 50
100
150
Number of GPUs p
200
600 400 200 0
250
(a) Varying p (GPUs).
p=64, N=8 GiB
800
800
AllReduce time (ms)
AllReduce time (ms)
AllReduce time (ms)
450
700 600 500 400 300 200
400
800
1200
1600
Message size N (GiB)
2000
1.2
(b) Varying n (message size).
1.6
2.0
2.4
Slowdown factor
2.8
(c) Varying ℓ (slowdown).
Figure 20: Single-straggler AllReduce completion time on SimAI for OptCC versus ICCL, NCCLNoFailure (no failure), and R2 CCL, at N =8 GiB. Filled markers are SimAI measurements; open markers are estimated values for bins not yet measured (filled in via the analytical model with p(ℓ−1) empirical scaling). R2 CCL is plotted from its closed form TR2 CCL = TNCCLoptimal 1 + 2(p−1) ; no measurements yet. (a) As p grows, OptCC’s completion time approaches NCCLNoFailure while the gap to NCCL and R2 CCL widens. (b) The absolute time gap grows linearly with message size n. (c) As the straggler becomes slower (ℓ increases), OptCC remains bounded by max{2, ℓ} n whereas NCCL and R2 CCL grow linearly in ℓ from ℓ=1.
m=2, 1=2, 2=1.5, N=8 GiB
m=2, 1=2, 2=1.5, p=64
400 350 300 250 200 50
100
150
Number of GPUs p
200
800 600 400 200 0
250
(a) Varying p (GPUs).
400
800
1200
1600
Message size N (GiB)
m=2, 1 = 2, p=64, N=8 GiB
800
AllReduce time (ms)
AllReduce time (ms)
AllReduce time (ms)
450
700 600 500 400 300 200
2000
1.2
(b) Varying N (message size).
1.6
2.0
2.4
Slowdown factor
2.8
(c) Varying ℓ (ℓ1 =ℓ2 ).
Figure 21: Multi-straggler AllReduce (m=2) at N =8 GiB. OptCC vs. NCCLNoFailure (no failure). (a) ℓ1 =1.5, ℓ2 =2, N =8 GiB; (b) p=64, ℓ1 =1.5, ℓ2 =2; (c) p=64, N =8 GiB, ℓ1 =ℓ2 .
g=8, =2, N=8 GiB
40 35 30 25 20 200
400
600
Number of GPUs p
800
(a) Varying p (GPUs).
1000
80
AllReduce time (ms)
AllReduce time (ms)
AllReduce time (ms)
45
g=8, p=512, N=8 GiB
g=8, =2, p=128
100
50
80 60 40 20 0
400
800
1200
1600
Message size N (GiB)
2000
(b) Varying N (message size).
70 60 50 40 30 20
1.2
1.6
2.0
2.4
Slowdown factor
2.8
(c) Varying ℓ (slowdown).
Figure 22: Multi-GPU-per-server AllReduce (g=8) at N =8 GiB. OptCC vs. ICCL, NCCLNoFailure , and R2 CCL. (a) ℓ=2, N =8 GiB; (b) p=64, ℓ=2; (c) p=64, N =8 GiB.
32