Chapter Summary

Chapter Summary

Key Points

• 1.

  Data shuffling is an information-theoretic coding problem. SGD convergence theory requires random reshuffling of data across epochs; in distributed training, this induces a per-epoch communication cost that matches or exceeds the gradient-aggregation cost. The problem is formalized in §7.2 with the placement-delivery structure of coded caching.

• 2.

  Optimal shuffling rate is $R^*(M) = N(1-\\mu)/(1+N\\mu)$, achieved by the Wan / Tuninetti / Caire CommIT-group contribution. The construction uses finite-field interference alignment (Chapter 4) in the delivery phase, XOR-combining per-subset demands into single broadcasts. Each unit of per-worker memory reduces communication by factor $1 + N\\mu$.

• 3.

  Achievability matches the cut-set converse. Both the upper bound (construction) and the lower bound (cut-set argument) give $R^* = N(1-\\mu)/(1+N\\mu)$, closing the rate region of the data-shuffling problem.

• 4.

  The framework extends to decentralized placement, demand privacy, and heterogeneous memory. Decentralized placement (random caching without coordination) is asymptotically optimal. Demand privacy adds a ramp-secret-sharing layer at a quantified rate penalty. Heterogeneous memory is the open direction.

• 5.

  Demand privacy is the bridge to PIR. The demand-private shuffling rate $R_{\\text{priv}} = N(1-\\mu)/(1+N\\mu-T)$ quantifies the cost of hiding workers' demands from $T$ colluders. This is the algebraic predecessor of the PIR capacity formula that Chapter 13 develops in full.