Chapter 2: Information-Theoretic Formulation

Learning Objectives

• Formulate distributed computation as a network information theory problem with workers as encoders and a master as a decoder
• Define the fundamental quantities: computation load $\mu$, communication load $\Delta$, storage, recovery threshold $K$
• State and interpret the computation–communication tradeoff $\Delta(\mu) = (1-\mu)/(N\mu)$ achievable by coded shuffling
• Prove a cut-set-style converse showing that uncoded schemes are a factor of $N\mu$ worse than optimal
• Recognize how this formal framework generalizes to secure aggregation (Part III), PIR (Part IV), and AirComp (Part V)