《Fundamental Limits of Caching》论文精读

作者：Mohammad Ali Maddah-Ali, Urs Niesen

发表：IEEE Transactions on Information Theory, 2014

领域：信息论 / 网络编码 / 缓存网络

一、开篇导读

1.1 论文基本信息

• 论文题目：Fundamental Limits of Caching

• 作者：Mohammad Ali Maddah-Ali, Urs Niesen

• 发表：IEEE Transactions on Information Theory, 2014

• 领域：信息论 / 网络编码 / 缓存网络

这篇论文是编码缓存（Coded Caching）方向的奠基之作，提出了一个反直觉但极其深刻的观点：缓存不仅能用来“本地命中”，还能用来创造多用户编码机会，从而大幅降低服务器的传输压力。

1.2 为什么这篇论文重要？

传统认知里，缓存的作用很简单：用户存了什么，就不用再传什么。这叫本地缓存增益——存得越多，传得越少，天经地义。但这篇论文告诉我们事情没这么简单。如果精心设计每个用户存什么，那么在用户请求不同文件时，服务器可以发送一个 XOR 编码信号，同时满足多个用户的需求。一个信号顶多个，这叫全局缓存增益——缓存越大，能创造的编码机会越多，传输速率下降得比你想象的快得多。

这篇论文的三大贡献：

1. 形式化定义了信息论意义下的缓存问题，给出了最优速率 $R^{\star }(M)$ 的严格定义。

2. 提出编码缓存方案，证明了可实现速率 $R_C(M)$（上界）。

3. 给出 cut-set 下界，并证明方案是 12-近似最优的。

自这篇论文之后，编码缓存成为信息论和网络通信领域的热门方向，衍生出无线场景、去中心化、多接入等大量扩展工作。要做这个方向，这篇是绕不开的起点。

1.3 阅读建议

前置知识：

• 信息论基础（熵、互信息、渐近可实现性）。

• 基本的组合数学（二项式系数、集合运算）。

• 知道 XOR 编码是什么就行，不需要网络编码的深入背景。

怎么读这篇精读：

• 如果你是第一次接触：建议从头按顺序读，第五章的系统模型是理解后续一切的基础。

• 如果你只关心核心思想：先看第七章的两个、三个用户例子，再看第八章一般构造。

• 如果你关心证明细节：第九、十章以及第十二章附录是重点，cut-set bound、常数近似和精确特例的推导都在那里。

读的时候记住一句话：放置阶段的设计是为了给交付阶段的编码创造条件。

二、论文整体结构概览

2.1 论文章节地图

论文原文共 8 个正文章节，另有附录，逻辑非常清晰：定义问题 → 给出结果 → 例子建立直觉 → 证明上界 → 证明下界 → 证明近似最优 → 讨论。

阅读主线：第二节定义了“我们在优化什么”，第三节说明“本文给出的结论”，第四节用例子预演证明，第五到七节分别证明上界、下界和两者的差距，逻辑层层递进。

2.2 核心概念速览

记住这张表，后面所有内容都是围绕这些概念展开的。

2.3 三大定理的关系

• Theorem 1 说：“我设计了一个方案，能达到速率 $R_C(M)$” → 这是上界，说明最优值 $R^{\star }(M)\le R_C(M)$。

• Theorem 2 说：“任何方案都不可能比这个下界更好” → 这是下界，说明最优值 $R^{\star }(M)\ge \text{下界}$。

• Theorem 3 说：“我设计的方案和理论最优之间，差距不超过 12 倍” → 把上下界联系起来，证明方案是常数近似最优的。

简单说：Theorem 1 告诉你“能做到多好”，Theorem 2 告诉你“最好能有多好”，Theorem 3 告诉你“这两者之间差不了太多（12 倍以内）”。

三、摘要（Abstract）精读

3.1 摘要原文与逐句解读

原文：

Caching is a technique to reduce peak traffic rates by prefetching popular content into memories at the end users. Conventionally, these memories are used to deliver requested content in part from a locally cached copy rather than through the network. The gain offered by this approach, which we term local caching gain, depends on the local cache size (i.e., the memory available at each individual user). In this paper, we introduce and exploit a second, global, caching gain not utilized by conventional caching schemes. This gain depends on the aggregate global cache size (i.e., the cumulative memory available at all users), even though there is no cooperation among the users. To evaluate and isolate these two gains, we introduce an information-theoretic formulation of the caching problem focusing on its basic structure. For this setting, we propose a novel coded caching scheme that exploits both local and global caching gains, leading to a multiplicative improvement in the peak rate compared with previously known schemes. In particular, the improvement can be on the order of the number of users in the network. In addition, we argue that the performance of the proposed scheme is within a constant factor of the information- theoretic optimum for all values of the problem parameters.

对照翻译： 缓存是一种通过将热门内容预取到终端用户的存储器中来降低峰值流量速率的技术。传统上，这些存储器用于从本地缓存的副本中提供部分请求内容，而非通过网络传输。这种方法带来的增益，我们称之为本地缓存增益，取决于本地缓存大小（即每个用户可用的存储器容量）。在本文中，我们引入并利用了第二种增益——全局缓存增益，这是传统缓存方案未曾利用的。这种增益取决于全局聚合缓存大小（即所有用户可用的累积存储器容量），尽管用户之间不存在任何协作。为了评估并分离这两种增益，我们引入了缓存问题的信息论表述，聚焦于其基本结构。在此设定下，我们提出了一种新颖的编码缓存方案，该方案同时利用本地和全局缓存增益，与已知方案相比，在峰值速率上实现了倍数级的提升。具体而言，这种提升可以达到网络中用户数量的量级。此外，我们论证了所提方案的性能在所有问题参数取值下，均在信息论最优值的常数因子范围内。

3.2 核心问题提炼

读完摘要，可以把这篇论文要回答的核心问题提炼为四个层层递进的问题：

问题一：传统缓存是否遗漏了什么？

传统缓存只利用了“本地存了就不用传”的本地增益。但在多用户场景下，每个用户存的内容不一样，这些分散的缓存之间是否存在某种协同效应，即使用户之间不直接通信，也能被服务器利用来减少传输？

问题二：如何严格定义这个问题？

要回答上面的问题，首先需要一个信息论层面的严格数学框架：缓存大小怎么度量？传输速率怎么定义？什么叫“一个方案是可行的”？最优性能怎么刻画？没有这些定义，就无法量化“全局增益”到底有多大。

问题三：能不能设计出利用全局增益的方案？

如果全局增益确实存在，具体该怎么设计缓存放置和传输策略才能把它用起来？能比传统方案好多少？是常数倍的提升，还是随用户数增长的量级提升？

问题四：这个方案离最优有多远？

提出一个方案不够，还需要知道它是不是最好的。信息论意义下的最优速率 $R^{\star }(M)$ 是多少？我们的方案和最优之间差多少？是差一个常数倍，还是差距随规模增长？

这四个问题构成了整篇论文的叙事主线：发现新增益 → 定义问题 → 设计方案 → 证明最优性。后面的章节就是按这个顺序展开的。

3.3 主要结论一句话概括

这篇论文发现了缓存的“全局增益”——通过精心设计每个用户存什么，服务器可以用 XOR 编码同时满足多个用户的不同请求；在适当的缓存规模下，相对传统方案的速率改善可达用户数量的量级。论文证明了所提编码缓存方案在所有参数下都满足 $R_C(M)\le 12R^{\star }(M)$，是常数近似最优的。

四、引言（Introduction）精读

4.1 研究背景

论文开篇从网络流量的时间波动性讲起：

“The high temporal variability of network traffic results in communication systems that are congested during peak-traffic times and underutilized during off-peak times.”

对照翻译： 网络流量的高度时间波动性，导致通信系统在高峰流量时段拥塞，而在非高峰时段利用率不足。

网络流量在高峰时段拥塞、在非高峰时段闲置，这是一个普遍存在的问题。缓存（caching）就是解决这个问题的标准技术：在非高峰时段把热门内容预取到用户本地，高峰时段就不用从网络传输了。

4.2 两个阶段受到不同的约束

原文：

From the above discussion, we see that the caching problem consists of two distinct phases. The first phase is the placement phase, which is based solely on the statistics of the user demands. In this phase, the network is not congested, and the main limitation is the size of the cache memories. The second phase is the delivery phase, which is performed once the actual demands of the users have been revealed. In this phase, the network is congested, and the main limitation is the rate required to serve the requested content.

对照翻译： 从上述讨论可以看出，缓存问题包含两个不同阶段。第一个阶段是放置阶段，它只以用户需求的统计信息为依据。在这一阶段，网络不拥塞，主要限制是缓存存储器的大小。第二个阶段是交付阶段，它在用户的实际需求揭示后进行。在这一阶段，网络拥塞，主要限制是服务这些请求所需的传输速率。

展开解读：

这里的“只知道统计信息”是对缓存系统的背景描述。本文随后采用最坏需求模型，不需要为每个文件指定请求概率。

真正不能违反的时间顺序是：先放置，再知道具体请求，再发送。 假如先知道用户最终请求哪一个文件，放置就可以直接针对该文件，问题会完全改变。

放置阶段不计入本文优化的峰值负载，并不意味着预取没有成本；作者把它视为另一个时段的资源。交付阶段的目标也不是减少服务器磁盘读取次数，而是减少共享瓶颈链路上的总比特数。

4.3 已有工作遗漏了什么？

原文：

Various versions of this problem have been studied, with the focus being mainly on exploiting the history or statistics of the user demands [1]–[7]. In these papers, the operation of the delivery phase is fixed to consist of simple orthogonal unicast or multicast transmissions. Assuming this method of delivery, the content placement is then optimized. The gain of caching in this approach results from making popular content available locally. In another line of research, the objective is to optimize the delivery phase for fixed known cache contents and for specific demands [8], [9] (see also the discussion in Section VIII-A).

对照翻译： 这个问题的不同版本已经得到研究，其中主要关注如何利用用户需求的历史或统计信息。在这些论文中，交付阶段被固定为简单的正交单播或组播传输，然后在这种交付方式下优化内容放置。这样获得的增益来自于把热门内容放到本地。另一个研究方向则是在缓存内容固定、需求具体且已知的条件下优化交付阶段。

展开解读：

两类已有工作分别固定了问题的一半：一类先规定如何传，再优化存什么；另一类给定存了什么，再优化如何传。本文把两者联合设计，但不允许放置依赖未来的具体需求。

论文中的“传统方案”应理解为本文用来比较的未编码基准，不能泛化为所有实际缓存系统都只会单播。原文明确包含普通组播；当多人要同一文件时，普通组播本来就能节省流量。

4.4 本地增益与全局增益的区别

原文：

As pointed out above, the gain from traditional uncoded caching approaches derives from making content available locally: if a user requests some content that is stored in its cache, this request can be served from its local memory. We hence call this the local caching gain. This gain is relevant if the local cache memory is large enough such that a sizable fraction of the total (popular) content can be stored locally. On the other hand, if the size of the local caches is small compared to the total amount of content, then this gain is insignificant. In this paper, we propose a novel coded caching approach that, in addition to the local caching gain, is able to achieve a global caching gain. This gain derives from jointly optimizing both the placement and delivery phases, ensuring that in the delivery phase several different demands can be satisfied with a single coded multicast transmission. Since the content placement is performed without knowledge of the actual demands, in order to achieve this gain the placement phase must be carefully designed such that these multicasting opportunities are created simultaneously for all possible requests in the delivery phase. We show that this global caching gain is relevant if the aggregate global cache size is large enough compared to the total amount of content. Thus, even though the caches cannot cooperate, the sum of the cache sizes becomes an important system parameter.

对照翻译： 传统未编码缓存的增益来自于让内容在本地可用：用户请求的内容若已在缓存中，就可以从本地存储器服务。因此，我们称之为本地缓存增益。只有当本地缓存相对于总内容足够大、能够存下相当比例的内容时，这种增益才显著。本文提出的编码缓存方法除了本地增益，还能实现全局缓存增益。它来自放置和交付的联合优化，使交付阶段的一次编码组播满足多个不同需求。由于放置时不知道实际需求，必须精心设计放置，使编码组播机会对所有可能的请求同时成立。当聚合缓存相对于总内容足够大时，这种全局增益就有意义。因此，即使缓存之间不能合作，缓存容量之和仍成为重要的系统参数。

展开解读：

“对所有请求同时成立”不是把所有请求同时服务一次，而是同一套缓存内容能适用于每一种未来请求向量。需求变，广播的 XOR 变，缓存不变。

**“缓存不能合作”指用户之间没有交换数据的链路。**用户只能读取自己的缓存和服务器广播。全局增益通过服务器设计的公共消息实现，不需要用户互相发送缓存内容。

设每个用户缓存占库容量的比例为 $m=M/N$。单个用户只看见 $m$，全体缓存的归一化总量却是 $Km$。因此 $m$ 很小，并不排除 $Km$ 很大。

图 1 原图：

N 个文件，每个文件为 $F$ 比特；它通过共享链路连接 $K$ 个用户，每个用户拥有大小为 $MF$ 比特的独立缓存。目标是设计放置和交付，使共享瓶颈链路上的峰值速率（按文件大小归一化的负载）最小。图中 $N=K=3$、$M=1$。

原文图注：

Fig. 1. Caching system considered in this paper. A server containing N files of size F bits each is connected through a shared link to K users each with an isolated cache of size MF bits. The goal is to design the placement phase and the delivery phase such that the peak rate (i.e. the load normalized by the file size) of the shared bottleneck link is minimized. In the figure, N = K = 3 and M = 1.

图注翻译： 本文考虑的缓存系统：服务器拥有 $N$ 个文件，每个文件为 $F$ 比特；它通过共享链路连接 $K$ 个用户，每个用户拥有大小为 $MF$ 比特的独立缓存。目标是设计放置和交付，使共享瓶颈链路上的峰值速率（按文件大小归一化的负载）最小。图中 $N=K=3$、$M=1$。

读图与分析：

图上方的服务器保存完整文件库。中间共享链路上的信息只发送一份，所有下游用户都能收到；图下方每个缓存只属于相应用户。

这解释了为什么 XOR 有用：同一段广播可以由不同用户结合不同旁信息进行不同的解码。若三条链路必须分别计费且不能共享一次传输，则这里的速率计算不能直接套用。

图中 $M=1$ 表示“可存一个完整文件那么多比特”，不要求缓存必须存一个完整文件。它完全可以存三个文件各自的三分之一。

4.5 引言中的核心速率表达式

原文公式（引言先限制为 $N\ge K$）：

对照翻译： 未编码方案的速率等于用户数乘以每个用户尚未缓存的文件比例。编码方案在此基础上，再乘以一个由全体缓存总量决定的缩减因子。

展开解读：

这里“增益”在原文中写成小于等于 1 的速率乘法因子。若改用“改善多少倍”的语言，对应的是它的倒数。例如全局增益的改善倍数为 $1+KM/N$，不是 $1/(1+KM/N)$ 倍。

适用范围必须记住： 上述编码表达式直接对应 $t=KM/N$ 为整数的构造点。一般实数 $M$ 要通过 memory sharing 得到分段线性速率，不能默认把这个光滑函数当作每一点都已由本定理实现。第六、八章会完整处理。

图 2 原图：

N=30、用户数 $K=30$ 时，交付阶段所需速率 $R$ 随缓存大小 $M$ 的变化；比较本文编码缓存方案与传统未编码缓存。

原文图注：

Fig. 2. Rate R required in the delivery phase as a function of memory size M for N = 30 files and K = 30 users. The figure compares the performance of the proposed coded caching scheme to that of conventional uncoded caching.

图注翻译： 当文件数 $N=30$、用户数 $K=30$ 时，交付阶段所需速率 $R$ 随缓存大小 $M$ 的变化；比较本文编码缓存方案与传统未编码缓存。

读图与分析：

横轴不是总缓存，而是每个用户的缓存容量。纵轴不是比特每秒，而是交付负载除以单文件大小。

在 $M=10$ 时，未编码方案需要

此时 $t=30\cdot 10/30=10$，编码方案需要

因此改善倍数恰为 $11$。原文写成约 $1.8$ 个文件的传输量，是对 $20/11$ 的近似。不是每个用户只收到了 $1.8/30$ 个文件的信息，而是共享广播与各自缓存共同支持恢复。

曲线最左端都从 $30$ 出发，最右端都到达零；编码曲线在中间显著低于未编码直线。这两个端点也提醒我们，“降低约用户数倍”并非对所有缓存大小都成立：$M=0$ 没有任何缓存增益。

重要的一个思想： 放置的价值不仅是提前存下“自己未来会需要”的比特，还包括让自己持有“别人未来可能需要”的旁信息。联合设计的目标，就是让这些旁信息支持同一个广播被多人使用。

五、问题设定（Problem Setting）精读

5.1 非正式模型：文件、缓存、需求和广播

原文：

We consider a system with one server connected through a shared, error-free link to K users, as shown in Fig. 1. The server has access to a database of N files W1,... , WN each of size F bits. Each user k has an isolated cache memory Zk of size MF bits for some real number M ∈ [0,N ]. The system operates in two phases: a placement phase and a delivery phase. In the placement phase, the users are given access to the entire database W1,... , WN of files. Each user k is then able to fill the content of its cache Zk using the database. In the delivery phase, only the server has access to the database of files. Each user k requests one of the files $W_{d_k}$ in the database. The server is informed of these requests and proceeds by transmitting a signal $X_{(d_1,\dots ,d_K)}$ of size $RF$ bits over the shared link for some fixed real number $R$. The quantities $RF$ and $R$ are referred to as the load and the rate of the shared link, respectively. Using the content Zk of its cache and the signal X(d1,...,dk) received over the shared link, each user k aims to reconstruct its requested file Wdk .

对照翻译： 我们考虑一个服务器通过共享无差错链路连接 $K$ 个用户的系统。服务器可以访问包含 $N$ 个文件的数据库，每个文件为 $F$ 比特。用户 $k$ 有一个独立缓存 $Z_k$，大小为 $MF$ 比特，其中 $M\in [0,N]$。系统分放置和交付两个阶段运行：放置时用户可以访问整个文件库并填充缓存；交付时只有服务器可以访问文件库。用户 $k$ 请求文件 $W_{d_k}$。服务器获知请求后，在共享链路上发送大小为 $RF$ 比特的信号 $X_{(d_1,\dots ,d_K)}$。$RF$ 和 $R$ 分别称为链路负载和速率。每个用户利用自身缓存与收到的广播重建所请求文件。

展开解读：

统一记号如下。源 Word 中少数下标被识别成小写 $k$，本文统一把完整需求向量长度写成 $K$。

若每个文件为 100 MB，而 $R=1/2$，表示服务器广播 50 MB，并不表示链路的物理速率是 0.5 Mbps。若物理链路速率为 $C$ 比特/秒，忽略其他开销后的交付时间才是 $RF/C$。

用户可以请求同一个文件，所以需求一共有 $N^K$ 种，不是 $N!$ 种。放置不能依赖 $\mathbf{d}$，交付和解码可以依赖它。

5.2 Example 1：未编码缓存基准

原文：

Example 1 (Uncoded Caching). For a memory size of MF bits, one possible strategy is for each user to cache the same M/N fraction of each file in the placement phase. In the delivery phase, the server simply transmits the remaining 1 − M/N fraction of any requested file over the shared link. Clearly, each user can recover its requested file from the content of its local cache and the signal sent over the shared link. In the worst case the users request different files—the delivery rate for this caching scheme is thus $R_U(M)\triangleq K(1-M/N)\min \{1,N/K\}.$ We refer to this caching strategy as uncoded caching, since both content placement and delivery are uncoded.

对照翻译： 对于大小为 $MF$ 比特的缓存，一种策略是在放置阶段，让每个用户缓存每个文件相同的 $M/N$ 比例。在交付阶段，服务器把每个被请求文件剩余的 $1-M/N$ 比例发到共享链路。用户可以由本地缓存和广播恢复所需文件。最坏情况是用户请求尽可能多的不同文件。我们称此策略为未编码缓存，因为放置和交付都不编码。

展开解读：

当 $N\ge K$ 时，最坏情况有 $K$ 个不同请求；当 $N<K$ 时，最多只有 $N$ 个不同文件需要发送。因此原文式 (1) 为

举例：$N=2,K=5$，即使五个用户发出请求，也只有两种文件，不必发五份。先按文件去重再广播，即可实现自然组播。

这里各用户缓存的是每个文件相同的位置。这让缓存命中容易分析，却没有形成互补旁信息；第七章会改用不同用户存不同子文件。

5.3 严格定义：文件作为独立随机变量

原文：

We now provide the formal definition of the information-theoretic caching problem. Let $(W_n{)}_{n=1}^N$ be $N$ independent random variables each uniformly distributed over $[2^F]\triangleq \{1,2,\dots ,2^F\}$ for some $F\in \mathbb{N}$. Each $W_n$ represents a file of size $F$ bits. A $(M,R)$ caching scheme consists of $K$ caching functions, $N^K$ encoding functions, and $K{N}^K$ decoding functions.

对照翻译： 现在给出缓存问题的信息论形式化定义。令 $W_1,\dots ,W_N$ 为相互独立的随机变量，每个变量在 $[2^F]=\{1,2,\dots ,2^F\}$ 上均匀分布，其中 $F$ 是正整数。每个 $W_n$ 代表一个大小为 $F$ 比特的文件。一个 $(M,R)$ 缓存方案由 $K$ 个缓存函数、$N^K$ 个编码函数及 $K{N}^K$ 个解码函数构成。

展开解读：

均匀分布意味着 $H(W_n)=F$；相互独立意味着

这两项假设排除了文件之间天然可压缩的相关性。否则，速率下降可能来自源压缩，而不能干净地归因于缓存。

$N^K$ 个编码函数并不意味着实现时必须存下 $N^K$ 张查找表；它只是说每一种需求都允许有自己的编码映射。后面的组合算法会统一描述所有这些映射。

5.4 三类函数：方案到底包含什么？

原文定义：

The $K$ caching functions

$${\varphi }_k:[2^F{]}^N\to [2^{\lfloor FM\rfloor }]$$

map the files $W_1,\dots ,W_N$ into the cache content

$$Z_k\triangleq {\varphi }_k(W_1,\dots ,W_N).$$

对照翻译： 第 $k$ 个缓存函数把整个文件库映射到用户 $k$ 的缓存内容，缓存的取值数不超过 $2^{\lfloor FM\rfloor }$。

展开解读： 因而 $H(Z_k)\le \lfloor FM\rfloor \le FM$。缓存可以保存原始比特，也可以保存跨文件的编码函数；定义没有把方案限制为未编码放置。附录正会利用这一点。

原文定义：

The $N^K$ encoding functions

$${\psi }_{\mathbf{d}}:[2^F{]}^N\to [2^{\lfloor FR\rfloor }]$$

map the files $W_1,\dots ,W_N$ to the input

$$X_{\mathbf{d}}\triangleq {\psi }_{\mathbf{d}}(W_1,\dots ,W_N).$$

对照翻译： 对每一个需求向量，服务器的编码函数把整个文件库映射为共享链路输入，其长度不超过约 $FR$ 比特。

展开解读： $X_{\mathbf{d}}$ 随需求变化，但 $Z_k$ 不随需求变化。服务器知道文件库、缓存设计和全部请求，因而能够直接计算广播。即使某一段旁信息位于另一个用户缓存中，也不需要该用户上传它。

原文定义：

Finally, the $K{N}^K$ decoding functions

$${\mu }_{\mathbf{d},k}:[2^{\lfloor RF\rfloor }]\times [2^{\lfloor FM\rfloor }]\to [2^F]$$

map the signal received over the shared link $X_{\mathbf{d}}$ and the cache content $Z_k$ to the estimate

$${\hat{W}}_{\mathbf{d},k}\triangleq {\mu }_{\mathbf{d},k}(X_{\mathbf{d}},Z_k).$$

对照翻译： 每个需求向量和每个用户都有对应解码函数，用广播与本地缓存生成对请求文件的估计。

展开解读： 解码器输入没有 $Z_j$（$j\ne k$）。这正是“独立缓存、用户不能合作”的数学表达。解码映射由需求索引，也说明模型允许解码器知道相关需求信息；实际协议携带索引和子文件标签的开销没有进入这里的主导文件负载。

5.5 错误概率、可实现性与最优速率

原文公式：

对照翻译： 在全部需求与全部用户中，取恢复错误概率的最大值。

展开解读： 这里有两层最坏情况：不能只对热门需求成功，也不能只保证大多数用户成功。概率来自随机文件；不是对需求分布求平均。

原文：

Definition. The pair (M, R) is achievable if for every ε > 0 and every large enough file size F there exists a (M, R) caching scheme with probability of error less than ε. We define the memory-rate tradeoff $R^{\star }(M)\triangleq \inf \{R:(M,R)\text{ is achievable}\}$.

对照翻译： 如果对每个 $\epsilon >0$，以及每个足够大的文件大小 $F$，都存在一个错误概率小于 $\epsilon$ 的 $(M,R)$ 缓存方案，则称 $(M,R)$ 可实现。定义内存—速率权衡为所有可实现速率的下确界。

展开解读：

把定义完整写为

量词顺序是：固定 $M,R,N,K$；任给错误容限；文件足够大时找到方案。它不是“总有某个小文件碰巧可以恢复”。

由定义立即得到几个边界点：

前者在无缓存时必须发送所有被请求的不同独立文件；后者把整个库放到每个缓存即可。$R^{\star }(M)$ 随 $M$ 非增，因为容量变大后仍能使用原来的方案。

本文一般构造是零误差方案，但最优值的比较对象更大：允许编码放置、非线性编码和渐近消失的错误概率。所以下界与 12 倍保证具有信息论意义。

六、主要结果（Main Results）精读

6.1 Theorem 1：一个可实现的速率上界

原文：

Theorem 1. For $N\in \mathbb{N}$ files and $K\in \mathbb{N}$ users each with cache of size $M\in \{0,N/K,2N/K,\dots ,N\}$,

$$R^{\star }(M)\le R_C(M)\triangleq K\left(1-\frac{M}{N}\right)\min \left\{\frac{1}{1+KM/N},\frac{N}{K}\right\}$$

is achievable. For general $0\le M\le N$, the lower convex envelope of these points is achievable.

对照翻译： 当缓存大小属于上述离散集合时，所给速率可实现，因此构成最优速率的上界。对一般实数缓存大小，这些点的下凸包也可实现。

展开解读：

令

各构造点的速率为

第一个候选来自编码组播；第二个候选来自普通未编码缓存和自然组播。定理选择更好的候选，并允许在构造点之间共享内存。

对于非整数 $t$，严格定义可写成下面的优化问题（这是本精读对“下凸包”的展开）：

约束为

这里 ${\lambda }_t$ 是按第 $t$ 个方案处理的文件比例，不是选择该需求的概率。若某个点高于其他点的连线，下凸包会跳过它；不能机械地认为所有情形都直接连接每个相邻原始点。$N\ge K$ 的标准编码点构成凸折线，此时相邻插值即可。

6.2 式 (2)：两个增益为什么相乘？

原文公式：

对照翻译： 在上述构造点上，总速率等于无缓存速率、本地缩减因子和全局缩减因子的乘积。

展开解读： 每个用户原本缺失 $1-M/N$ 个文件的量，$K$ 人一共缺失 $K(1-M/N)$。若每份广播能够同时给 $t+1$ 个用户各带来一份缺失子文件，则总传输量再除以 $t+1=1+KM/N$。

“缺失信息量的总和”可以大于实际广播长度，因为不同用户的条件信息不同；不能把每个用户的新增信息量直接加起来当作广播熵的下界。

例如广播一个比特 $U\oplus V$，知道 $V$ 的用户获得 $U$，知道 $U$ 的用户获得 $V$。广播熵至多一比特，但分别条件于不同旁信息后，两位用户各得到一比特。这不违背信息守恒，也不创造新的源信息。

6.3 Example 2：改善倍数达到 $\Theta (K)$

原文（Example 2）：

Consider a system with the same number of users as files, i.e., $N=K$. Assume each user has enough cache memory for half of the files so that $M=N/2$. Then the local caching gain is $1/2$ and the global caching gain is $1/(1+K/2)$.

对照翻译： 考虑文件数等于用户数的系统，每个用户能缓存半个文件库。本地缩减因子为 $1/2$，全局缩减因子为 $1/(1+K/2)$。

展开解读： 对 $K$ 为偶数的构造点，

两者之比为

因此人数增长时，未编码方案需要发送的量线性增长，而编码方案保持在一个文件的量以下。代价是每个用户都已经缓存了半个文件库，且子分包数量会增长。

当 $K$ 为奇数时，$t=K/2$ 非整数，需在相邻构造点共享内存；仍有相同的 $\Theta (K)$ 改善量级，但不能直接把上述整数构造表达式当作精确的插值速率。例如 $K=N=3,M=1.5$ 时，插值得 $R_C=2/3$，而光滑表达式给出 $3/5$，二者不同。

6.4 Example 3：小缓存处的斜率改善

原文（Example 3）：

From (1), the rate of uncoded caching has a slope of $-1$ around $M=0$. On the other hand, by Theorem 1, the rate of coded caching has a slope less than $-K/2$ around $M=0$.

对照翻译： 在 $N=K$ 时，未编码缓存速率在原点附近的斜率为 $-1$，而编码缓存曲线在原点附近的斜率小于 $-K/2$。

展开推导： 构造点为

连接这两点，得到

所以在 $0\le M\le 1$ 上，

这里算的是实际可实现折线的斜率。直接对 $K(1-M/K)/(1+M)$ 求导，会在原点得到 $-(K+1)$，并不是定理所定义折线的斜率。这个差一倍的错误很常见。

6.5 当 $N<K$：自然组播与编码组播的比较

原文：

The scheme in Theorem 1 achieves the better of these two gains. We point out that for $M\ge 1-N/K$ this minimum is achieved by the first of the two gains.

对照翻译： 定理 1 的方案实现自然组播和编码组播中较好的增益；当 $M\ge 1-N/K$ 时，最小值由编码组播对应的项取得。

展开推导： 在构造点比较两个候选缩减因子，

等价于

因此文件数少于用户数时，很小缓存区域已经存在普通组播收益，不能把无缓存负载直接写成 $K$。所有一般参数的推导都要保留 $\min \{N,K\}$ 或候选最小值。

6.6 Theorem 2：任何方案都必须满足的下界

原文：

Theorem 2. For $N\in \mathbb{N}$ files and $K\in \mathbb{N}$ users each with cache of size $0\le M\le N$,

$$R^{\star }(M)\ge \underset{s\in \{1,\dots ,\min \{N,K\}\}}{\max }\left(s-\frac{s}{\lfloor N/s\rfloor }M\right).$$

对照翻译： 对任意合法系统参数，最优速率至少等于右侧所有割集下界中的最大值。

展开解读： 记右侧为 $R_L(M)$。$s$ 是选取的用户数量；$\lfloor N/s\rfloor$ 是安排这些用户在多个假想需求实例中请求不重复文件时，可安排的完整批次数。

每一个 $s$ 给出一条直线；同时满足所有直线约束，因此要取最大值。$s=1$ 给出

在 $M=0$ 处选 $s=\min \{N,K\}$，得到无缓存精确值。这个定理只是下界，通常并不等于最优值；下一章和附录将给出具体反例。

6.7 Theorem 3：12 倍保证到底说明什么？

原文：

Theorem 3. For $N\in \mathbb{N}$ files and $K\in \mathbb{N}$ users each with cache of size $0\le M\le N$,

$$1\le \frac{R_C(M)}{R^{\star }(M)}\le 12,$$

with the achievable rate $R_C(M)$ of coded caching as defined in Theorem 1.

对照翻译： 本文编码缓存方案的速率不低于最优速率，并且最多是最优速率的 12 倍。

展开解读： 为处理 $M=N$ 时 $0/0$ 没有定义的问题，严格而统一地写成

当 $M<N$ 时再写成比值形式。这个常数不依赖文件数、用户数或缓存大小，所以称为常数因子近似或量级最优。

它不表示“性能误差为 12%”，也不表示每个参数点恰好相差 12 倍。它保证在该模型内，即使允许更复杂编码，也不可能获得相对于本方案随系统规模无限增长的改善倍数。

原文还报告数值计算提示常数可能降到 5。这里的“5”是论文的数值观察，不是本文已经证明的定理。后面的证明必须保留 12，不能用猜测替代。

七、例子（Examples）精读

7.1 Example 4：二文件、二用户的完整权衡图

图 3 原图：

N=K=2 的内存—速率权衡。蓝色实线为定理 1 的可实现速率 $R_C(M)$，红色虚线为定理 2 的下界，黑色点线为该特例的精确最优速率 $R^{\star }(M)$。">

原文图注：

Fig. 3. Memory-rate tradeoff for N = 2 files K = 2 users. The achievable rate RC (M ) of the coded caching scheme from Theorem 1 is indicated by the solid blue curve. The lower bound on $R^{\star }(M)$ from Theorem 2 is indicated by the dashed red curve. For the N = K = 2 case, $R^{\star }(M)$ can be found exactly and is indicated by the dotted black curve.

图注翻译： $N=K=2$ 的内存—速率权衡。蓝色实线为定理 1 的可实现速率 $R_C(M)$，红色虚线为定理 2 的下界，黑色点线为该特例的精确最优速率 $R^{\star }(M)$。

读图与分析：

先看三个不同对象：蓝线是“一个方案能做到”，红线是“任何方案做不到低于它”，黑线才是“真正最优”。蓝线和红线在部分区域之间留有空隙，附录分别改善两侧，最后闭合。

定理 1 的三个构造点是 $(0,2)$、$(1,1/2)$、$(2,0)$。红线是

在 $M=1/2$ 时，蓝线为 $5/4$，红线为 $1$，黑线也为 $1$；上界并未达到最优。在 $M=3/4$ 时，蓝线为 $7/8$，红线为 $5/8$，黑线为 $3/4$；这次上下界都不紧。

因此“常数近似最优”与“逐点精确最优”是两个不同结论，不能混用。

7.2 两个端点：$(0,2)$ 与 $(2,0)$

原文：

We start with the upper bound in Theorem 1, focusing on the corner points of the achievable region. First, let us consider the two extreme cases M = 0 and M = N . If M = 0, the server can always transmit both files A and B over the shared link. Since this satisfies every possible request, the (M, R) pair (0, 2) is achievable. If M = 2, each user can cache both files A and B in the placement phase. Therefore, no communication is needed in the delivery phase and the (M, R) pair (2, 0) is achievable.

对照翻译： 先看两个极端：$M=0$ 时，服务器总可以广播 $A,B$ 两个文件，从而满足任意请求，所以 $(0,2)$ 可实现。$M=2$ 时，每个用户都缓存 $A,B$，交付无需通信，所以 $(2,0)$ 可实现。

展开解读：

极端点是 memory sharing 的锚点，同时也是对模型单位的检查。这里两位用户即使请求相同文件，实际可以少传；但方案所保证的 $R$ 是全部需求中的最大负载。

7.3 关键点 $(M,R)=(1,1/2)$：放置、广播与解码

原文：

Consider then the more interesting corner point at M = 1. The caching scheme achieving the upper bound in Theorem 1 is as follows (see Fig. 4). We split both files A and B into two subfiles of equal size, i.e., A = (A1, A2) and B = (B1, B2). In the placement phase, we set Z1 = (A1, B1) and Z2 = (A2, B2). In words, each user caches one exclusive part of each file. For the delivery phase, assume for example that user one requests file A and user two requests file B. Given that user one already has subfile A1 of A, it only needs to obtain the missing subfile A2, which is cached in the second user’s memory Z2. Similarly, user two only needs to obtain the missing subfile B1, which is cached in the first user’s memory Z1. In other words, each user has one part of the file that the other user needs. The server can in this case simply transmit A2 ⊕B1, where ⊕ denotes bitwise XOR. Since user one already has B1, it can recover A2 from A2⊕B1. Similarly, since user two already has A2, it can recover B1 from A2 ⊕B1. Thus, the signal A2 ⊕B1 received over the shared link helps both users to effectively exchange the missing subfiles available in the cache of the other user.

对照翻译： 考虑 $M=1$。把两个文件各等分为两段，$A=(A_1,A_2)$、$B=(B_1,B_2)$。放置时令 $Z_1=(A_1,B_1)$、$Z_2=(A_2,B_2)$。若用户 1 请求 $A$、用户 2 请求 $B$，前者只缺 $A_2$，后者只缺 $B_1$，而这两段分别位于对方缓存中。服务器广播 $A_2\oplus B_1$；用户 1 利用已知的 $B_1$ 恢复 $A_2$，用户 2 利用已知的 $A_2$ 恢复 $B_1$。

展开解读：

每段长度都是 $F/2$，所以每个缓存的长度为 $F/2+F/2=F$，恰好满足 $M=1$。

解码不能只用一句“做 XOR”带过，具体为

两位用户再分别与 $A_1$、$B_2$ 拼接恢复完整文件。长度为 $F/2$ 的 XOR 仍只有 $F/2$ 比特，不是两个输入长度的和，因此

“交换缺失子文件”是效果上的描述：真正的发送者始终是服务器。

图 4 原图：

N=K=2,M=1 时覆盖全部四种用户请求的缓存策略。每个文件等分为两段：$A=(A_1,A_2)$、$B=(B_1,B_2)$。该方案达到 $R=1/2$。服务器的发送内容随请求变化，而缓存内容不变。">

原文图注：

Fig. 4. Caching strategy for N = 2 files and K = 2 users with cache size M = 1 with all four possible user requests. Each file is split into two subfiles of size 1/2, i.e., A = (A1, A2) and B = (B1, B2). The scheme achieves rate R = 1/2. Observe that, while the transmission from the server changes as a function of the user requests, the cache contents do not.

图注翻译： $N=K=2,M=1$ 时覆盖全部四种用户请求的缓存策略。每个文件等分为两段：$A=(A_1,A_2)$、$B=(B_1,B_2)$。该方案达到 $R=1/2$。服务器的发送内容随请求变化，而缓存内容不变。

读图与分析：

四个子图不是四次连续交付，而是四种可能需求的并列展示。它们共用同一套放置 $Z_1=(A_1,B_1)$、$Z_2=(A_2,B_2)$。

即使两个用户都请求 $A$，他们缺的也是不同半段；一次 XOR 仍能同时补齐。这个例子完整验证了“放置不知道需求”这一要求，而不是只为 $(A,B)$ 设计一个巧合。

7.4 Memory sharing：从离散点到连续缓存大小

原文：

So far, we have shown that the (M, R) pairs at corner points (0, 2), (1, 1/2), and (2, 0) are achievable. On the other hand, by dividing the cache memories and the transmitted signal proportionally, it is easy to see that if any two points (M1, R1) and (M2, R2) are achievable, then the line connecting them is also achievable. Inspired by the term time sharing in network information theory, we refer to this as memory sharing. Memory sharing between the corner points (0, 2), (1, 1/2), and (2, 0) establishes the achievability of the solid blue curve in Fig. 3, which coincides with the upper bound stated in Theorem 1.

对照翻译： 目前已经证明三个角点 $(0,2)$、$(1,1/2)$、$(2,0)$ 可实现。通过按比例划分缓存和传输信号，可以看到：如果两个点 $(M_1,R_1)$、$(M_2,R_2)$ 可实现，则连接它们的线段也可实现。受信息论中 time sharing 的启发，我们称其为 memory sharing。在三个角点之间共享内存，得到图 3 中的蓝色实线，即定理 1 的上界。

展开解读：

关键是把每个文件分成比例为 $\lambda$ 和 $1-\lambda$ 的两部分，而不仅仅是“某些用户用方案 1，其他用户用方案 2”。两部分都服务全部用户的同一次请求。

第一部分采用方案 1，缓存消耗 $\lambda M_{1}F$、发送 $\lambda R_{1}F$；第二部分采用方案 2，消耗 $(1-\lambda )M_{2}F$、发送 $(1-\lambda )R_{2}F$。故

例如 $M=1/2$，让每个文件一半用 $(0,2)$，另一半用 $(1,1/2)$，得到

完整蓝线为

这还不是附录的 $(1/2,1)$；后者用了不同的、编码的放置。

7.5 二用户例子的两条 cut-set 下界

原文：

We continue by analyzing the lower bound on $R^{\star }(M)$ in Theorem 2. The proof relies on the cut-set bound. We consider two cuts. The first cut separates (X(1,2), Z1, Z2) from the two users. Assume (M, R) is an achievable memory-rate pair. Then this cut has capacity at most RF + 2MF , since X(1,2) is at most RF bits by definition of achievability, and since Z1, Z2 contain each MF bits. On the other hand, since the first user can recover A from (X(1,2), Z1) and the second user can recover B from (X(1,2), Z2), the number of bits that need to be transmitted over this cut is at least 2F . Hence, RF + 2MF ≥ 2F, The second cut separates (X(1,2), X(2,1), Z1) from the first user. Note that this user can recover A and B from (X(1,2), Z1) and (X(2,1), Z1), respectively. Hence, this cut yields 2RF + MF ≥ 2F

对照翻译： 第一条割把 $(X_{(1,2)},Z_1,Z_2)$ 与两位用户分开。广播与两个缓存总共至多包含 $RF+2MF$ 比特，而两位用户能恢复两个独立文件，因此至少需要 $2F$ 比特。第二条割把 $(X_{(1,2)},X_{(2,1)},Z_1)$ 与用户 1 分开；同一用户分别通过两个需求下的广播和同一个缓存恢复 $A$ 与 $B$。

展开解读：

第一条割：

第二条割：

第二条不等式最重要的地方是缓存只算一次。放置在需求之前确定，所以两个假想需求下是同一个 $Z_1$。我们没有要求真实系统必须连续发生这两次请求，只是利用“同一方案要支持这两种请求”来构造联合信息约束。

若错误概率只是趋于零，上述右侧应先减去 $o(F)$，最后除以 $F$ 并令文件长度趋于无穷。第九章会补齐这一步。

因此

原文随后指出更强的约束 $R^{\star }(M)\ge 3/2-M$，并将证明放入附录。本精读也保留这个顺序，在第十二章完整证明。

7.6 Example 5：$N=K=3,M=1$ 的两两编码

原文：

Example 5. In this example, we assume that N = K = 3 so that there are three users and three files, say W1 = A, W2 = B, and W3 = C. Again, it is trivial to see that the (M, R) pairs (0, 3) and (3, 0) are achievable. We focus on two nontrivial corner points at M = 1 and M = 2. Consider first caches of size M = 1. We split each file into three subfiles of equal size, i.e., A = (A1, A2, A3), B = (B1, B2, B3), and C = (C1, C2, C3). In the placement phase, the cache content of user k is selected as Zk = (Ak, Bk, Ck). A more formal way to describe this content placement, which is a bit exaggerated for this simple setting but will be useful for the general setting below, is as follows. Let T be a subset of one element of {1, 2, 3}. Then subfiles AT , BT , CT are placed into the cache of user k if k ∈ T . For example, A1 is cached at user one since in this case T = {1}. For the delivery phase, let us consider as an example that user one requests file A, user two requests file B, and user three requests file C. Then the missing subfiles are A2 and A3 for user one, B1 and B3 for user two, and C1 and C2 for user three. Given the cache contents, users one and two aim to exchange A2 and B1, users one and three aim to exchange A3 and C1, and users two and three aim to exchange B3 and C2. The signal (A2 ⊕ B1, A3 ⊕ C1, B3 ⊕ C2) enables all of these three exchanges. All other requests can be satisfied in a similar manner. Since each subfile has rate 1/3, the proposed scheme achieves a rate of 1, and therefore (M, R) pair (1, 1) is achievable. Observe that, through careful content placement, we have again created coded multicasting opportunities for any two users even with different demands. Moreover, these coded multicasting opportunities are available simultaneously for all 27 possible triples of user requests.

对照翻译： 现在令 $N=K=3$，文件为 $A,B,C$，显然 $(0,3)$、$(3,0)$ 可实现。先看 $M=1$：每个文件等分为三段，用户 $k$ 缓存 $(A_k,B_k,C_k)$。对请求 $(A,B,C)$，三位用户分别缺少 $(A_2,A_3)$、$(B_1,B_3)$、$(C_1,C_2)$。广播 $(A_2\oplus B_1,A_3\oplus C_1,B_3\oplus C_2)$ 可以完成三组交换。每段大小为文件的三分之一，总速率为 1。相同的放置为全部 27 种请求都创造了两用户编码组播机会。

展开解读：

把每位用户的解码过程展开：

缓存长度为 $3(F/3)=F$，广播长度也为 $3(F/3)=F$，故 $(M,R)=(1,1)$。

对任意请求索引 $(d_1,d_2,d_3)$，直接广播

索引可以重复，解码仍成立。这给出了全部 $3^3=27$ 种需求的统一规则，而非只验证全不同请求。

7.7 $N=K=3,M=2$：从两人收益到三人收益

原文：

Consider next caches of size $M=2$. We again split each file into three subfiles of equal size. However, it will be convenient to label these subfiles differently, namely $A=(A_{12},A_{13},A_{23})$, $B=(B_{12},B_{13},B_{23})$, and $C=(C_{12},C_{13},C_{23})$.

对照翻译： 再考虑缓存大小 $M=2$。仍把每个文件分成三等份，但改用两元素集合标记子文件。

展开解读： 下标不再只是编号，而是“谁缓存了这一段”的集合。$A_{13}$ 表示用户 1 和用户 3 都缓存了这段。完整放置为

每个用户存六段，每段 $F/3$ 比特，所以缓存为 $2F$。

原文：

This exchange can be enabled by transmitting the signal $A_{23}\oplus B_{13}\oplus C_{12}$ over the shared link. Given its cache content, each user can then recover the missing subfile. All other requests can be satisfied in a similar manner.

对照翻译： 在共享链路发送 $A_{23}\oplus B_{13}\oplus C_{12}$ 即可完成交换。每个用户结合自己的缓存，可以恢复缺失子文件；其他请求也能类似处理。

展开推导： 对需求 $(A,B,C)$，三位用户分别只缺 $A_{23}$、$B_{13}$、$C_{12}$。记广播为 $X$，则

每一行用于消去的两项都位于相应用户缓存中。一份 $F/3$ 比特广播同时服务三人，故

任意请求对应广播

从 $M=1$ 到 $M=2$，不仅每人缺失内容变少，单次广播的受益人数还从 2 增加到 3。这正是本地与全局两个增益同时变化的例子。

图 5 原图：

N=K=3 的内存—速率权衡。蓝色实线为定理 1 的可实现速率，红色虚线为定理 2 的下界。">

原文图注：

Fig. 5. Memory-rate tradeoff for N = 3 files and K = 3 users. The achievable rate RC (M ) of the coded caching scheme from Theorem 1 is indicated by the solid blue curve. The lower bound on $R^{\star }(M)$ from Theorem 2 is indicated by the dashed red curve.

图注翻译： $N=K=3$ 的内存—速率权衡。蓝色实线为定理 1 的可实现速率，红色虚线为定理 2 的下界。

读图与分析：

蓝线依次连接 $(0,3)$、$(1,1)$、$(2,1/3)$、$(3,0)$，即

定理 2 的三个候选分别为

$s=2$ 的直线从不超过另外两条的上包络，所以图中下界可简化为

两条线交于 $M=3/4$。当 $2\le M\le 3$ 时上下界重合，故该区间已知精确最优；其他区间的空隙不能简单理解为本方案实际一定损失了那么多。图 5 没有像图 3 那样给出整个区间的精确黑线。

7.8 三用户例子的下界逐步推导

原文公式及对应恢复关系：

The first cut separates $(X_{(1,2,3)},Z_1,Z_2,Z_3)$ from the three users.

$$RF+3MF\ge 3F.$$

对照翻译： 第一条割把一次广播和三个缓存与用户隔开；这些信息能恢复三个独立文件，因此总容量至少为三个文件的大小。

展开推导：

原文：

The second cut separates $(X_{(1,2,3)},X_{(2,3,1)},X_{(3,1,2)},Z_1)$ from the first user.

$$3RF+MF\ge 3F.$$

对照翻译： 第二条割使用三种需求对应的广播和同一个用户缓存，使用户 1 分别恢复三个文件。

展开推导： 用户 1 的请求依次是 1、2、3，因此联合观察三个广播与 $Z_1$ 后能恢复整个库。缓存只计一次，于是

将两条不等式取最大值，就得到图 5 的红色虚线。例子到这里已经预演了一般割集证明的两种思想：一次服务多个用户，以及多次假想需求复用同一组缓存。

八、编码缓存方案（Proof of Theorem 1）精读

8.1 用整数 $t$ 统一描述所有缓存构造点

原文：

Consider cache size $M\in \{0,N/K,2N/K,\dots ,N\}$, and set

$$t\triangleq MK/N.$$

Observe that $t$ is an integer between $0$ and $K$.

对照翻译： 对上述离散缓存大小，定义整数 $t=MK/N$，它在 0 到 $K$ 之间。

展开解读： $t$ 同时有三种解释：全体缓存容量与文件库容量之比；每个子文件被复制到的用户数；每条编码消息所服务用户数减一。后两种解释来自构造，而不是任意缓存方案都有的性质。

两个端点单独处理：

以下先假设 $1\le t\le K-1$。这避免在计数式中出现 $\left(\genfrac{}{}{0ex}{}{K-1}{-1}\right)$ 等无意义写法。

8.2 放置第一步：按用户子集切分文件

原文：

In the placement phase, each file is split into $\left(\genfrac{}{}{0ex}{}{K}{t}\right)$ nonoverlapping subfiles of equal size. It will be convenient to label the subfiles of file $W_n$ as

$$W_n=(W_{n,\mathcal{T}}:\mathcal{T}\subset [K],|\mathcal{T}|=t).$$

对照翻译： 在放置阶段，把每个文件切成 $\left(\genfrac{}{}{0ex}{}{K}{t}\right)$ 个互不重叠、大小相等的子文件，以所有大小为 $t$ 的用户子集作为标签。

展开解读： 这里 $[K]=\{1,\dots ,K\}$，$\mathcal{T}$ 不是请求集合，而是缓存持有者集合。比如 $K=4,t=2$ 时，标签为

每个文件共有六段，每段 $F/6$ 比特。用户请求可以变化，但这些标签及分段边界在放置时已经确定。

一般情况下单段长度为

这里隐含了等分长度可实现的整除要求。对适当的有限 $F$ 可以精确等分；一般渐近文件长度可用填充和趋于零的额外归一化开销处理，必要时先取任意小速率松弛再利用下确界定义。

8.3 放置第二步：用户 $k$ 缓存所有含 $k$ 的标签

原文：

For each $n\in [N]$, subfile $W_{n,\mathcal{T}}$ is placed in the cache of user $k$ if $k\in \mathcal{T}$.

对照翻译： 对每一个文件，只要用户 $k$ 属于子文件标签集合 $\mathcal{T}$，就把该子文件放入用户 $k$ 的缓存。

展开推导： 固定用户 $k$ 后，标签中已有一个元素 $k$，另外 $t-1$ 个成员从剩余 $K-1$ 个用户中选择，故每个文件在用户 $k$ 处有

段，总共 $N\left(\genfrac{}{}{0ex}{}{K-1}{t-1}\right)$ 段。缓存长度为

这条组合恒等式不是无关的计算：它验证了每位用户都恰好满足缓存约束，而不是只验证全体缓存总量够用。

此外，每个标签恰有 $t$ 个用户，所以每段被复制 $t$ 次。总缓存量既可按用户数算成 $KMF$，也可按子文件复制次数算成 $tNF$，两种计数相等。

8.4 Example 6：一般放置式回到三用户例子

原文：

Let $N=K=3$ and $M=2$. Then $t=2$ and the content placement is

$$Z_1=(W_{n,\{1,2\}},W_{n,\{1,3\}}{)}_{n=1}^3,$$

$$Z_2=(W_{n,\{1,2\}},W_{n,\{2,3\}}{)}_{n=1}^3,$$

$$Z_3=(W_{n,\{1,3\}},W_{n,\{2,3\}}{)}_{n=1}^3.$$

对照翻译： 在三文件三用户、缓存大小 2 的情况下，$t=2$，每个用户缓存每个文件中标签包含自己的两段。

展开解读： 这与第七章的 $A_{12},A_{13},A_{23}$ 完全一致。原文把这个例子再列一次，是为了确认抽象集合记号与可手算的小例子一一对应。

8.5 交付规则：每个 $t+1$ 用户子集发送一个 XOR

原文：

We focus on a subset $\mathcal{S}\subset [K]$ of $|\mathcal{S}|=t+1$ users. Observe that every $t$ users in $\mathcal{S}$ share a subfile in their caches that is needed at the remaining user in $\mathcal{S}$.

For each such subset $\mathcal{S}\subset [K]$ of cardinality $|\mathcal{S}|=t+1$, the server transmits

$$\underset{s\in \mathcal{S}}{⨁}{W}_{d_s,\mathcal{S}\setminus \{s\}}.$$

对照翻译： 考察任意一个包含 $t+1$ 位用户的集合。对集合内每位用户 $s$，其需要的某段内容被其余 $t$ 位用户共同缓存。服务器对每个这样的用户集合，把这些分别缺失的子文件逐比特异或后广播。

展开解读： 固定 $s\in \mathcal{S}$，其中一项为

它满足三个条件：属于用户 $s$ 请求的文件；标签不含 $s$，所以 $s$ 缓存中没有；标签含集合内的其他每个人，所以每个其他用户都知道它。

因此站在任意用户 $k\in \mathcal{S}$ 的角度，整条 XOR 中恰好只有自己的那项未知。站在另一个用户的角度，未知项又不同。这个统一的“每人只差一项”结构，就是放置设计的目的。

8.6 交付负载计算：把全部组合数展开

原文推导：

对照翻译： 总共存在 $\left(\genfrac{}{}{0ex}{}{K}{t+1}\right)$ 个用户子集，每个子集发送一段长为 $F/\left(\genfrac{}{}{0ex}{}{K}{t}\right)$ 的 XOR，所以得到上述总负载。

展开推导：

最后代入 $t=KM/N$，于是 $K-t=K(1-M/N)$。

注意计数对象是广播条数，不是 XOR 项数。每条 XOR 含 $t+1$ 个子文件，但只发一个子文件长度。如果误乘 $t+1$，就恰好把全局增益丢掉了。

8.7 Example 7：一般交付规则回到 $N=K=3,M=1$

原文：

Let $N=K=3$ and $M=1$. Then $t=1$ and the content placement is $Z_k=(W_{n,\{k\}}{)}_{n=1}^3$. For request $(d_1,d_2,d_3)=(1,2,3)$, the signal transmitted in the delivery phase is

$$X_{(1,2,3)}=(W_{1,\{2\}}\oplus W_{2,\{1\}},W_{1,\{3\}}\oplus W_{3,\{1\}},W_{2,\{3\}}\oplus W_{3,\{2\}}).$$

对照翻译： 对三文件三用户、缓存为 1 的系统，$t=1$，每个用户缓存以自己编号为标签的一段。请求分别为文件 1、2、3 时，广播上述三条 XOR。

展开解读： 三条消息分别对应 $\mathcal{S}=\{1,2\}$、$\{1,3\}$、$\{2,3\}$。所以第七章看似手工配对的三次交换，其实就是遍历所有大小为 $t+1$ 的集合。

8.8 完整解码证明：不只证明“某一段能解”

原文：

Since each user $k\in \mathcal{S}$ already has access to the subfiles $W_{d_s,\mathcal{S}\setminus \{s\}}$ for all $s\in \mathcal{S}\setminus \{k\}$, it can solve for $W_{d_k,\mathcal{S}\setminus \{k\}}$ from the signal sent over the shared link.

对照翻译： 用户 $k$ 已知该 XOR 中属于其他用户的所有子文件，因此可解出自己的缺失子文件。

展开证明： 对所有 $s\ne k$，因为 $k\in \mathcal{S}\setminus \{s\}$，相应项属于 $Z_k$，故

接下来还要证明每个缺失标签都会出现。用户 $k$ 的缺失段标签满足

对任一这样的 $\mathcal{T}$，选择唯一集合

服务器必定发送对应消息，其中属于 $k$ 的项正是 $W_{d_k,\mathcal{T}}$。因此所有缺失段均能恢复。标签含 $k$ 的其余段已经在缓存中，于是整个文件恢复完成。

子文件数量也闭合：

该论证没有用到 $d_i\ne d_j$，因此对全部 $N^K$ 种需求成立。

8.9 Algorithm 1：原算法、翻译与执行含义

原算法版面：

原文算法（排版整理，数学记号与原算法一致）：

procedure PLACEMENT(W₁, …, W_N)
    t ← MK/N
    T ← {T ⊂ [K] : |T| = t}
    for n ∈ [N] do
        split Wₙ into (Wₙ,T : T ∈ T) of equal size
    end for
    for k ∈ [K] do
        Zₖ ← (Wₙ,T : n ∈ [N], T ∈ T, k ∈ T)
    end for
end procedure

procedure DELIVERY(W₁, …, W_N, d₁, …, d_K)
    t ← MK/N
    S ← {S ⊂ [K] : |S| = t + 1}
    X_(d₁,…,d_K) ← (⊕_{k∈S} W_(dₖ,S\{k}) : S ∈ S)
end procedure

对照翻译： 放置过程先计算 $t$、枚举所有 $t$ 元标签并等分每个文件，再把含用户编号的所有子文件放入该用户缓存。交付过程枚举所有 $t+1$ 元用户集合，为每个集合生成一条 XOR，并把这些 XOR 拼成公共广播。

展开解读： 为避免伪代码中字母集合和单个集合混淆，可用 $\mathcal{T}$、$\mathcal{S}$ 表示“集合的集合”，用 $\mathcal{T}$、$\mathcal{S}$ 表示其中的元素。算法本身不需要知道未来需求；只有第二个过程才接收 $\mathbf{d}$。

原算法针对 $0<t<K$ 的整数构造点。完整定理还需补上端点、与未编码基准取较小值、以及一般 $M$ 的内存共享。这三项不能从伪代码中省略后就声称已经实现所有参数。

8.10 定理 1 的闭环与零误差性质

原文：

Observe that the placement phase of the algorithm is designed such that, in the delivery phase, the caches enable coded multicasting between MK/N +1 users with different demands. These coded multicasting opportunities are available simultaneously for all N K possible user demands. This is again critical, since the placement phase has to be designed without knowledge of the actual demands in the delivery phase. We also point out that while the problem setting allows for vanishing probability of error as F → ∞, the achievable scheme presented here actually has zero error probability for finite F .

对照翻译： 算法的放置阶段使缓存能够在交付阶段支持 $MK/N+1$ 位、可能请求不同文件的用户之间的编码组播。这种机会对全部 $N^K$ 种可能需求同时成立，这是放置阶段不知道实际需求时的关键。另外，尽管问题设定允许 $F\to \infty$ 时错误概率趋于零，这里给出的方案对于适当的有限文件长度实际上具有零错误概率。

展开解读：

因此定理 1 的证明闭环是：缓存长度合法 → 每条广播长度可计数 → 每个用户解出全部缺失段 → 对所有需求成立 → 获得可实现点 → 共享内存补齐连续容量。

它还暴露一个实践成本：每个文件要切成 $\left(\genfrac{}{}{0ex}{}{K}{t}\right)$ 段，服务器要构造 $\left(\genfrac{}{}{0ex}{}{K}{t+1}\right)$ 条消息。当 $t$ 接近 $K/2$ 时，子分包数量很大。论文证明的是速率与内存的最优量级，没有把子分包和计算成本一起优化。

九、最优速率下界（Proof of Theorem 2）精读

9.1 为什么需要跨需求的割集？

原文：

Let $s\in \{1,\dots ,\min \{N,K\}\}$ and consider the first $s$ caches $Z_1,\dots ,Z_s$. There exists a user demand and a corresponding input to the shared link, say $X_1$, such that $X_1$ and $Z_1,\dots ,Z_s$ determine the files $W_1,\dots ,W_s$. Similarly, there exists an input to the shared link, say $X_2$, such that $X_2$ and $Z_1,\dots ,Z_s$ determine the files $W_{s+1},\dots ,W_{2s}$.

对照翻译： 选取前 $s$ 个用户的缓存。存在一种需求，使相应广播 $X_1$ 和这些缓存足以恢复前 $s$ 个文件；再存在另一种需求，使广播 $X_2$ 和同一组缓存恢复接下来的 $s$ 个文件。

展开解读： 如果只看一次需求，可得 $R+sM\ge s$。它在缓存略大后很快失去约束力，因为把 $s$ 个缓存的全部容量一次性抵扣了。

但同一缓存要支持许多不同需求，不能在每一种需求下都被当作一份全新信息。因此把不同需求对应的广播放在一起，而缓存只保留一份，会得到更强约束。

令

第 $j$ 个假想需求中，令前 $s$ 位用户依次请求

其他 $K-s$ 个用户的需求可任意合法指定。每个需求都必须由同一个可实现方案满足，故这些广播函数全都存在。

图 6 原图：

s=2 对应的割。图中 $N=K=4$，$X_1=X_{(1,2,3,4)}$，$X_2=X_{(3,4,2,1)}$。">

原文图注：

Fig. 6. Cut corresponding to parameter s = 2 in the proof of the converse. In the figure, N = K = 4, and X1 = X(1,2,3,4) , X2 = X(3,4,2,1) .

图注翻译： 下界证明中参数 $s=2$ 对应的割。图中 $N=K=4$，$X_1=X_{(1,2,3,4)}$，$X_2=X_{(3,4,2,1)}$。

读图与分析：

第一种需求下，用户 1、2 分别从 $X_1$ 和自身缓存恢复 $W_1,W_2$。第二种需求下，同两位用户从 $X_2$ 和相同缓存恢复 $W_3,W_4$。

图中的四个恢复节点表示跨需求实例恢复的四个文件，不要误读成“现在给四个用户只保留两个缓存”。它是证明用的组合恢复网络。

所以 $(X_1,X_2,Z_1,Z_2)$ 足以恢复四个独立文件，得到