Ferkans — Interactive Telecom Tutor

Quantifying the Gap

With the MAN upper bound and the cut-set lower bound in hand, we can plot the memory-load envelope — the region in the $(M, R)$ plane bounded above by MAN and below by cut-set. The width of this envelope is the slack: the unknown region where $R^*(M)$ might lie.

A natural question is: what is the multiplicative gap $R_{\text{MAN}}/R_{\text{cut-set}}$ ? Maddah-Ali and Niesen proved it is at most 12; later analyses reduced it to 4 (under coded placement) and exactly 1 (under uncoded placement, YMA 2018). This section quantifies the gap and discusses what it tells us about the structure of the problem.

Theorem: Order-Optimality of MAN

For all $K, N \geq 1$ and $M \in [0, N]$ , $\frac{R_{\text{MAN}}(M)}{R^*(M)} \;\leq\; 12.$ In particular, the MAN scheme is order-optimal: it achieves a rate within a constant factor of any possible scheme's rate.

Order-optimality is a weaker but still very useful statement: the MAN scheme's rate cannot be more than a constant factor above the true optimum. This is the kind of guarantee that lets systems engineers deploy MAN-like schemes confidently: the asymptotic gain $1 + KM/N$ is correct up to a constant factor, which in most practical regimes is much less than 12.

Proof

Three regimes for $M$

Split $M \in [0, N]$ into three regimes based on how $M$ compares to $N/K$ : (i) $M \leq N/(K \lceil \log_2 K \rceil)$ (small $M$ ), (ii) $N/(K \lceil \log_2 K \rceil) < M < N/2$ , (iii) $M \geq N/2$ .

Small $M$ regime

For small $M$ , $R_{\text{MAN}} \approx K(1-M/N) \approx K$ . Cut-set with $s = K$ : $R \geq K - KM$ , which is approximately $K$ for small $M$ . Gap: constant $\leq 2$ .

Intermediate $M$ regime

Use cut-set with $s = K/t$ for $t = KM/N$ . After some algebra, the gap is bounded by a constant $\leq 12$ (this is the delicate part of the MN '14 proof).

Large $M$ regime

For $M \geq N/2$ , both $R_{\text{MAN}}$ and the cut-set bound are near zero; the gap is bounded by a constant.

Take max

Maximum multiplicative gap across all regimes is 12. (The number 12 was later improved in subsequent works; it is not tight, but it suffices to establish order-optimality.) $\blacksquare$

MAN Gap vs. Cut-Set

The multiplicative gap $R_{\text{MAN}}/R_{\text{cut-set}}$ as a function of $M/N$ . Horizontal reference lines show the MN '14 proven bound (gap $\leq 12$ ) and the YMA '18 tight result (gap = 1 under uncoded placement). The gap is typically much smaller than 12 — maxing around 2–3 for typical $K, N$ . The plot reveals where the cut-set bound is slack (large gap) and where it is nearly tight (gap $\approx 1$ ).

Parameters

Number of users K20

Number of files N40

Definition:
Number of Distinct Demands

Given a demand vector $\mathbf{d} = (d_1, \ldots, d_K)$ , let $N_e(\mathbf{d}) \;=\; |\{d_1, d_2, \ldots, d_K\}|$ denote the number of distinct demands. We have $1 \leq N_e(\mathbf{d}) \leq \min(K, N)$ .

Worst-Case Demands: All Distinct

For the MAN scheme, the worst-case rate is achieved when $N_e(\mathbf{d}) = \min(K, N)$ — all users request distinct files (if $K \leq N$ ), or every file is requested at least once (if $K > N$ ). Intuitively, when demands coincide, the server can exploit the coincidence to reduce the number of distinct subfiles to deliver. The rigorous statement: for MAN delivery, the rate depends on $\mathbf{d}$ only through $N_e(\mathbf{d})$ and equals $R_{\text{MAN}}(M, N_e)$ , monotone in $N_e$ .

This is why the "worst-case" definition of $R^*(M)$ focuses on distinct demands: they maximize over all demand vectors.

Rate vs. Number of Distinct Demands

The MAN rate as a function of the number of distinct demands $N_e(\mathbf{d})$ . Worst case is $N_e = \min(K, N)$ ; easier demand vectors (many coincidences) allow strictly lower rate. This reveals a fundamental averaging question: the MAN worst-case rate is not the average-case rate, and the gap between them is the subject of research in non-uniform demand regimes (Chapter 13).

Parameters

Number of users K10

Number of files N20

Memory ratio M/N0.2

Example: Gap Analysis: $K = 3$ , $N = 3$

For $K = N = 3$ , compute $R_{\text{MAN}}(M)$ and the cut-set lower bound for $M \in \{0, 1, 2, 3\}$ . Quantify the gap.

Solution

MAN rates

$t = KM/N = M$ . $R_{\text{MAN}}(t) = (K-t)/(t+1)$ . So: $M=0, R=3$ ; $M=1, R=2/2=1$ ; $M=2, R=1/3$ ; $M=3, R=0$ .

Cut-set bounds

$s \in \{1, 2, 3\}$ . $s=1, \lfloor N/s \rfloor = 3$ : $R \geq 1 - M/3$ . $s=2, \lfloor N/s \rfloor = 1$ : $R \geq 2 - 2M$ . $s=3, \lfloor N/s \rfloor = 1$ : $R \geq 3 - 3M$ . Max over $s$ : $M=0$ : max(1, 2, 3) = 3. $M=1$ : max(2/3, 0, 0) = 2/3. $M=2$ : max(1/3, -2, -3) = 1/3. $M=3$ : 0.

Gap ratios

$M=0$ : 3/3 = 1 (tight!). $M=1$ : 1/(2/3) = 1.5. $M=2$ : (1/3)/(1/3) = 1 (tight!). $M=3$ : 0/0 (undefined). The cut-set bound is tight at $M = 0$ and $M = 2$ , but loose at $M = 1$ . MAN exceeds the cut-set by factor $1.5$ at $M = 1$ .

What the Gap Tells Us

The example above shows the cut-set bound is often tight at the endpoints ( $M = 0$ and $M = N$ ) but loose in the middle. Why? The middle region $M \approx N/K \cdot t$ for moderate $t$ is where the coded multicasting gain is most pronounced; the cut-set bound does not capture this gain directly — it is a joint-entropy argument that does not distinguish between uncoded and coded schemes.

The YMA '18 converse (next section) fills this gap by using a more refined information-theoretic argument that explicitly accounts for uncoded placement structure. Under general (coded) placement, the gap-closing remains open.

Common Mistake: A Bound Can Be Loose Without Being Useless

Mistake:

Dismissing the cut-set bound because it is not tight: "MAN is order-optimal, so who cares about the converse?"

Correction:

Even a loose converse serves two purposes: (i) No-go result: the converse tells us no scheme can do strictly better than the bound. Even if MAN is not optimal, the true $R^*$ is bounded below by cut-set. (ii) Scaling structure: the cut-set bound has the form $s(1 - sM/N)$ , which suggests the general shape of $R^*$ as a function of $M$ . MAN also has this shape. The coincidence is not accidental.

More refined converses — YMA '18 and beyond — build on the cut-set bound, tightening it with additional information-theoretic constraints.

The Memory-Load Envelope and the Gap

Quantifying the Gap

Theorem: Order-Optimality of MAN

Three regimes for $M$

Small $M$ regime

Intermediate $M$ regime

Large $M$ regime

Take max

MAN Gap vs. Cut-Set

Parameters

Definition: Number of Distinct Demands

Worst-Case Demands: All Distinct

Rate vs. Number of Distinct Demands

Parameters

Example: Gap Analysis: K=3K = 3K=3, N=3N = 3N=3

MAN rates

Cut-set bounds

Gap ratios

What the Gap Tells Us

Common Mistake: A Bound Can Be Loose Without Being Useless

Definition:
Number of Distinct Demands

Example: Gap Analysis: $K = 3$ , $N = 3$