Exercises

$t = 30 \cdot 0.2 = 6$. $F = \binom{30}{6} = 593{,}775 \approx 6 \times 10^5$. Feasible for 1 GB files (each subfile = ~2 KB).

$F \approx 100^3/3! \approx 1.67 \times 10^5$. Compare MAN: $\binom{100}{3} = 1.62 \times 10^5$. Here similar — but at larger $K$, PDA grows polynomially while MAN explodes.

Each subfile must be at least a few KB (header overhead). For a 1 GB file: max $F \approx 10^6$. Beyond this, subfiles are sub-bit and the scheme breaks. MAN's exponential $F$ caps $K$ at ~50. Polynomial-$F$ schemes remove this cap.

Achievable: $F = O(K^2)$ with rate $\leq 2 R_{\text{MAN}}$ in practical regimes. Polynomial subpacketization; constant-factor rate gap. CommIT result.

A $(K, F, Z, S)$-PDA is a $F \times K$ integer/star matrix where:

• $K$ = number of users (columns).
• $F$ = subpacketization (rows).
• $Z$ = number of $*$ per column (= files cached per user).
• $S$ = number of distinct non-$*$ symbols (= coded messages). Rate: $S/F$ file units.

$F = 6$. Rows: 2-subsets of $[4]$: $\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}$. Users: 1-4.

Entry $p_{\mathcal{S}, k} = *$ iff $k \in \mathcal{S}$. Row $\{1,2\}$: $*, *, ., .$ (columns 1, 2 starred). Row $\{1,3\}$: $*, ., *, .$ etc.

For $(t+1) = 3$-subsets $\mathcal{S}'$: define coded message. $\{1,2,3\}$: message 1. $p_{\{1,2\}, 3} = 1$, $p_{\{1,3\}, 2} = 1$, $p_{\{2,3\}, 1} = 1$. Similarly for $\{1,2,4\}, \{1,3,4\}, \{2,3,4\}$: messages 2, 3, 4. $S = 4$ messages.

$R = S/F = 4/6 = 2/3$. Matches MAN: $(K-t)/(t+1) = 2/3$. ✓

$S/F = (K^{t+1}/(t+1)!) / (K^t/t!) = K t! / ((t+1)!) = K/(t+1)$. Hmm, this is $K/(t+1)$, slightly larger than MAN's $(K-t)/(t+1)$. Gap $= t/(t+1)$.

For small $t$: gap $\approx 0$. For large $t$: gap approaches 1 — polynomial PDA loses factor $t/(t+1)$. Still: polynomial $F$ vs exponential MAN.

$K h_b(0.1) \leq 16.6$. $h_b(0.1) \approx 0.47$. $K \leq 35$.

$K^t/t! \leq 10^5$, $t = 0.1 K$. For $t = 3, K = 30$: $\binom{30}{3}/3! \approx 4{,}060/6 \approx 676$. Huge headroom. For $t = 6, K = 60$: $60^6/6! \approx 6.5 \times 10^7 > 10^5$. Crossover around $K \approx 50$.

$F = K^2 \leq 10^5 \Rightarrow K \leq 316$. By far the most scalable.

Under this budget: MAN $K \leq 35$. PDA $K \leq 50$. Graph-coloring $K \leq 316$. For large $K$ deployments, graph-coloring is the only option.

Fewer subfiles $\Rightarrow$ less cached diversity $\Rightarrow$ more messages needed per delivery round. Exact tradeoff depends on PDA structure.

For any $(K, F, Z, S)$-PDA: $S \geq F \cdot (K - KZ/F)/(KZ/F + 1)$ via MAN-like converse. Halving $F$ roughly requires 1-2× increase in $S$.

PDAs that halve $F$ typically lose ~10-30% in rate. The CommIT graph-coloring schemes achieve $F = O(K^2)$ with ~2× rate — a substantial reduction in $F$ at moderate rate cost.

$R_\text{dec}/K = (0.75/0.25)(1 - 0.75^{20}) = 3 \cdot (1 - 0.00317) \approx 2.99$. Per-user: 2.99/20 = 0.15. Centralized MAN at $t = 5$: $R_\text{cent} = 20 \cdot 0.75/6 = 2.5$. Per-user: 0.125.

Decentralized slightly higher rate (small gap at finite $K$). Gap vanishes as $K \to \infty$; both → $(1-\mu)/\mu = 3$.

MAN rate: $(K-t)/(t+1)$. Corresponds to specific PDA with $F = \binom{K}{t}$ (exponential).

Kaji-Caire 2020: any PDA with rate $(K-t)/(t+1)$ has $F \geq \Omega(\binom{K}{t})$. Polynomial $F$ is impossible for exact MAN rate.

Relaxing rate to $c (K-t)/(t+1)$ for $c > 1$ allows polynomial $F$. Factor 2: $F = O(K^2)$ (graph-coloring).

Exact constant $c^*$ for $F = O(K^2)$ is open. Conjectured $c^* \to 1$ as $K \to \infty$.

Formulate as an integer programming: minimize $F$ subject to PDA constraints. NP-hard in general.

Start with MAN; iteratively merge rows that can be combined without violating constraints. Each merge reduces $F$ by 1. Greedy: prefer merges that don't increase $S$.

$O(F^2)$ merge candidates; $O(F^2 K)$ constraint checks per merge. Feasible for $F < 10^3$. For larger, use LP relaxation or structured constructions.

Automated PDA design is active research. CommIT group uses structured designs (Latin squares, resolvable) — more reliable than heuristic search.

Subfile split: each user retains bits it had; simple. Subfile merge: users may have inconsistent content; requires retransmission or re-placement.

Splitting: negligible bandwidth; useful for fine-grained scheduling. Merging: can be expensive; requires agreement across users.

Adaptive PDAs that evolve with network dynamics are a research frontier. CommIT work on online coded caching (Chapter 20) touches this.

Network coding within the XOR messages could reduce header overhead. Combined schemes (Shanmugam-Dimakis 2014+) achieve higher effective throughput.

Complexity increases at both decoding (network-code recovery) and placement (coordinating cache + NC). Benefits: marginal at small $K$; larger at $K > 100$.

Combined coded-caching + network-coding is studied in a few papers; active research area with limited deployment.

Apply forward error correction (e.g., Raptor codes) to each XOR message. Users can recover from lost packets via FEC.

FEC adds ~5-10% redundancy. Recovery probability ≥ 99.9% even with 5% loss rate. Acceptable overhead.

5G NR uses Polar/LDPC codes for FEC. Combining with MAN XOR: FEC'd subfiles, XOR over FEC'd versions, recover via decoder ladder. Implementable.

Lossy-channel coded caching is studied; standard 5G techniques apply. Not a fundamental research gap.