Chapter Summary

Chapter Summary

Key Points

• 1.

  The MAN scheme is a two-phase coded caching strategy. Placement (off-peak) splits each file into $\binom{K}{t}$ equal-sized subfiles $W_{n,\mathcal{S}}$, with $\mathcal{S}$ ranging over $t$-subsets of $[K]$; user $k$ caches exactly those subfiles whose index set contains $k$. Delivery (peak) sends one XOR message per $(t+1)$-subset of $[K]$: $X_{\mathcal{S}'} = \bigoplus_{k \in \mathcal{S}'} W_{d_k, \mathcal{S}' \setminus \{k\}}$.

• 2.

  Each coded message simultaneously serves $t + 1$ users. For every $k \in \mathcal{S}'$, all summands except $W_{d_k, \mathcal{S}' \setminus \{k\}}$ are already in user $k$'s cache, so XOR cancellation recovers the missing subfile. This is the coded multicasting gain, $1 + t$.

• 3.

  Memory-load theorem: For integer $t = K M/N$, the MAN worst-case delivery rate is $$R_{\text{MAN}} \;=\; \frac{K - t}{t + 1} \;=\; K \frac{1 - M/N}{1 + K M/N}.$$ The gain over uncoded caching is exactly $1 + t$ — multiplicative in the aggregate cache size.

• 4.

  The rate formula has two factors: a local caching gain $(1-M/N)$ and a coded multicasting gain $(1+KM/N)^{-1}$. The local gain is captured by any caching scheme; the coded gain is unique to schemes with combinatorial placement and XOR delivery. As $K \to \infty$ at fixed $M/N$, the coded gain is unbounded while the local gain saturates.

• 5.

  Memory sharing extends the scheme to non-integer $t$. The lower convex envelope of the $K+1$ integer-$t$ operating points is achievable by time-sharing two adjacent points with weight $\alpha$. The achievable region is piecewise-linear.

• 6.

  Subpacketization $F = \binom{K}{t}$ is the practical bottleneck. For $K = 50$, $t = 10$, we need $\sim 10^{10}$ subfiles per file — infeasible. Chapter 14 develops polynomial-subpacketization schemes (PDAs, graph coloring) that approach the MAN gain without the exponential overhead.

• 7.

  The MAN scheme is demand-agnostic. Placement is fixed once (independent of future demands); delivery adapts to the demand vector $\mathbf{d}$ via the summands of each $X_{\mathcal{S}'}$. The worst-case rate bound holds uniformly over all $\mathbf{d} \in [N]^K$.