Exercises

$R_\text{MA}(1) = K(1 - \mu)/(1 + K\mu)$ — standard MAN.

$L\mu = K\mu$. If $K\mu \geq 1$: rate = $K(1 - K\mu)/(1+K^2\mu)$. When $K\mu = 1$ (full cache): rate = 0. Matches intuition (every user has whole library).

$\mu = 0.1$. $L\mu = 0.2$. $KL\mu = 2$.

$R_\text{MA}(2) = 10 \cdot 0.8 / 3 = 2.67$ files/use.

Single-access: $R = 10 \cdot 0.9 / 2 = 4.5$. Multi-access is $1.7\times$ better.

Each cache holds random $M/N$ fraction. User's $L$ caches together hold $1 - (1 - \mu)^L$ of library (by inclusion- exclusion) — less than $L\mu$ when $L \geq 2$.

Cyclic disjoint placement: partitioned cover. Each user's access set sees exactly $LM$ distinct files — full $L\mu$ effective memory.

Structured placement essential for full multi-access gain.

Each file $W_n$ split into 4 subfiles $W_{n, 0}, W_{n, 1}, W_{n, 2}, W_{n, 3}$, each of size $F/4$. With $M = 1$: cache $j$ stores 2 subfiles (M K / N = 1).

Cache 0: $\{W_{n, 0}, W_{n, 2}\}$ for all $n$. Cache 1: $\{W_{n, 1}, W_{n, 3}\}$. Cache 2: $\{W_{n, 2}, W_{n, 0}\}$. Cache 3: $\{W_{n, 3}, W_{n, 1}\}$.

User 0 accesses caches 0, 1: subfiles $\{0, 2\} \cup \{1, 3\} = \{0, 1, 2, 3\}$ — full file! User 0 has effective memory = 4 files of content, decodes locally. Matches $L\mu = 0.5$: user 0 has half memory per file. Actually $2M = 2$ files worth — matches $L M = 2$.

$R_\text{MA} = 4(1 - 0.5)/(1 + 2) = 2/3$ files/use.

Effective memory = $1 - (1-\mu)^L$. Rate: $R \sim K(1 - (1 - (1-\mu)^L))/(1 + K (1 - (1-\mu)^L))$.

$R_\text{HKD} = K(1 - L\mu)/(1 + KL\mu)$.

$(1 - (1-\mu)^L) \leq L\mu$ (Bernoulli inequality). Hence decentralized is strictly worse for $L > 1$. Numerical gap: $\mu = 0.1$, $L = 4$: $L\mu = 0.4$; $1 - 0.9^4 = 0.344$. $\sim 15\%$ gap.

HKD's placement is $\mathbb{Z}_K$-invariant under rotation. Each user's access set is a shifted copy of every other's. This is essential for delivery symmetry.

Random access sets: no common structure. Some users share many caches, others share none. Overlaps uneven.

Disjoint coverage may fail for some users. Delivery XOR structure also breaks. Need generalized design (§18.3) or PDA-like heuristics.

For a set of $t$ users $\mathcal{T}$ with access sets $\mathcal{A}_\mathcal{T} = \cup_{k \in \mathcal{T}} \mathcal{A}_k$, they collectively hold $|\mathcal{A}_\mathcal{T}| \cdot M$ files worth.

Broadcast $X$ + caches must let all $t$ users decode their $t$ files (distinct under worst case): $R + |\mathcal{A}_\mathcal{T}| M \geq t$, i.e., $R \geq t - |\mathcal{A}_\mathcal{T}| M$.

Minimizing over $\mathcal{T}$: $R \geq \max_t (t - \min_{\mathcal{T}:|\mathcal{T}|=t} |\mathcal{A}_\mathcal{T}| M)$.

Consecutive $t$ users: $|\mathcal{A}_\mathcal{T}| = t + L - 1$. So $R \geq t(1 - M) - (L-1)M$. Combined with HKD's achievable: gap by constant factor.

Points: 9 pairs $(x, y) \in \mathbb{F}_3^2$. Lines: 12 (4 directions $\times$ 3 parallel lines each).

Direction 0 (horizontal): $\{(x, 0), (x, 1), (x, 2)\}$ for $y = 0, 1, 2$. Similarly for vertical, diagonal-1, diagonal-(-1).

9 users (points), 12 caches (lines), each cache serves 3 users (points on line). Each user is in 4 lines (4 directions).

Using the Katyal-Ramkumar-style formula: $R \sim (1/r)(1 - k/v) = (1/4)(1 - 3/9) = 1/6$ of uncoded.

• Dense deployment with multiple APs (stadium, campus).
• Infrastructure-controlled caching (operator).
• Broadcast delivery preferred over P2P.

• Sparse infrastructure (rural, IoT).
• Battery-constrained devices (D2D shorter range).
• Peer-based content sharing (social networks).

Many real deployments: multi-access AP + D2D offload for neighbor devices. Active research in CommIT.

$\mu = 0.1$. $L\mu = 0.4$. $KL\mu = 800$.

$R_\text{MA} = 2000 \cdot 0.6 / 801 = 1.498$ clips/use.

$R = 2000 \cdot 0.9 / 201 = 8.955$ clips/use. Multi-access is $6\times$ better.

At 10 Mbps per clip: multi-access saves ~75 Gbps aggregate Wi-Fi backhaul load at peak.

User accesses $L_1$ edge + $L_2$ regional + $L_3$ origin caches. Per-tier ratios $\mu_1, \mu_2, \mu_3$.

If disjoint across tiers: $\sum_\ell L_\ell \mu_\ell$ total.

$R \sim K(1 - \sum_\ell L_\ell \mu_\ell)/(1 + K \sum_\ell L_\ell \mu_\ell)$.

Higher tiers (regional, origin) typically have larger caches (larger $\mu$) but fewer users accessing (smaller $L$). Tradeoffs explored in Wan-Caire 2023.

If $LM > N$: user's $L$ caches would need to store more than the full library. Impossible without redundancy.

In this regime, overlapping cache content is unavoidable. Effective memory caps at $N$ — full library cached in user's access set.

If $LM \geq N$: $R = 0$ (trivial, everybody has everything). The interesting regime is $LM < N$.

Placement: HKD cyclic + shared permutation per user. Delivery: users send masked demands, server runs HKD on masked demands.

Same as HKD (privacy free in MAN, also free here).

Provides demand privacy across multi-access topology — useful for stadium scenarios where fans shouldn't know neighbors' video preferences.

Mid-delivery mobility: user's effective memory changes. HKD placement assumes stationary access.

• Hysteresis. User commits to initial access set for round duration.
• Delivery retransmission. Over-deliver to accommodate mobility.
• Robust placement. Design placement resilient to moderate access-set changes (active research).

If fraction $p$ of users move: effective rate degrades by $\sim (1 - p)^{\text{dep}}$ factor, depending on dependency.

HKD assumes regular cyclic. Real-world APs: irregular density. Resolvable designs help but don't cover all cases. Open: rate-optimal placement for arbitrary bipartite user-AP graph.

Uniform demand: MAN-optimal structure works. Zipf / skewed demand: unknown whether HKD cyclic is still optimal; maybe popularity-weighted multi-access placement is better.

CommIT multi-tier + user mobility: no closed-form optimal scheme. Likely requires online / adaptive caching (Ch 20).