Measured-Topology Coded Shuffling: Letting the Network Choose the Multicast Groups

Coded multicasting can make the data-exchange step of distributed jobs several times faster. In that step, often called the shuffle, every machine must send intermediate results to every other machine. The trick is to compute each piece of input on several machines, so that each machine already holds some of what its peers need. A sender can then transmit one XOR of several blocks, and each receiver cancels out the part it already has. Theory says that computing everything on $r$ machines cuts shuffle traffic by about a factor of $r$. That result assumes a network in which sending one packet to a group costs the same as sending it to one machine, and in which every link is equally fast. Commodity clouds offer neither. Native multicast is usually unavailable and is emulated with unicast copies or relay trees. Bandwidth also varies with hidden host placement and switch oversubscription. Most heterogeneous coded-computing results are checked only in simulators that assume all of this away.

This note proposes a cheap measurement step before each job. The system probes the real cloud cluster to see which machines can share transmissions cheaply. A clustering method that needs no tuning, the Mutex Watershed, then groups the machines from these noisy probe results without anyone choosing the number of groups. Coded multicast groups are built only inside the discovered groups, and plain unicast is used across them. Two benefits are expected. First, coding effort goes where the network rewards it. Second, the step that enumerates multicast groups, which grows combinatorially with cluster size, shrinks to the size of the discovered groups. The headline evaluation compares simulator predictions against wall-clock results on real cloud instances, with the gap between them as one of the things measured.

Core Claim

The benefit of coded shuffling on a real cloud is set by the measured cost of one-to-many transmission between specific machines, not by the redundancy factor alone. That cost has structure that can be discovered cheaply and without hyperparameters. A coded shuffle restricted to measured groups should therefore match or beat global coded shuffling in wall-clock time on unthrottled, heterogeneous clusters, while generating coding plans much faster. It should also beat the strongest uncoded topology-aware shuffle once the network is the bottleneck. The claim can be tested and could fail in either direction. If randomly chosen groups of the same sizes perform as well as measured ones, the topology discovery adds nothing.

Where This Sits in Prior Work

The coding mechanism is reused from Coded TeraSort. That paper places each input on $r$ machines and broadcasts XORed packets within multicast groups, and it shows real speedups on Amazon EC2. It also documents the two costs we target. Its group-generation phase, which it calls CodeGen, scales combinatorially with cluster size $K$ and redundancy $r$, and decoding needs extra memory. Its experiments throttled every node to 100 Mbps. That setting makes the network artificially uniform, which is exactly the regime where topology does not matter. The tradeoff analysis in A Unified Coding Framework for Distributed Computing with Straggling Servers supplies the theory we start from, and its i.i.d. server-runtime model is one of the assumptions we test against measurement.

Three lines of work motivate the gap. On Heterogeneous Coded Distributed Computing handles unequal storage across machines with a linear program over $2^K$ variables, which is intractable for large $K$, and it uses synthetic parameters only. Design and Optimization of Heterogeneous Coded Distributed Computing With Nonuniform File Popularity handles unequal message sizes, but through a static two-tier grouping fixed in advance. Speeding Up Distributed Machine Learning Using Codes shows on EC2 that the real multicast cost ratio $\gamma(n)$ and long-tailed latency depart from idealized models. In all three, heterogeneity is a given input rather than something measured. We measure it and let it decide the code structure.

The closest structural relative is Gradient Coding with Clustering and Multi-Message Communication. It also confines coding to groups of workers, but its groups are fixed in advance and of equal size, it targets stragglers rather than shuffle bandwidth, and it is evaluated only in Monte Carlo simulation with shifted-exponential runtimes. We replace hand-picked groups with groups discovered from measurements, apply them to multicast shuffling, and validate on hardware.

The grouping method comes from The Mutex Watershed. It sorts attractive and repulsive edges by strength and merges greedily, refusing any merge across a repulsive ("mutex") edge. The number of groups emerges without seeds or thresholds, in $O(|E|\log|E|)$ time. That paper reports good segmentation even when 60% of affinities are replaced with noise. This robustness is why we use it on network probes, which are noisy. We have not seen it applied outside image or graph segmentation. Its documented weakness is sensitivity to poorly calibrated affinities, and that weakness is the main technical risk here.

The reality-gap concern is grounded in TFR-LRC. Its authors state that simulations assuming uniform cross-rack bandwidth miss TCP dynamics and hardware interactions, and they leave testbed validation to future work. We treat the size of the simulator-versus-hardware gap as a measured outcome, not a caveat.

Research Program

The system has three stages that run before each shuffle.

The probing stage runs pairwise transfers between machines. These are scheduled in $K-1$ rounds of $K/2$ disjoint pairs, so each round takes seconds. Each probe records sustained throughput. A smaller sample of group probes records slowdown when one sender emulates a multicast to several receivers at once, and when two pairs transfer at the same time. Machine pairs that keep high throughput under concurrent load get attractive edges, weighted by that throughput. Pairs whose concurrent transfers slow each other, a sign of a shared oversubscribed link, get repulsive edges weighted by the slowdown.

The grouping stage runs the Mutex Watershed on this signed graph, which yields machine groups $G_1,\dots,G_m$. Group sizes are not forced to be equal, and nobody sets $m$. Groups smaller than three machines fall back to uncoded transfer.

The planning stage places input files with redundancy $r_j$ inside each group $G_j$, and builds coded multicast groups only among members of $G_j$. Data headed across groups is sent uncoded after local combining, in the manner of Compressed Coded Distributed Computing. The per-group redundancy $r_j$ is chosen from a small integer range by minimizing a predicted shuffle time. That prediction uses the measured multicast costs, not the theoretical unit cost. The choice is made from measurements, not tuned by rerunning jobs. Group generation now costs on the order of $\sum_j \binom{|G_j|}{r_j+1}$ instead of $\binom{K}{r+1}$, so plan generation should shrink sharply whenever the groups are much smaller than $K$.

The program also includes an analysis component. For each configuration, we feed a shifted-exponential, uniform-bandwidth simulator of the kind used in Gradient Coding with Clustering and On Heterogeneous Coded Distributed Computing the same parameters. We then report how far its predicted speedups and its ranking of schemes depart from wall-clock results.

Baselines

The naive reference point is uncoded TeraSort with standard all-to-all unicast shuffling. It is run on the same instances, data, and network settings. All speedups are reported relative to it.

The strongest existing method is global Coded TeraSort as described in Coded TeraSort. It forms multicast groups over all $K$ machines with a single redundancy $r$. That paper reports end-to-end speedups of 1.97x to 3.39x over uncoded TeraSort on 16 and 20 EC2 nodes throttled to 100 Mbps, on 12 GB of TeraGen data. In its 16-node, $r=5$ setting, shuffle time fell from 945.7 seconds to 222.8 seconds. We will first reproduce this throttled setting to confirm that our implementation matches those numbers. Then, under every other condition, global Coded TeraSort gets the same search over $r$ that our method uses. To beat it, our method must give lower end-to-end time, counting probing and plan generation, on unthrottled or heterogeneous clusters. Separately, it must cut plan-generation time at $K \ge 32$. In the uniform throttled setting it should only tie, and a tie there is the expected result.

The key ablation keeps everything in our pipeline but replaces the measured groups with random groups of the same sizes. A second ablation replaces them with fixed equal-size groups, as in Gradient Coding with Clustering. Together these isolate whether measured topology matters, or whether all the gain comes from smaller groups that make plans cheap.

A strong uncoded competitor schedules shuffle transfers from the same probe data to avoid contended pairs, and applies local combining. This tests whether measurement alone, without coding, captures the benefit.

For the grouping step, we compare against k-means on probe vectors with the number of groups picked by BIC-style splitting, as in txmeans. Where the cloud exposes placement information, we also compare against oracle groups built from it.

Why not just…?

Why not just run global Coded TeraSort and pick the best $r$? On a uniform, throttled network this is probably optimal, and we expect our method to tie there. Global groups force every multicast to span machines whose actual group-transfer cost may be high. Coded TeraSort itself reports that plan generation and decoding memory grow combinatorially with $K$ and $r$. Comparing the two at $K = 16, 32, 64$, unthrottled and with induced per-node bandwidth heterogeneity, will show whether these costs dominate at realistic sizes.

Why not just schedule uncoded transfers around the measured topology and skip coding? This is the real threat. If most of the shuffle penalty comes from contention rather than total bytes, smart uncoded scheduling may capture it. Coded TeraSort shows coding helps when the network is the bottleneck. Locality-only methods such as RBBD and WSCS also report more modest gains, a 36.37% average transfer reduction and up to 20% runtime improvement, and they act on input placement rather than the intermediate shuffle. Still, neither result was obtained on a heterogeneous unthrottled cluster. The uncoded topology-aware baseline is in the main comparison for exactly this reason. If it matches our method, we will report that coding adds nothing once topology is accounted for.

Why not just use the cloud's placement metadata or k-means with a tuned group count? If reliable placement labels exist, they should be used, and the oracle comparison measures what is lost without them. Labels do not capture time-varying contention. Tuning a group count requires repeated full shuffles, each of which costs as much as the job itself. The k-means-with-BIC comparison tests whether the Mutex Watershed's handling of repulsive edges matters on noisy probes. If it does not matter, the simpler method wins.

Why not just validate in simulation? We will run the simulator, and its prediction error is a result we report. Speeding Up Distributed Machine Learning Using Codes already found long-tailed latency and multicast cost penalties on EC2 that idealized models miss. TFR-LRC concedes the same gap for storage codes.

Proposed Experiments

The primary workload is TeraSort on TeraGen data, matching Coded TeraSort. The secondary workload is random-reshuffle data shuffling for distributed gradient descent, as in Speeding Up Distributed Machine Learning Using Codes. That paper reports that coded shuffling cuts communication by over 80% even with small caches, and that coded gradient descent runs 31% to 35% faster than uncoded on EC2. We run both on EC2 at $K = 16, 20, 32, 64$, under four network conditions. The first is the 100 Mbps uniform throttle, as a reproduction check. The second is unthrottled. The third throttles a random subset of nodes to induce heterogeneity. The fourth spreads instances across placement settings so that the hidden topology varies.

Metrics are end-to-end time broken into probing, plan generation, map, shuffle, and decode. We also record bytes on the wire and peak memory per node. For grouping quality, we report agreement with placement labels where they are available, and how stable the groups are across repeated probes.

Three checks settle the main questions. The first is whether measured groups beat random equal-size groups in shuffle time under the heterogeneous condition. If they do not, the topology claim fails. The second is whether our method beats both global Coded TeraSort and uncoded topology-aware scheduling end to end, including probing overhead. The third is how far the shifted-exponential simulator's predicted speedups and scheme rankings depart from measured ones. If the simulator ranks the schemes correctly, the reality-gap motivation weakens, and we will report that plainly.