Chapter Summary

Chapter Summary

Key Points

• 1.

  Distributed computing is a network information theory problem. Workers become per-node encoders, the master becomes a joint decoder, and the dataset becomes a source. The rate region is determined by three fundamental quantities: storage load $\mu$, communication load $\Delta$, and recovery threshold $K$.

• 2.

  The cut-set bound is the structural converse. For any scheme, the aggregate message entropy across a cut must exceed the conditional entropy of the output given the storage on the other side: $H(X_{\mathcal{S}}) \geq H(Y \mid X_{\mathcal{S}^c})$. Every converse in the rest of the book is a specialization of this recipe.

• 3.

  The computation–communication tradeoff is tight at $\Delta^*(\mu) = (1-\mu)/(N\mu)$. Coded shuffling achieves this curve (XOR-combined broadcasts among overlapping storage groups); a cut-set argument matches it from below. Each unit of additional per-worker storage reduces the communication load by a factor of $N\mu$.

• 4.

  Uncoded schemes live strictly inside the achievable region. The uncoded operating point $(\mu, \Delta) = (1/N, 1 - 1/N)$ lies above the tradeoff curve by a factor of $N\mu$ in load — a quantifiable cost paid for running without coded redundancy.

• 5.

  The framework generalizes. Privacy (Part III), PIR (Part IV), and wireless aggregation (Part V) each add one dimension to the rate region, but all use the same cut-set converse recipe. The four-step template — cut, entropy bound, symmetrize, normalize — is the common language of every information-theoretic result in this book.