Straggler-Aware Scheduler for Distributed Training

In synchronous data-parallel training every worker waits at the all-reduce barrier, so an iteration takes as long as the slowest flow takes:

T_iter = max_{i ∈ [1,N]} T_flow_i

That makes per-flow fairness the wrong objective. DCTCP and TIMELY both work to give every flow its share, and here speeding up a worker that is going to sit at the barrier anyway buys exactly nothing. The bandwidth should go to whoever is holding everyone up. 6.5820 final project, with Joseph Ye.

Detecting a straggler without chasing noise

The naive version of this oscillates. A worker hits a microburst, the scheduler hands it bandwidth, the burst passes, the scheduler takes it back, and the cost of thrashing exceeds whatever the reallocation saved. So detection is filtered by persistence:

streak_i = streak_i + 1 if T_i > 1.2 × T_med else 0
confirmed_straggler = (streak_i ≥ 3)

Three consecutive slow iterations before anything moves. The threshold is relative to the median, so it tracks background load instead of needing a tuned absolute number, though that also means a uniformly slow cluster looks fine to it.

Moving bandwidth

r'_i = r_i × (1 + 0.3) if straggler else r_i × (1 - 0.15 × |S|/(N-|S|))

The adjustment is deliberately asymmetric: help the straggler hard (α=0.3), take from donors gently (β=0.15). Since only the max matters, α > 2β is what actually reduces T_iter.

Recovery is slower than punishment, r_{t+1} = 0.5 × r_t + 0.5 × r_base, so rates ease back rather than snapping and starting the cycle again, and a 5-iteration cooldown after each reallocation stops the controller from acting on its own last move.

Implementation

Ring all-reduce is written by hand rather than calling torch.distributed.all_reduce. That is the entire reason: the two-phase scatter-reduce and all-gather loop over point-to-point send/recv gives a per-send hook where a delay can be injected and per-worker timing can be read out. The stock collective is a black box with nowhere to hang that.

The network is simulated, delay_i = d_base / r_i as a blocking sleep. This tests the control logic, not a transport: no real incast, no queueing, no drops. Four delay profiles: uniform (all 10ms), straggler (one worker 3x, persistent), variable (per-iteration Gaussian), bursty (5x at 20% probability).

The workload is deliberately small: a 3-layer MLP of 201,482 parameters on synthetic data, 5 runs of 250 iterations per configuration, 1,240 reported after warmup, N=4 workers. What is being measured is communication scheduling under injected delay, so the model only has to produce gradient tensors of a realistic size. The repo has ResNet-18 and real CIFAR-10 loading wired up and the experiment runner never uses them, which is worth knowing before reading the numbers as a vision result.

Results

| Profile | Baseline | Ours | Change | |---------|----------|------|--------| | Straggler | 1298ms | 717ms | 44.8% faster | | Variable | 268ms | 268ms | under 1% | | Bursty | 747ms | 750ms | under 1% |

Welch's t-test gives p < 0.0001 on the straggler improvement. The distribution moves, not just the mean: median 1314ms to 708ms (46%), p99 1365ms to 1001ms (27%).

The variable row deserves a caveat rather than a victory lap: it fired zero reallocations across all five runs, so it shows the persistence filter correctly declining to act, not the controller handling variance well.

The persistence threshold K is the parameter I would most want a real sweep on. The argument for K=3 is that instant reaction under bursty delay should thrash, reallocating on noise and paying the cost without the benefit, and that is why the filter exists. But the K sweep is defined in the experiment runner and was never actually run, so I am not going to quote numbers for it. That is the next thing to measure.

What it does not do

The network is a sleep, not congestion, so nothing here is validated against real ECN or RTT signals or real queue buildup. It runs as processes on one machine, not nodes on a cluster. Detection is relative to the median, so a uniformly slow cluster is invisible to it. And it cannot tell a compute straggler from a network straggler, which matters because the right response differs: you can give a slow link more bandwidth, and you cannot do anything for a worker whose GPU is throttling.

Code, including the results JSON every number above comes from.