Exercises

(a) $t = KM/N = 3 \times 2/6 = 1$. (b) Sub-files per file: $\binom{3}{1} = 3$. Each file is split into 3 equal parts. (c) Delivery load: $R = K(1-M/N)/(1+t) = 3(1-1/3)/2 = 2/2 = 1$ file. (d) Coded multicasting gain: $1 + t = 2$. Each transmission serves 2 users.

Files: $A = (A_{\{1\}}, A_{\{2\}}, A_{\{3\}})$, similarly for $B$ and $C$.

• User 1 caches: $A_{\{1\}}, B_{\{1\}}, C_{\{1\}}$ (sub-files containing user 1 in the index).
• User 2 caches: $A_{\{2\}}, B_{\{2\}}, C_{\{2\}}$.
• User 3 caches: $A_{\{3\}}, B_{\{3\}}, C_{\{3\}}$. Cache size: $3 \times F/3 = F = MF$. Correct.

For $\mathcal{S} = \{1,2\}$: send $A_{\{2\}} \oplus B_{\{1\}}$. User 1 has $B_{\{1\}}$, recovers $A_{\{2\}}$. User 2 has $A_{\{2\}}$, recovers $B_{\{1\}}$.

For $\mathcal{S} = \{1,3\}$: send $A_{\{3\}} \oplus C_{\{1\}}$. User 1 recovers $A_{\{3\}}$, User 3 recovers $C_{\{1\}}$.

For $\mathcal{S} = \{2,3\}$: send $B_{\{3\}} \oplus C_{\{2\}}$. User 2 recovers $B_{\{3\}}$, User 3 recovers $C_{\{2\}}$.

Total: 3 messages of size $F/3$ each. Load: $R = 3 \times (1/3) = 1$ file.

The coded multicasting gain is exactly $1 + t$. At $M = 10$ (half the library), the coded scheme serves the entire demand with less than 1 file of transmission.

For each file (N total), user $k$ caches sub-files $W_{n, \mathcal{T}}$ where $k \in \mathcal{T}$ and $|\mathcal{T}| = t$. The number of such $\mathcal{T}$ is $\binom{K-1}{t-1}$ (choose the remaining $t-1$ members from $K-1$ users).

Total cached bits: $N \cdot \binom{K-1}{t-1} \cdot \frac{F}{\binom{K}{t}} = NF \cdot \frac{\binom{K-1}{t-1}}{\binom{K}{t}} = NF \cdot \frac{t}{K} = \frac{tN}{K} \cdot F = MF$. Correct.

$K = 10, t = 3$: $\binom{10}{3} = 120$ sub-files. For 1 GB: each sub-file is $1\text{GB}/120 \approx 8.3$ MB. Feasible.

$K = 20, t = 5$: $\binom{20}{5} = 15{,}504$ sub-files. Each sub-file is $1\text{GB}/15504 \approx 64$ KB. Feasible but the overhead of managing 15,504 sub-files per file is non-trivial.

$K = 50, t = 10$: $\binom{50}{10} \approx 10^{10}$. Each sub-file would be 0.1 bytes — less than one byte! Completely impractical.

$R(t) = (K-t)/(t+1)$. We need $R(t-1) + R(t+1) \ge 2R(t)$: $\frac{K-t+1}{t} + \frac{K-t-1}{t+2} \ge \frac{2(K-t)}{t+1}$.

Cross-multiplying and simplifying (with $a = K-t$): $(a+1)(t+2) + (a-1)t \ge 2a(t+2) \cdot t / (t+1)$. This simplifies to $2a + 2 \ge 2a$, which holds with equality only when the function is affine (it is not). The strict inequality confirms convexity.

For non-integer $t$, split each file into fraction $\alpha$ processed with parameter $t_1 = \lfloor t \rfloor$ and fraction $1-\alpha$ with $t_2 = \lceil t \rceil$, where $\alpha t_2 + (1-\alpha)t_1 = t$. This gives $\alpha = t_2 - t$. The resulting load $\alpha R(t_1) + (1-\alpha)R(t_2)$ traces the line segment between adjacent integer-$t$ points on the convex curve.

$t = KM/N = 9 \times 3/9 = 3$. $L + t = 3 + 3 = 6 < K = 9$. NDT $= K(1-M/N)/(L+t) = 9 \times 2/3 / 6 = 6/6 = 1$.

Total multicast messages: $\binom{9}{4} = 126$. Each slot serves $L = 3$ messages (one per beamforming direction). Time slots: $126/3 = 42$. Each message has size $F/\binom{9}{3} = F/84$. Total delivery: $42 \times 3 \times F/84 = 126F/84 = 3F/2$. NDT: $(3F/2)/(F \times L) = (3/2)/3 = 1/2$... Let me recalculate.

Actually, NDT $= \binom{K}{t+1}/(L\binom{K}{t}) = 126/(3 \times 84) = 126/252 = 1/2$. With the file-size correction: $R = \binom{K}{t+1}/\binom{K}{t} = 126/84 = 3/2$. NDT $= R/L = (3/2)/3 = 1/2$... But using the formula directly: NDT $= K(1-M/N)/(L+t) = 9(2/3)/6 = 1$. The discrepancy arises from the DoF definition. Using the correct formula: NDT $= (K-t)/((t+1)L) = 6/(4 \times 3) = 1/2$.

Per slot: $L = 3$ beamforming vectors, each carrying one multicast message to a group of $t+1 = 4$ users. Each vector is in $\mathbb{C}^3$ and lies in the null space of the channels of users outside its target group.

In the index coding formulation, each demanded sub-file $W_{k, \mathcal{T}}$ (user $k$ wants this, with $k \notin \mathcal{T}$) is a "message." User $k$ has side information $W_{j, \mathcal{T}'}$ for all $j$ and $\mathcal{T}' \ni k$.

For a fixed $\mathcal{S}$ with $|\mathcal{S}| = t+1$, the sub-files $\{W_{k, \mathcal{S}\setminus\{k\}} : k \in \mathcal{S}\}$ form a "clique" in the index coding sense: each is wanted by one user in $\mathcal{S}$ and available as side information to all other users in $\mathcal{S}$. This is precisely the structure that allows the XOR $\bigoplus_{k \in \mathcal{S}} W_{k, \mathcal{S}\setminus\{k\}}$ to simultaneously serve all users in $\mathcal{S}$.

The MAN delivery is a clique cover of the index coding side-information graph. The $\binom{K}{t+1}$ cliques partition all demanded sub-files, and each clique is served by one XOR. This clique cover is optimal for the MAN placement (matching the converse for uncoded placement).

Each user independently includes each bit of each file in its cache with probability $q = M/N$. The expected number of bits user $k$ caches from file $n$ is $qF$, and $|Z_k| = NqF = MF$. Correct in expectation.

For a bit of file $W_{d_k}$ not cached by user $k$ (probability $1-q$), the set of users who do cache this bit has size $\text{Binom}(K-1, q)$. A coded multicast serves all users who need the bit and whose caches differ. The average group size is $1 + (K-1)q \approx 1 + Kq = 1 + KM/N$.

$R_{\text{dec}} = N\binom{K}{t+1}(1-q)^{t+1}q^t / \binom{K}{t}$ after careful accounting, which simplifies to approximately $K(1-M/N)/(1+KM/N)$ for large $F$. The decentralized scheme loses a constant factor compared to centralized MAN (approximately $e \approx 2.72$ for large $K/t$), but has the advantage of requiring no coordination during placement.

$t_{\text{user}} = KM_{\text{user}}/N = 8 \times 2/20 = 0.8$. Effective file fraction not at edge: $1 - M_{\text{edge}}/N = 1 - 5/20 = 0.75$. Effective file fraction not at user: $1 - M_{\text{user}}/N = 0.9$.

NDT $= K(1 - M_{\text{user}}/N - M_{\text{edge}}/N)/(L + t_{\text{user}})$ $= 8(1 - 0.1 - 0.25)/(4 + 0.8) = 8 \times 0.65/4.8 = 5.2/4.8 \approx 1.08$.

Without edge caching: NDT $= 8 \times 0.9/4.8 = 1.5$. Without user caching: NDT $= 8 \times 0.75/4 = 1.5$. Without any caching: NDT $= 8/4 = 2$.

The two caching layers provide complementary gains.

$\binom{K}{t} = \binom{K}{1} = K$ sub-files per file. File $W_n$ is split into $W_{n,\{1\}}, W_{n,\{2\}}, \ldots, W_{n,\{K\}}$, each of size $F/K$.

For each pair $\{i, j\}$ ($\binom{K}{2}$ pairs), send $W_{d_i, \{j\}} \oplus W_{d_j, \{i\}}$. User $i$ has $W_{d_j, \{i\}}$ (cached) and recovers $W_{d_i, \{j\}}$. User $j$ has $W_{d_i, \{j\}}$ (cached) and recovers $W_{d_j, \{i\}}$.

$R = \binom{K}{2} \times F/K / F = \binom{K}{2}/K = (K-1)/2$. Check: $R_{\text{MAN}} = (K-1)/(1+1) = (K-1)/2$. Matches.

$M/N = 5/50 = 0.1$. Per-user throughput: $\Theta(0.1)$ files per slot. Independent of $K = 100$.

Without coding, each D2D transmission serves one user. With spatial reuse, throughput is $\Theta(1/K \times K) = \Theta(1)$ total, so $\Theta(1/K)$ per user. But with uncoded caching, the hit ratio is $M/N = 0.1$, so $T_{\text{uncoded}} = \Theta(M/N \times 1/K_c)$ per cluster, which is worse.

With $K_c = 10$ users per cluster: $t_c = K_c M/N = 10 \times 0.1 = 1$. Coded multicasting gain: $1 + t_c = 2$. Per-user throughput within cluster: $\Theta(M/N) = \Theta(0.1)$ (same scaling, but with a smaller constant than the global scheme). Subpacketization: $\binom{10}{1} = 10$ (very manageable).

The delivery message $X$ of size $RF$ must enable every user to decode. For any ordering of users: $H(W_1, \ldots, W_K | X, Z_1, \ldots, Z_K) = 0$ (all files decodable).

By the chain rule: $H(X) \ge H(X | Z_1, \ldots, Z_K) \ge \sum_k H(W_k | X, Z_k, W_1, \ldots, W_{k-1})$.

But $H(W_k | X, Z_k, W_1, \ldots, W_{k-1}) = 0$ (user $k$ decodes from $X$ and $Z_k$, plus the "genie" information $W_1, \ldots, W_{k-1}$). So we need the reverse direction.

$RF = H(X) \ge H(X | Z_1, \ldots, Z_K) \ge \sum_k [H(W_k | Z_k, W_1, \ldots, W_{k-1}) - H(W_k | X, Z_k, W_1, \ldots, W_{k-1})] = \sum_k H(W_k | Z_k, W_1, \ldots, W_{k-1})$.

With MAN symmetric placement, the fraction of $W_k$ not cached by user $k$ and not determined by $W_1, \ldots, W_{k-1}$ decreases with $k$. After averaging over all $K!$ orderings: $RF \ge \frac{1}{K!}\sum_{\pi} \sum_k H(W_{\pi(k)} | Z_{\pi(k)}, W_{\pi(1)}, \ldots, W_{\pi(k-1)}) = (K-t)F/(t+1)$.

Message $i$ (for group $\mathcal{S}_i$) is wanted by all $t+1$ users in $\mathcal{S}_i$. User $k \in \mathcal{S}_i$ experiences interference from messages $j \ne i$. However, user $k$ can use its cache to cancel some interference terms within each multicast message.

After cache-based cancellation, user $k \in \mathcal{S}_i$ needs to decode one sub-file from message $i$ while suppressing $L-1$ interfering messages. With $L$ transmit antennas and $L-1$ interference constraints, there is exactly 1 degree of freedom for the desired signal — sufficient for ZF.

The beamforming vector $\mathbf{v}_i$ must satisfy: $\mathbf{h}_k^H \mathbf{v}_j = 0$ for all $k \in \mathcal{S}_i$ and $j \ne i$ (after cache cancellation reduces the effective number of interferers). With $L$ antennas and $L-1$ ZF constraints per user, the system $[\mathbf{h}_{k_1}, \ldots, \mathbf{h}_{k_{L-1}}]^H \mathbf{v}_i = \mathbf{0}$ has a 1-dimensional solution space (generically), proving feasibility.

With $K$ users in a unit square, the average inter-user distance is $\Theta(1/\sqrt{K})$. Setting $r = c/\sqrt{K}$ for a sufficiently large constant $c$ ensures that the expected number of neighbors is $K \pi r^2 = K\pi c^2/K = \pi c^2 = \Theta(1)$. By standard random geometric graph results, this guarantees connectivity w.h.p.

Divide the unit square into cells of side $\Theta(r)$. There are $\Theta(1/r^2) = \Theta(K)$ cells. Within each cell, $\Theta(1)$ users communicate. Cells separated by $\Theta(r)$ can transmit simultaneously without interference (interference decays with distance). Using a constant number of colors (spatial TDMA with reuse factor $\Theta(1)$): $\Theta(K)$ simultaneous transmissions.

Within each cell of $K_c = \Theta(1)$ users, coded caching with $t_c = K_c M/N = \Theta(M/N)$ gives delivery load $\Theta(K_c/t_c) = \Theta(N/M)$ per cell. Each cell takes $\Theta(N/M)$ time slots. With $\Theta(K)$ cells operating in parallel: total time $\Theta(N/M)$. Per-user throughput: $1$ file / $\Theta(N/M)$ slots $= \Theta(M/N)$.

User $k$ caches each bit of each file independently with probability $q_k = M_k/N$. The expected cache size is $N \times q_k \times F = M_k F$. Correct.

A bit not cached by user $k$ (prob $1-q_k$) but cached by all users in $\mathcal{S}$ (prob $\prod_{j \in \mathcal{S}} q_j$) can be served via a multicast to the group $\mathcal{S} \cup \{k\}$. The delivery load is: $R = \sum_{k=1}^K (1-q_k) \sum_{\mathcal{S} \subseteq [K]\setminus\{k\}} \frac{\prod_{j \in \mathcal{S}} q_j \prod_{j \notin \mathcal{S}\cup\{k\}} (1-q_j)}{|\mathcal{S}|+1}$.

For the symmetric case $q_k = q$ for all $k$: $R = K(1-q)\sum_{s=0}^{K-1} \binom{K-1}{s}q^s(1-q)^{K-1-s}/(s+1)$ $= K(1-q) \cdot \frac{1-(1-q)^K}{Kq} = \frac{(1-q)(1-(1-q)^K)}{q}$ which matches the decentralized MAN result.

For the worst-case demand $d_1 = 1, d_2 = 2$ (distinct files): $RF \ge H(W_1 | Z_1) \ge F - MF = (1-M/N)F$ (user 1's missing info). $RF \ge H(W_2 | Z_2) \ge (1-M/N)F$ (user 2's missing info). $RF \ge \frac{1}{2}H(W_1, W_2 | Z_1, Z_2) \ge \frac{1}{2}(2F - 2MF) = (1-M/N)F$.

The joint bound: $2RF \ge H(W_1|Z_1) + H(W_2|Z_2,W_1)$. The second term is $H(W_2|Z_2,W_1) = H(W_2|Z_2) - I(W_1;W_2|Z_2)$. But $I(W_1; W_2 | Z_2) \le I(W_1; Z_2) \le MF$ (user 2's cache has at most $MF$ bits about $W_1$). Therefore $2RF \ge 2(1-M/N)F - MF/N \cdot ...$. After careful accounting: $R \ge 2(1-M/N)/(1+2M/N)$, matching the MAN achievability.

A $(K, F', Z, S)$-PDA is an $F' \times K$ array with entries from $\{*, 1, 2, \ldots, S\}$ such that: (1) each column has exactly $Z$ stars (cached sub-files), (2) each integer appears at most once per row, and (3) if entry $(f, k) = s$ and entry $(f, k') = s$ for $k \ne k'$, then entries $(f, k')$ and $(f', k)$ are both stars (enabling XOR decoding).

Use a Steiner system $S(2, q, K)$ (a collection of $q$-element blocks covering every pair of users exactly once). The blocks define the multicast groups. This gives subpacketization $F' = K(K-1)/(q(q-1))$ (polynomial in $K$) and coded multicasting gain $q$ (constant, independent of $K$).

The gain is $q$ instead of $t+1 = 1+KM/N$ (which can be much larger). The subpacketization is $O(K^2)$ instead of $\binom{K}{t}$. This is the fundamental subpacketization-gain tradeoff: polynomial subpacketization at the cost of bounded (constant) multicasting gain.

Allocate cache fraction $\alpha M$ to the top $N_p$ files (coded caching) and $(1-\alpha)M$ to the remaining files (uncoded caching). Within each group, use the MAN scheme with the appropriate parameters.

The probability of requesting a popular file is $\sum_{n=1}^{N_p} p_n$. Expected load = (prob. all demands popular) $\times R_{\text{MAN}}(N_p, \alpha M)$

• (otherwise) $\times R_{\text{uncoded}}$. Optimize over $\alpha$ and $N_p$.

For $\gamma > 1$: most of the probability mass is on the first few files. With $N_p = O(K^{1/\gamma})$ popular files and $\alpha = 1$: the demand is almost surely for a popular file, and the MAN gain applies fully. The expected load decreases as the probability of unpopular demands vanishes.

1. For each $M$: compute $t = KM/N$, subpacketization $F' = \binom{K}{t}$.
2. Generate the placement matrix: entry $(n, \mathcal{T}, k) = 1$ iff $k \in \mathcal{T}$.
3. For each demand vector $\mathbf{d}$: compute the set of required XOR messages and sum their sizes.

With $N = 20 > K = 10$: many demand vectors have repeated requests (demand collisions). When two users request the same file, fewer coded messages are needed. The average load is strictly less than the worst-case load.

At $M/N = 0.5$ ($t = 5$): worst-case $R = 5 \times 0.5 / 6 = 0.417$. Average: approximately $0.3$-$0.35$ (depending on $N/K$ ratio).