Ferkans — Interactive Telecom Tutor

Why Caching and Distributed Computing Are the Same Problem

Coded caching (Maddah-Ali / Niesen 2014) and coded distributed computing (Li / Maddah-Ali / Yu / Avestimehr 2018, our Chapter 2) are two faces of the same information-theoretic coin. In coded caching, $K$ users with local memory request files from a central server; the server uses a single broadcast to satisfy all demands. In coded computing, $N$ workers store partial intermediate values; the master uses an all-to-all shuffle to collect the missing parts. Both schemes use interference alignment to cram more information into fewer broadcasts: the user-side cache content is precisely what allows the "interference" of unwanted file fragments to be cancelled.

This section makes the connection precise. The cross-reference is intentionally heavy: readers of Book CC will recognize the Maddah-Ali / Niesen scheme of §4.3, and readers of Chapter 2 of this book will recognize the same achievability counting. The unifying principle is finite-field IA — the topic of Section 4.1 — applied to the broadcast / shuffle channel.

Definition:
Coded-Caching Problem

A coded-caching system has:

A library of $F$ files $W_1, \ldots, W_F$ , each of size $|W| = b$ bits.
A server connected to $K$ users via a noiseless shared broadcast link.
Per-user cache of size $M \cdot b$ bits ( $M \in [0, F]$ ), populated in a placement phase when user demands are unknown.
A delivery phase in which user $k$ requests file $W_{d_k}$ for a random demand vector $\mathbf{d} \in [F]^K$ .

The delivery rate $R(\mathbf{d})$ is the number of bits the server must broadcast (normalized by $b$ ) to satisfy demand $\mathbf{d}$ . The worst-case rate is $R^* = \max_{\mathbf{d}} R(\mathbf{d})$ . The information-theoretic question is: given cache size $M$ , what is the minimum achievable $R^*$ ?

Coded Caching

A two-phase scheme in which user caches are filled (placement) before demands are known, and a single broadcast satisfies all requests (delivery). Coded broadcasts exploit the cached side information to reduce the delivery rate.

Cache Memory $M$

The size of each user's local cache, measured in number-of-files units ( $M \in [0, F]$ ). Larger $M$ allows more side information to be exploited, reducing the delivery rate. The Maddah-Ali / Niesen tradeoff $R^*(M)$ characterizes the optimal exchange.

Theorem: Maddah-Ali / Niesen Coded-Caching Tradeoff

For the symmetric coded-caching system with $K$ users and $F$ files (assume $K M \in \{0, 1, \ldots, K\}$ for clarity), the centralized coded-caching scheme achieves worst-case delivery rate $R^*(M) \;=\; K \!\left(1 - \frac{M}{F}\right) \cdot \frac{1}{1 + KM/F},$ which improves over the uncoded baseline $R_{\text{uncoded}}(M) = K(1 - M/F)$ by a multiplicative factor of $1 + KM/F$ — the global caching gain. The scheme uses finite-field IA in the delivery phase: each broadcast XOR combines $1 + KM/F$ user demands into a single transmission, and each user's cache content cancels the unintended interferers.

Without caching, the server needs one broadcast per demanded file: $R = K(1 - M/F)$ if uncached portions are sent in the clear. With coded delivery, the server XORs together $1 + KM/F$ requests at a time; each user already has all but its own desired chunk and so can solve for the missing chunk by subtracting (XORing out) the others using its local cache. The "alignment" is in the cache placement: it is chosen centrally so that the right chunks meet at the right users.

Proof

Placement

Split each file into $\binom{K}{KM/F}$ subfiles indexed by subsets $\mathcal{T} \subset [K]$ of size $KM/F$ . User $k$ caches all subfiles whose $\mathcal{T}$ contains $k$ — total $\binom{K-1}{KM/F - 1}$ subfiles per file, or $\binom{K-1}{KM/F-1} \cdot F = MK \cdot \binom{K-1}{KM/F-1}/(K \cdot F)$ scaled correctly to $M \cdot F$ bits as required.

Delivery — XOR coding

For each subset $\mathcal{S} \subset [K]$ of size $KM/F + 1$ , broadcast $\bigoplus_{k \in \mathcal{S}} W_{d_k, \mathcal{S} \setminus \{k\}}$ , where $W_{f, \mathcal{T}}$ is file $f$ 's subfile indexed by subset $\mathcal{T}$ .

Total number of broadcasts: $\binom{K}{KM/F + 1}$ . Each broadcast is one subfile chunk, so the rate is $\binom{K}{KM/F + 1} / \binom{K}{KM/F}$ . Algebraic simplification gives $R^*(M) = K(1 - M/F)/(1 + KM/F)$ .

User $k$ decodes

For each broadcast indexed by $\mathcal{S} \ni k$ , user $k$ has cached $W_{d_j, \mathcal{S} \setminus \{j\}}$ for all $j \in \mathcal{S} \setminus \{k\}$ , so it can XOR them out and isolate $W_{d_k, \mathcal{S} \setminus \{k\}}$ — the desired subfile. Repeating across all $\mathcal{S} \ni k$ recovers all subfiles of $W_{d_k}$ . $\blacksquare$

Key Takeaway

The global caching gain $1 + KM/F$ is finite-field IA in disguise. Each broadcast satisfies $1 + KM/F$ users simultaneously by XOR-aligning their unintended portions inside their local caches. The factor $K$ in the gain is the number of users — not the cache size — confirming that the coding (alignment), not the storage, is what delivers the multiplicative improvement.

Example: $K = 3$ Users, $F = 3$ Files, $M = 1$

Three users, three files $A, B, C$ , each cache holds $M = 1$ file. Design a coded-caching scheme. Compare the delivery rate to the uncoded baseline.

Solution

Placement

$KM/F = 1$ . Split each file into $\binom{3}{1} = 3$ subfiles: $A = (A_1, A_2, A_3)$ , similarly $B$ and $C$ . User $k$ caches $A_k, B_k, C_k$ . Total per-user storage: $3$ subfiles = $1$ file, satisfying $M = 1$ .

Delivery — three XOR broadcasts

Suppose users 1, 2, 3 demand $A, B, C$ . The server broadcasts:

$A_2 \oplus B_1$ (for users 1 and 2 who hold $A_1, B_2$ )
$A_3 \oplus C_1$ (for users 1 and 3)
$B_3 \oplus C_2$ (for users 2 and 3)

Total: 3 broadcasts of subfile size, i.e., delivery rate $R = 3 \cdot (1/3) = 1$ file-equivalent.

Comparison

Uncoded delivery: send each requested file in its entirety minus what is cached, giving rate $R_{\text{uncoded}} = 3 \cdot (1 - 1/3) = 2$ . The coded scheme cuts this to $R^* = K(1-M/F)/(1+KM/F) = 3 \cdot (2/3)/2 = 1$ — a $2\times$ reduction. Each user decodes its desired file by XOR-subtracting the cached portions from each broadcast.

Operational meaning

The single-broadcast XOR aligns three demands into one transmission. The "interference" — the two unintended chunks per broadcast — is precisely what the recipient's cache cancels.

Coded Caching Memory–Rate Tradeoff

Plot the delivery rate $R^*(M)$ vs. the per-user cache size $M$ for coded vs. uncoded caching, for various numbers of users $K$ . The coded curve achieves the global gain $1 + KM/F$ over the uncoded baseline. As $K$ grows, the gain widens — the operational signature of the IA-style alignment in the delivery broadcasts.

Parameters

K

— users8

Number of users sharing the broadcast link

F

— files in library16

Total library size in number of files

One Broadcast Satisfying Three Users

Animation of the

K = 3

,

M = 1

Maddah-Ali / Niesen scheme. The server XORs three subfiles into a single broadcast; each user XORs out the two it does not need from its local cache, isolating its desired chunk.

Why This Matters: Coded Caching $\equiv$ Coded Shuffling

The Maddah-Ali / Niesen scheme is mathematically equivalent (up to relabeling) to the Li-Maddah-Ali-Avestimehr coded- shuffling scheme of Chapter 2. In both, the global gain is $1 + KM/F = N\mu$ , achieved by the same XOR-aligned broadcast construction. Chapter 7 of this book formalizes the equivalence and uses the connection to handle non-uniform demand distributions in distributed-ML data shuffling — a result where the CommIT group has made several contributions (Wan / Tuninetti / Caire 2021).

Common Mistake: Coded Caching Requires Coordinated Placement

Mistake:

Treat each user as caching independently — e.g., each user caches its top- $M$ favorite files based on local statistics.

Correction:

The global caching gain depends critically on coordinated placement: the server (or a designated controller) must assign each user a specific subset of subfiles, chosen so that the delivery-phase XOR alignment works. Decentralized placement (Maddah-Ali / Niesen 2014, §VI) recovers most of the gain at a small rate cost, but completely uncoordinated placement forfeits the alignment and reverts to uncoded performance.

⚠️Engineering Note

Coded Caching in Production CDNs

Major content delivery networks (Akamai, Cloudflare, Netflix Open Connect) currently use uncoded caching at the edge nodes. The reasons are practical: video chunks are large relative to per-edge memory, demand statistics shift on short timescales, and the IA-style coordination among edge nodes is hard to deploy without a tightly-controlled cluster. Several research-track deployments (Cisco's coded-caching pilot, MIT's TICS testbed) have demonstrated the predicted gains in laboratory settings, but production adoption is waiting for tighter integration with QUIC / HTTP/3 transport. Wireless-edge (5G / 6G) deployments are expected to be more receptive because spectrum is precious and coordination overhead is amortized over many users.

Practical Constraints

•
Production CDNs typically use uncoded LRU/LFU eviction
•
Coded-caching gains require coordinated placement, hard at scale
•
5G / 6G edge caching standards (3GPP TR 23.748) leave room for coded variants

📋 Ref: 3GPP TR 23.748 (edge computing and caching)

Historical Note: Coded Caching: A Decade of Impact

2014–present

Mohammad Ali Maddah-Ali and Urs Niesen's 2014 paper introduced coded caching as an information-theoretic problem distinct from cache-eviction policies. Their main result — a multiplicative global caching gain of $1 + KM/F$ — was the first polynomial-in- $K$ improvement over uncoded caching at any non-trivial cache size. The paper opened a decade of follow-on work: decentralized variants, hierarchical networks, demand-private caching (with relevant CommIT contributions in Chapters 7 and 15 of this book), and extensions to wireless interference networks. The "coded" half of the modern coded-computing field traces directly to this paper.

Quick Check

For $K = 10$ users with cache size $M = F/5$ , the global caching gain over the uncoded baseline is approximately:

$1 + KM/F = 3$

$M/F = 1/5$

$K = 10$

$F/M = 5$

Correction:

1 + KM/F = 3

$1 + 10 \\cdot (1/5) = 3$ . The coded delivery rate is $1/3$ of the uncoded rate at this $(K, M, F)$ point.

IA in Coded-Caching Delivery

Why Caching and Distributed Computing Are the Same Problem

Definition: Coded-Caching Problem

Coded Caching

Cache Memory MMM

Theorem: Maddah-Ali / Niesen Coded-Caching Tradeoff

Placement

Delivery — XOR coding

User $k$ decodes

Key Takeaway

Example: K=3K = 3K=3 Users, F=3F = 3F=3 Files, M=1M = 1M=1

Placement

Delivery — three XOR broadcasts

Comparison

Operational meaning

Coded Caching Memory–Rate Tradeoff

Parameters

One Broadcast Satisfying Three Users

Why This Matters: Coded Caching ≡\equiv≡ Coded Shuffling

Common Mistake: Coded Caching Requires Coordinated Placement

Coded Caching in Production CDNs

Historical Note: Coded Caching: A Decade of Impact

Quick Check

Definition:
Coded-Caching Problem

Cache Memory $M$

Example: $K = 3$ Users, $F = 3$ Files, $M = 1$

Why This Matters: Coded Caching $\equiv$ Coded Shuffling