Exercises

$H_{1000,1} \approx 7.49$. $H_{100,1} \approx 5.19$. Hit ratio: $5.19/7.49 \approx 0.69$. $R = 50 \cdot 0.31 = 15.5$ files/round. Compare uniform case: $R_{\text{uniform,avg}} = 50 \cdot 0.9 = 45$. Zipf helps ~3×.

Decentralized: $9 \cdot (1 - 0.9^{50}) = 9 \cdot (1 - 0.005) \approx 8.95$. Centralized MAN: $50 \cdot 0.9/6 = 7.5$ at integer $t = 5$. Decentralized slightly higher (gap vanishes as $K \to \infty$).

MAN rate depends on $t = KM/N$, which for heterogeneous caches translates to $t_\text{agg} = \sum_k M_k/N$. Rich-cache users hold more of the library and contribute to XOR messages that benefit poor-cache users. Poor-cache users still receive content but their own hit rate is lower. The aggregate cache is the key quantity.

Under Zipf-$\alpha$ with $\alpha \in (0, 1)$, effective memory ratio $\mu_\text{eff} = \mu^{1-\alpha}$. For $\alpha = 0$ (uniform): $\mu_\text{eff} = \mu$. For $\alpha \to 1$: $\mu_\text{eff} \to 1$ (almost all demand is concentrated in cache).

Centralized MAN requires a coordinator that tells each user exactly which combinatorial subset to cache. Real systems have dynamic users (come/go), different arrival times, and operators without central control. Decentralized random placement has each user independently sample, with no coordination. It achieves MAN-like rate asymptotically (MN 2015) while being operationally simple.

$R_\text{MAN} = 20 \cdot 0.8/(1+4) = 3.2$.

At $\alpha = 0$ (uniform): $R_\text{pop} = 20(1-0.2) = 16$ — much larger than MAN. At $\alpha = 1$: $H_{40,1}/H_{200,1} \approx \ln 40/\ln 200 = 0.695$. $R_\text{pop} = 20 \cdot 0.305 = 6.1$ — still above MAN. At $\alpha = 1.5$: $\zeta$-dominated; $H_{40,1.5} \approx 2.08$, $H_{200,1.5} \approx 2.30$. Ratio $\approx 0.90$. $R_\text{pop} = 20 \cdot 0.10 = 2.0$ — below MAN.

Approximately $\alpha^* \approx 1.3$. For $\alpha > 1.3$ popularity wins; for $\alpha < 1.3$ MAN wins in expectation.

For web / video (α = 0.6-1.2): MAN wins. For news / trending (α > 1.3): popularity wins.

Under random placement, each bit is cached by a random subset $\mathcal{S} \subseteq [K]$. Pr($\mathcal{S}$ has size $s$): $\binom{K}{s} \mu^s (1-\mu)^{K-s}$.

For each subset of size $s+1$, MAN delivery has $\binom{K}{s+1}$ XOR messages each of size proportional to the fraction of bits cached by exactly that subset: $\mu^s (1-\mu)^{K-s}$.

Total rate: $\sum_s \binom{K}{s+1} \mu^s (1-\mu)^{K-s}$ $= \frac{1}{\mu} \sum_s \binom{K}{s+1} \mu^{s+1} (1-\mu)^{K-s}$ $= \frac{1}{\mu} [(1-(1-\mu)^K) - (1-\mu)^K \cdot \mu]$... (after simplification). Result: $R_\text{dec} = (1-\mu)/\mu \cdot (1 - (1-\mu)^K) \cdot K$ (per $K$ users); per-user: $(1-\mu)/\mu \cdot (1-(1-\mu)^K)$.

As $K \to \infty$: $(1-\mu)^K \to 0$, so $R_\text{dec} \to K(1-\mu)/\mu$ — same rate per user as centralized MAN.

For $\alpha < 1$: $H_{K,\alpha} \sim K^{1-\alpha}$. $H_{0.1 N, \alpha}/H_{N,\alpha} \approx 0.1^{1-\alpha}$.

$\alpha = 0$: $0.1$ (uniform, 10% demand). $\alpha = 0.5$: $0.1^{0.5} \approx 0.32$. $\alpha = 1$: $\ln(0.1N)/\ln N \approx 1 - \log 10/\log N$, so for $N = 10^4$: $\approx 0.75$. $\alpha = 1.5$: $H_{\infty,1.5} \approx 2.61$. Using finite sum: top 10% covers ~90% demand.

Concentration grows dramatically with $\alpha$. At $\alpha > 1$, "80/20 rule" emerges: small fraction of files dominates demand.

For $K$ users with total budget $B$: $\sum M_k = B$. Under homogeneous allocation $M = B/K$: $t = KM/N = B/N$, rate $R \propto 1/t$.

Under concentrated allocation (one user has $M_1 = B$, others zero): $t = B/N$ (same aggregate). Rate: (Sengupta-Tandon- Clancy) at most 2× the homogeneous rate.

Aggregate dominates; distribution matters only up to constant factors. For ops: give caches proportional to user activity (high-usage devices get more); fairness/battery tradeoffs also matter.

$K = 100$, $B = 1000$ files. Homogeneous $M = 10$. Alternative: 10 users with $M = 100$, 90 with $M = 0$. Rate in both cases is within factor 2. So heterogeneity is ~operationally neutral under MAN.

Top 70 files cached by all users. Hit ratio for requests in top 70: $H_{70, 0.8}/H_{1000, 0.8} \approx 0.55$.

30 random files per user. Random user caches each of the remaining 930 files w.p. $30/930 \approx 0.032$. Under Zipf, this covers ~$0.032^{0.2} \approx 0.5$ probability mass of non-popular content, which is ~$1 - 0.55 = 0.45$ of total demand. So this component contributes $0.45 \cdot 0.5 = 0.225$ hit rate.

$0.55 + 0.225 = 0.775$ — higher than pure popularity ($0.55$) or pure random ($0.1$).

Random 30% enables MAN-style coded delivery. Effective caching gain picks up ~factor 2 compared to pure popularity. Hybrid is practically superior.

$R^* \geq c_\alpha \cdot K (1 - \mu_\text{eff})/(1 + K\mu_\text{eff})$ where $c_\alpha$ is a constant depending on $\alpha$ (but not $K, N, M$). Order-optimal with Ji-Tulino-Llorca-Caire achievability.

Extend Yu-Maddah-Ali-Avestimehr '18 converse: average over permutations of users and over Zipf-biased demand. The resulting symmetric rate is at least $c_\alpha \cdot$ MAN-like formula at $\mu_\text{eff}$.

The constant $c_\alpha$ is not determined exactly. Known: $c_\alpha \in [1, 4]$ roughly for $\alpha \in (0, 1)$. Tight constant is an open problem.

Marginal is Zipf-$\alpha$: $\Pr(d_k = n) = P_n$. Joint is adversarial: correlated demands possible.

Adversary maximizes rate. Can pick $\mathbf{d}$ with maximum distinct demands (each $d_k$ sampled from top-$K$ popular files, adversarially).

MAN worst-case rate: $K(1-\mu)/(1+K\mu)$, unchanged (MAN is demand-agnostic beyond distinct count). So adversarial Zipf doesn't hurt MAN: still worst-case optimal. Popularity caching, however, is hurt — adversary picks diverse unpopular files.

Standard MAN placement is static: fix once, use forever. With evolving content, the placement becomes stale (new popular content not cached; old cached content becomes unpopular).

1. Periodic refresh: every $T$ rounds, re-run MAN placement on current catalog.
2. Online learning: bandit algorithms for cache content updates, balancing exploration vs exploitation.
3. Lookahead placement: predict upcoming popular content (using engagement signals, social trends).

Chapter 20 treats online coded caching. Caire-group research on online MAN is ongoing; current state-of-art achieves near-offline optimality under mild regret assumptions.

Pareto: $P_n \propto n^{-\alpha}$ but only for rank $n$ above some threshold. Head is different.

The JTLC analysis extends as long as the tail decays sufficiently. For $\alpha > 1/2$, order-optimality result holds with modified constants. For flatter distributions, MAN becomes more competitive.

Yin-Caire et al. recent work (2023+) characterizes general heavy-tailed demand; results suggest universal $\Theta(M/N)$ effective behavior up to distribution- dependent constants.

Fraction $p$ of users participate (cache + serve). Effective network size $n_\text{eff} = p n$. Per-user scaling: $\Theta(M/N)$ if $p$ is constant (does not vanish with $n$).

Options:

1. Reduced service cost for participants (e.g., free data).
2. Payment / token reward for each D2D delivery served.
3. Priority service at base station for active D2D contributors.

Stable participation rate: cost $c$ of participating balanced by benefit $b$. Network designer subsidizes participation ($b > c$) to ensure $p > 0$. Equilibrium analysis in Caire-group research (2019+).

Practical schemes (Li-Fu-Caire 2021): tiered rewards based on contribution level, credit-based "I'll help if you helped me" reciprocity. Achieves $p \approx 0.5$-$0.8$ in simulation.