Exercises

$R_\text{coded} = 100 \cdot 0.9/(1+10) \cdot 1 \text{ PB} = 90/11 = 8.18 \text{ PB per epoch}$. Uncoded: $90$ PB. Savings: $10\times$.

Cache $M$ ↔ Worker memory $sD$. Files $N$ ↔ Dataset $D$. Memory ratio $M/N$ ↔ Storage fraction $s$. Demand ↔ New assignment. Delivery ↔ Shuffling. Caching gain $1+KM/N$ ↔ Shuffling gain $1+Ks$.

$(r+1)/K = 5/50 = 10\%$. Per-worker storage: 10% of dataset (vs 2% without coding — $1/K$). Storage overhead: 5×.

At large $K$: $K(1-s)/(1+Ks) \to (1-s)/s$ (asymptote). Independent of $K$. Beyond moderate $K$, adding workers doesn't reduce per-worker shuffling cost. Storage fraction $s$ is the dominant lever.

$s = 1$: each worker has the full dataset; no data transfer needed per epoch. $R_\text{coded} = 0$. Formula: $K(1-1)/(1+K) = 0$. ✓

Consider any single worker. At epoch $t+1$, it needs its new assignment $\tilde D_k$ of size $sD$. Of these, $(1-s)$ fraction is new data; the rest was already stored.

Worker must receive at least $sD(1-s) = s(1-s)D$ new data per epoch. Across $K$ workers: $Ks(1-s)D$. After optimizing over the information shared across workers via coded multicasting: achievable rate is $K(1-s)/(1+Ks) \cdot D$.

The MAN-style coded scheme (§15.2) matches this bound asymptotically. $\blacksquare$

$R = p \cdot K(1-s)/(1+Ks) \cdot D$. Linear in $p$; saturating gain structure.

Production ML shuffles $p \sim 10\%$ per epoch (not full). Total cost 10× less than full shuffling. Coding still helps; reduction remains $(1+Ks)$.

$1+Ks = 13.8$. Coded: 36.5/13.8 $\approx$ 2.64 TB per epoch. At 100 Gbps network, 256 workers: shuffling time $\approx 2.64 \times 10^{12} \cdot 8 / (100 \times 10^9 \cdot 256)$ = 0.82 seconds. Uncoded: 11 seconds.

90 epochs. Uncoded: 1000 s = 17 min. Coded: 74 s = 1.2 min. Saved: ~16 min per training run.

For 1000 training runs/year (hyperscale): ~260 hrs of compute cluster time saved per year, on shuffling alone.

Handles straggler tolerance via redundant data / computation. Storage overhead: $(r+1)/K$.

Handles inter-epoch data transfer. Bandwidth reduction: $(1+Ks)$.

Both techniques can coexist: gradient coding for reliability, shuffling for bandwidth. Storage overhead from gradient coding: $s' = s(r+1)$. Shuffling gain: still $(1+Ks')$. Compound gain possible.

Not yet standard in production. Research prototype: Caire- Tuninetti collaborations explore combined schemes.

10 DCs × 10 Gbps = 100 Gbps aggregate cross-DC.

Per-epoch transfer: $K(1-s)D$ = say $100(1-0.1)$ PB = 90 PB. At 100 Gbps: $720{,}000$ seconds = 200 hours per epoch. Infeasible.

Reduce by $1+Ks = 11$: 8.2 PB per epoch. At 100 Gbps: 18 hrs. Still slow; use smaller datasets or longer epochs.

Cross-DC federated training is bottlenecked by bandwidth. Coded shuffling helps but cannot eliminate the constraint. Future 100+ Tbps optical networks needed for full-scale federated training.

Rate: $K(1 - \bar s)/(1 + K \bar s)$ where $\bar s = (1/K) \sum_k s_k$. Aggregate storage determines rate.

Factor-of-2 upper bound on penalty vs homogeneous at $\bar s$ (analogous to Sengupta-Tandon-Clancy 2017 for caches).

Rich workers (more storage) contribute more to coded multicast. Poor workers still receive via XOR.

Each worker's new assignment is independent of its previous assignment and of other workers' assignments. Uniformly random over size-$sD$ subsets.

Under this assumption, per-epoch rate is fixed at $K(1-s)D/(1+Ks)$. No dependence on $T$.

If assignments are correlated (e.g., slow drift), the structure can be exploited for further reduction. Open research area.

$K$ devices, each with local private data. No raw data exchange allowed. Gradient updates exchanged; coded shuffling of model parameters.

Add differential-privacy noise to gradients; use coded shuffling to communicate masked updates efficiently.

Privacy budget + communication cost tradeoff. Rate savings ~$(1+Ks)$ while maintaining DP-$\epsilon$ privacy.

Active CommIT-Tuninetti research; papers 2023-2024 explore combined schemes.

Standard all-reduce: O($2K$) phases of bandwidth, $(K-1)/K \cdot$ total gradient size per phase.

Apply coded aggregation: workers exchange XOR-coded gradient segments. Reduce communication by coded-caching-style gain at cost of computation.

Coded all-reduce is active research; marginal speedups (5- 20%) over NCCL optimized schemes. Not yet standard in PyTorch.

1. Integration with existing frameworks (PyTorch, TF, JAX).
2. Operational complexity (storage overhead, coding logic).
3. Limited measured benefit at typical scales.
4. Engineer familiarity: coded techniques not widely taught.

2024-2025: Open-source implementations of coded shuffling in PyTorch Distributed. Research benchmarks. 2026-2027: Cloud-provider-integrated (AWS, GCP) coded- compute services. 2028+: Standard adoption in hyperscale training.

Widespread adoption hinges on framework integration — researchers know the value; practitioners need turnkey tools.