Exercises

$L(1) = 1 \cdot (1 - 1/K) = 1 - 1/K$. Matches uncoded: each worker broadcasts $(K-1)/K$ to peers per key.

$L(K) = (1/K)(1 - 1) = 0$. Full replication eliminates shuffle — each worker has everything.

$\binom{K}{r}$ file batches, each requiring separate map function invocation. For $K = 100$, $r = 10$: $\binom{100}{10} \approx 1.7 \times 10^{13}$.

Partition overhead dominates. LMYA works well for small $r$ (2-5); large $r$ infeasible. PDA-like reductions (Ch 14) can mitigate for coded MapReduce but require active research.

Uncoded: $T_\text{unc} = T_m + T_s + T_r$. Coded: $T_c(r) = rT_m + T_s/r + T_r$.

Speedup $\iff T_c < T_\text{unc} \iff (r-1)T_m < (1 - 1/r)T_s$.

Factor out $(r - 1)$: $r \cdot T_m < T_s$ $\iff r < T_s / T_m$. Coded MapReduce wins when replication doesn't exceed the shuffle-to-map time ratio.

Differentiate: $r^* = \sqrt{T_s / T_m}$. Balances map and shuffle exactly.

$s + 1 = 5$: each data partition stored at 5 of 20 workers.

Total storage = $K \cdot (s+1)/K = s + 1 = 5$ times the uncoded total. 5× overhead for 4-straggler tolerance.

$(K, k)$-MDS: any $k$ of $K$ coded symbols determine all $K$. Equivalently: tolerate any $K - k$ erasures.

Polynomial encoding: $\mathbf{P}(x_j) \mathbf{B}$ for $j = 1, \ldots, K$. Any $k$ evaluations uniquely determine $\mathbf{P}(\cdot) \mathbf{B}$ — same as $(K, k)$-MDS.

Stragglers = erasures. MDS tolerates $K - k$ erasures, so coded matmul tolerates $K - k$ stragglers.

$L(5)/L(1) = (1/5)(1 - 5/500)/(1 - 1/500) \approx (0.198)/0.998 \approx 0.199 \approx 5\times$ reduction.

Each file mapped at 5 workers — 5× CPU time.

Net benefit only if $T_\text{shuffle} > 5 T_\text{map}$.

For subset $\mathcal{T} \subseteq [K]$ of $t$ workers, they need values from files mapped by workers in $\mathcal{T}^c$. With computation load $r$, the fraction of "new" values (not already at $\mathcal{T}$) is $(K - r)/K \cdot (K-r-1)/(K-1)\cdots$

After averaging over all $t$, total shuffle load $\geq (1/r)(1 - r/K)$. Matches LMYA achievable.

LMYA's scheme exactly achieves the lower bound for integer $r$. For non-integer $r$, time-sharing closes the gap.

Data $D_k$ stored at workers $k, k+1, k+2 \pmod 5$.

$B = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix}$ (rows = workers, columns = data partitions). Each column has 3 ones (data at 3 workers).

Any 3 rows span the all-ones vector $\Leftrightarrow$ can reconstruct $\sum_i \nabla f_i$. Verified by checking all $\binom{5}{3} = 10$ selections.

Coded shuffling: ML training pipeline, regular epochs. Coded MapReduce: batch analytics jobs, one-shot processing.

Both yield $(1 + Kt)$ or $r$-factor reduction in communication via MAN-style coding.

In hybrid pipelines (feature engineering + training): apply coded MapReduce for feature computation, coded shuffling for training data epoch shuffling. Distinct layers, both using coded caching principles.

Batches $B_{\{1,2\}}, B_{\{1,3\}}, \ldots, B_{\{5,6\}}$ — 15 total. Worker $k$ holds $B_\mathcal{S}$ iff $k \in \mathcal{S}$.

Number of 3-subsets: $\binom{6}{3} = 20$. Each message is an XOR of 3 intermediate-value chunks.

from itertools import combinations
K = 6; r = 2
shuffle_msgs = []
for subset in combinations(range(K), r+1):
    xor = sum(V[subset - {k}][q_k] for k in subset)
    shuffle_msgs.append(xor)
# Uncoded: K choose (K-1) = K(K-1) messages, not XORed

Any $k$-of-$K$ MDS code tolerates the worst-case $(K-k)$ erasures. Reed-Solomon is canonical MDS over large enough field.

LDPC/Polar codes offer better computation at high redundancy but complicate decoding. For matmul, the encoding overhead and decoder complexity of RS are typically acceptable; fancier codes are used for bandwidth-critical regimes.

Tandon et al.: $K$ workers, each with IID data of equal size. Encoding matrix weights data symmetrically.

Non-IID: client $k$'s data is different. Weighted gradient $\sum_k w_k \nabla f_k$ with $w_k$ reflecting data size.

Extend encoding matrix to handle weighted sums. Encoding matrix $B$ satisfies: any $K - s$ rows span $\mathbf{w}^T$ (weight vector), not $\mathbf{1}^T$. Requires modified RS-like construction.

LMYA file batch at $r$-subset = MAN file subfile at $t$-subset. LMYA $(r+1)$-subset XOR = MAN $(t+1)$-subset XOR. Identical combinatorics.

"Cache" in LMYA = redundant computation capacity. A worker computing at higher redundancy has "more cache". This insight made coded caching portable to new domains.

Unified theory: one combinatorial toolkit serves many problems. Advances in one translate to others — e.g., PDA subpacketization (Ch 14) informs coded MapReduce design.

• Shuffle bytes per job. Direct verification of $L(r)$.
• Wallclock per job. End-to-end validation.
• CPU-hours for map phase. Verify $r\times$ overhead.
• Network utilization during shuffle. Saturation behavior.
• p99 latency tail. Straggler effects.

Compare coded MapReduce (research prototype) vs uncoded (production Spark) on identical workloads. Control for data locality and network topology.

Shuffle volume matches $(1/r)(1 - r/K)$ within 5%. Wallclock reduction depends on shuffle/map ratio. Network utilization peaks reduced (less burstiness).

All four: $\binom{K}{t+1}$ or $\binom{K}{r+1}$ messages. Scales exponentially in $K$ for fixed gain. PDA reduction works for caching; open for LMYA, shuffling, gradient coding.

All four assume large file/block size for coding to work. Finite-blocklength effects (small files) undercuts gains. Open research.

All four have privacy variants (Wan-Caire privacy, private FL, etc). Open: unified privacy-rate tradeoff across all four primitives.