Ferkans — Interactive Telecom Tutor

The MAN Scheme on One Page

Before we dive into proofs, here is the entire Maddah-Ali–Niesen scheme in one page. It works when $t = K M/ N$ is an integer (non-integer $t$ is handled by memory sharing, §2.5).

Placement (off-peak). Split each file $W_n$ into $\binom{K}{t}$ equal-sized subfiles, one per $t$ -subset of $[K]$ : $W_n \;=\; (W_{n,\mathcal{S}})_{\mathcal{S} \subseteq [K],\, |\mathcal{S}| = t}.$ Each subfile has size $F/\binom{K}{t}$ bits. Place subfile $W_{n,\mathcal{S}}$ in the cache of user $k$ if and only if $k \in \mathcal{S}$ .

Delivery (peak). For each $(t+1)$ -subset $\mathcal{S}' \subseteq [K]$ , send the coded message $X_{\mathcal{S}'} \;=\; \bigoplus_{k \in \mathcal{S}'} W_{d_k, \mathcal{S}' \setminus \{k\}}.$ There are $\binom{K}{t+1}$ such messages, each of size $F/\binom{K}{t}$ .

Rate. $R_{\text{MAN}} \;=\; \frac{\binom{K}{t+1}}{\binom{K}{t}} \;=\; \frac{K - t}{t + 1} \;=\; K\cdot \frac{1 - M/N}{1 + K M/N}.$

That is the entire scheme. The rest of this chapter spells out why it works and verifies the claims.

Definition:
The Maddah-Ali–Niesen (MAN) Scheme

Fix $K$ , $N$ , $M$ with $t = K M/N \in \{0, 1, \ldots, K\}$ . The Maddah-Ali–Niesen (MAN) scheme consists of the following placement and delivery algorithms.

Placement. Each file $W_n$ is split into $\binom{K}{t}$ subfiles of equal size $F/\binom{K}{t}$ , indexed by $t$ -subsets $\mathcal{S} \subseteq [K]$ . The cache of user $k$ is $\mathcal{Z}_{k} \;=\; \{\, W_{n,\mathcal{S}} \,:\, n \in [N],\; \mathcal{S} \subseteq [K],\; |\mathcal{S}| = t,\; k \in \mathcal{S} \,\}.$ That is, user $k$ holds every subfile whose index set contains $k$ .

Delivery. On demand vector $\mathbf{d} \in [N]^K$ , for every $(t+1)$ -subset $\mathcal{S}' \subseteq [K]$ , the server broadcasts $X_{\mathcal{S}'} \;=\; \bigoplus_{k \in \mathcal{S}'} W_{d_k,\; \mathcal{S}' \setminus \{k\}}.$ The XOR is over $\mathbb{F}_2^{F/\binom{K}{t}}$ (bitwise).

Key Takeaway

Each coded message $X_{\mathcal{S}'}$ simultaneously serves exactly $t + 1$ users — namely all $k \in \mathcal{S}'$ . For each $k \in \mathcal{S}'$ , user $k$ can recover $W_{d_k, \mathcal{S}' \setminus \{k\}}$ because every other summand $W_{d_j, \mathcal{S}' \setminus \{j\}}$ (with $j \neq k$ ) is already in user $k$ 's cache (since $k \in \mathcal{S}' \setminus \{j\}$ ). This is the coded multicasting gain in its purest form.

MAN Placement (K=3, t=1)

For

K=3

,

t=1

: each file is split into

\binom{3}{1} = 3

subfiles

W_{n,\{1\}}, W_{n,\{2\}}, W_{n,\{3\}}

. User

k

caches exactly the subfiles indexed by subsets containing

k

— here, a single subfile per file. Per-user storage:

N \cdot 1/3 = M

files' worth.

MAN Delivery — One XOR Serves $t+1$ Users

For demands

d = (1, 2, 3)

on

K=3

,

t=1

: three XOR messages, one per 2-subset of

[3]

. Each message uses bits that the two targeted users already have in their caches, so the single message simultaneously delivers one subfile to each of the two.

Example: Walkthrough: $K = 3$ , $t = 1$ , $N = 2$ Files

Take $K = 3$ , $N = 2$ , $M = 2/3$ (so $t = KM/N = 1$ ). Execute the MAN scheme for demand $\mathbf{d} = (1, 2, 2)$ .

Solution

Split files

Each file is split into $\binom{3}{1} = 3$ subfiles: $W_1 = (W_{1,\{1\}},\, W_{1,\{2\}},\, W_{1,\{3\}})$ and $W_2 = (W_{2,\{1\}},\, W_{2,\{2\}},\, W_{2,\{3\}})$ . Each subfile has size $F/3$ bits.

Populate caches

User 1's cache: $\{W_{n,\{1\}} : n \in \{1,2\}\} = \{W_{1,\{1\}}, W_{2,\{1\}}\}$ , total size $2 \cdot F/3$ = $M F$ bits ( $M = 2/3$ ). ✓ User 2: $\{W_{1,\{2\}}, W_{2,\{2\}}\}$ . User 3: $\{W_{1,\{3\}}, W_{2,\{3\}}\}$ .

Delivery: enumerate $(t+1)$-subsets

$(t+1) = 2$ -subsets of $[3]$ : $\{1,2\}, \{1,3\}, \{2,3\}$ . Three coded messages.

$X_{\{1,2\}} = W_{d_1, \{2\}} \oplus W_{d_2, \{1\}} = W_{1,\{2\}} \oplus W_{2,\{1\}}$ .

$X_{\{1,3\}} = W_{d_1, \{3\}} \oplus W_{d_3, \{1\}} = W_{1,\{3\}} \oplus W_{2,\{1\}}$ .

$X_{\{2,3\}} = W_{d_2, \{3\}} \oplus W_{d_3, \{2\}} = W_{2,\{3\}} \oplus W_{2,\{2\}}$ .

Verify each user decodes

User 1 receives $X_{\{1,2\}}, X_{\{1,3\}}$ . It has $W_{2,\{1\}}$ in its cache, so from $X_{\{1,2\}} = W_{1,\{2\}} \oplus W_{2,\{1\}}$ it recovers $W_{1,\{2\}}$ . From $X_{\{1,3\}} = W_{1,\{3\}} \oplus W_{2,\{1\}}$ it recovers $W_{1,\{3\}}$ . It already has $W_{1,\{1\}}$ . Done: all three subfiles of $W_1$ . ✓

User 2 already has $W_{2,\{2\}}$ . From $X_{\{1,2\}}$ with $W_{1,\{2\}}$ in cache: decodes $W_{2,\{1\}}$ . From $X_{\{2,3\}} = W_{2,\{3\}} \oplus W_{2,\{2\}}$ with $W_{2,\{2\}}$ in cache: decodes $W_{2,\{3\}}$ . All three subfiles of $W_2$ . ✓

User 3: already has $W_{2,\{3\}}$ . From $X_{\{2,3\}}$ : recovers $W_{2,\{2\}}$ . From $X_{\{1,3\}}$ : recovers $W_{2,\{1\}}$ ... wait, user 3 needs $W_2$ 's subfiles, but $X_{\{1,3\}}$ contains $W_{1,\{3\}} \oplus W_{2,\{1\}}$ . User 3 has $W_{1,\{3\}}$ in cache, so it decodes $W_{2,\{1\}}$ . ✓

Compute the rate

3 messages, each of size $F/3$ bits: total $F$ bits. Rate $R = 1$ file. MAN formula: $R = 3 \cdot (1 - 2/9) / (1 + 3 \cdot 2/9) \cdot (\text{recalling } M = 2/3, N = 2 \Rightarrow M/N = 1/3)$ . Wait — let me recompute with $M/N = 1/3$ : $R = 3(1 - 1/3)/(1 + 3 \cdot 1/3) = 2/2 = 1$ . ✓ Match.

Placement Structure — Which Subfile Goes to Which User?

Visualize the MAN placement as a heatmap: rows are subfiles $W_{n,\mathcal{S}}$ (indexed by $t$ -subsets $\mathcal{S}$ of $[K]$ ), columns are users. A filled cell means subfile $W_{n,\mathcal{S}}$ is placed in user $k$ 's cache. Each row has exactly $t$ filled cells (subfile in $t$ caches); each column has $\binom{K-1}{t-1}$ filled cells (user $k$ holds that many subfiles per file).

Parameters

Number of users K4

Gain parameter t2

MAN subfile

A subfile $W_{n,\mathcal{S}}$ of file $W_n$ indexed by a $t$ -subset $\mathcal{S} \subseteq [K]$ . Every subfile has equal size $F/\binom{K}{t}$ bits, and subfile $W_{n,\mathcal{S}}$ is stored in the caches of exactly the users $k \in \mathcal{S}$ .

Related: Coded multicasting

Coded multicasting

The delivery-phase technique of sending a single XOR-coded message $X_{\mathcal{S}'}$ that simultaneously satisfies $t+1$ users, one per element of $\mathcal{S}'$ . This is the core combinatorial gain of the MAN scheme, distinguishing it from uncoded delivery.

Coded caching gain

The multiplicative factor $(1 + t)^{-1}$ by which the MAN scheme's delivery rate is smaller than the uncoded rate $K(1-M/N)$ . For $t = KM/N$ large, the gain is unbounded.