Prerequisites & Notation

Before You Begin

Chapter 2 re-expresses the three challenges of Chapter 1 in the formal language of network information theory. The mathematical prerequisites are modest but concrete — most notably entropy, mutual information, and conditional entropy for discrete sources. Readers who are fluent with Book ITA Chapters 1–3 can proceed directly; others may want to refresh before tackling Section 2.3's converse argument.

Entropy, joint entropy, conditional entropy(Review ch01)
Self-check: Can you write the chain rule $H(X, Y) = H(X) + H(Y \mid X)$ ?
Mutual information $I(X;Y) = H(X) - H(X \mid Y)$ (Review ch01)
Self-check: Why is $I(X;Y) \geq 0$ ?
Data processing inequality(Review ch01)
Self-check: For $X \to Y \to Z$ , why does $I(X; Z) \leq I(X; Y)$ ?
Cut-set bound for multi-terminal networks(Review ch21)
Self-check: Can you state the cut-set bound for a three-node relay network?
Chapter 1 of this book — MapReduce, stragglers, distributed SGD(Review ch01)
Self-check: Can you state the computation load $\mu$ and communication load $\Delta$ informally?

Notation for This Chapter

Chapter 2 is where we formalize the information-theoretic objects that will reappear throughout the book. Keep this table close while reading Sections 2.2–2.4.

Symbol	Meaning	Introduced
$\mathcal{D}$	Input dataset as a random variable (uniform over its support)	s01
$\mathcal{D}_k$	Portion of $\mathcal{D}$ stored at worker $k$	s01
$N$	Number of workers	s01
$Y$	Output of the distributed computation (scalar or vector)	s01
$X_k$	Message transmitted by worker $k$ (output of its local encoder)	s01
$\mu$	Normalized per-worker storage: $\|\mathcal{D}_k\|/\|\mathcal{D}\|$	s02
$\Delta$	Normalized total communication load (bits / intermediate-file size)	s02
$K$	Recovery threshold: any $K$ responses suffice	s02
$R_{\text{comp}}$ , $R_{\text{comm}}$	Computation and communication rates (bits per input sample)	s02
$H(\cdot)$	Shannon entropy	s03
$I(\cdot;\cdot)$	Mutual information	s03

← Ch 1 Workers as Encoders, Master as Decoder