betaFeedback

WorksComputer Science

Hotplug Coded Caching: Embedding the YMA and Interference Elimination Schemes via Reed–Muller Codes

Abstract

In the hotplug coded caching model, KK users fill their caches of size MM as a function of NN files, but only an unknown subset of A<KA<K users is active in the delivery phase. We recently showed that (i) under uncoded placement, offline users cause a strict load penalty at intermediate memory sizes, so that coded placement is needed; and (ii) for AM≤NAM\leq N, every classical scheme with row-wise placement, including the scheme of Gomez-Vilardebo (GV), can be embedded in a Reed-Solomon code, which removes the penalty. In this note, we show that every point of the scheme of Yu, Maddah-Ali and Avestimehr (YMA) for a classical system with AA users is achievable in the hotplug model for every K≥AK\geq A. Each user is associated with a hyperplane and each file with a homogeneous polynomial; each user caches the restriction of the polynomial to its hyperplane, and the subfiles seen by the active users are the values of the polynomial at the points where their hyperplanes meet. This is a projective Reed-Muller code, which reduces to the Reed-Solomon code when each subfile is cached by one user. We then show, by an existence argument, that every classical scheme whose cache is a linear compression of the Maddah-Ali-Niesen cache and whose correctness holds for generic coefficients can also be embedded over a sufficiently large field; this includes the interference elimination (IE) schemes of Tian and Chen. These embeddings complement the Reed-Solomon one, which allows any row-wise placement and any delivery. Together with past work, our results show that every point attained by a GV, YMA or IE scheme (N≤AN\leq A for IE), and every corner point of the linear tradeoff for A=N=3A=N=3, is achievable in the hotplug model with a load that does not depend on KK. Whether the optimal hotplug tradeoff depends only on AA remains open, but these results support a positive answer.

Introduction

Coded caching [1] studies a server with NN files connected through a shared link to KK users with caches of size MM files. We call a system classical if all the users that take part in the placement phase also take part in the delivery phase, and hotplug if only AA of the K>AK > A users that took part in the placement phase are active in the delivery phase, where the set of active users is unknown at the time of placement.

The hotplug model was introduced by Ma and Tuninetti [10], who proposed schemes with a placement phase based on Maximum Distance Separable (MDS) codes. In all regimes where these schemes could be shown to be optimal, the optimal tradeoff of the hotplug model coincides with that of a classical system with AA users; in particular, it does not depend on KK. Whether this holds in general was posed as an open question [10, 11], and it remains open.

To make progress on this open question, in [12] we showed that, under uncoded placement, this is not the case: the optimal scheme under uncoded placement is the natural extension of the scheme of Yu, Maddah-Ali and Avestimehr (YMA) [2], in which the offline users are assigned the demands of active users, and its load is strictly larger than that of a classical system with AA users at intermediate memory sizes. Hence, to attain the classical load in the hotplug model, coded placement is needed in general. The coded placement schemes in [12] cover the small memory regime AM≤NAM \le N, where a classical system with AA users admits row-wise placements (RWP), meaning that each file is split into AA rows, and the cache of user a∈[A]a \in[A] is a function of row aa of every file. Any such classical RWP scheme can be embedded in a Reed–Solomon code: in the hotplug model, user k∈[K]k \in[K] caches the same function of a coded row, namely the evaluation at a point αk\alpha_k of the polynomial whose coefficients are the rows; once the active users are known, their coded rows are the rows of an invertible transformation of the library, and the classical delivery applies [12 Theorem 2]. Thus, both the scheme of Gómez-Vilardebó (GV) [6] and the YMA point with AM=NAM = N (i.e., one cached row per file) are achievable in the hotplug model for every K≥AK \ge A. This note shows that something similar can be done at larger memory sizes.

Contributions

We give three results:

  1. First, an explicit construction: every YMA point of a classical system with AA users can be embedded in the hotplug model by means of a Reed–Muller code (Theorem 4); hence, the YMA tradeoff for AA users is achievable in the hotplug model for every K≥AK \ge A.

  1. Second, an existence result: on top of the same construction, a generic linear compression of the MAN cached data embeds every classical scheme whose cache is a linear compression of a MAN cache and whose correctness holds for generic coefficients (Theorem 5); this includes the IE scheme [7]. As a consequence, the hotplug tradeoff with 4 active users and 2 files equals the classical one wherever the latter is known (Corollary 4).

  1. Finally, for A=N=3A = N = 3, we give a placement, row-wise up to one common subfile per file, that attains the point (35,32)\left(\frac{3}{5}, \frac{3}{2}\right) of Cao and Xu [9] and embeds via the Reed–Solomon code (Proposition 1); to the best of our knowledge, no scheme that attains this point is known for other values of NN and AA. As a consequence, under linear coding in both placement and delivery, the hotplug tradeoff with 3 active users and 3 files equals the classical one for every K≥3K \ge3 (Proposition 1).

Paper organization

We first state the hotplug model and existing results (§ 2) and summarize novel results (§ 3), then explain the explicit construction by examples (§ 4 and § 5). We then prove Theorem 4 (§ 6) for projective Reed–Muller codes, and also give an equivalent description in terms of symmetric polynomials. We then explain why an exact embedding is limiting and prove Theorem 5 (§ 7). Finally, we settle the linear-optimal point (M,R)=(35,32)(M, R) = \left(\frac{3}{5}, \frac{3}{2}\right) for A=N=3A = N = 3 (§ 8).

Notation

Calligraphic symbols denote sets, bold symbols vectors and matrices, and sans-serif symbols system parameters. (ab)=0\binom{a}{b} = 0 unless a≥b≥0a \ge b \ge0. For integers a≤ba \le b, [a:b]:={a,…,b}[a:b] := \{a,\ldots,b\} and [b]:=[1:b][b] := [1:b]. For a set G\mathcal{G}, ΩtG:={T⊆G:∣T∣=t}\Omega_t^{\mathcal{G}} := \{T \subseteq\mathcal{G} : |T| = t\}. For a set I⊆N\mathcal{I} \subseteq\mathbb{N}, XI:=(Xn:n∈I)X_{\mathcal{I}} := (X_n : n \in\mathcal{I}), and d[I]\mathbf{d}[\mathcal{I}] is the sub-vector of d\mathbf{d} restricted by I\mathcal{I}.

Model and Known Results

Hotplug model

A server has NN independent files F1,…,FNF_1,\ldots,F_N, each of BB i.i.d. uniform symbols over a finite field Fq\mathbb{F}_q; for entropies, logarithms are in base qq. In the placement phase, user k∈[K]k \in[K] stores ZkZ_k, a function of the files, with H(Zk∣F[N])=0H(Z_k \mid F_{[N]}) = 0 and H(Zk)≤MBH(Z_k) \leq MB. In the delivery phase, the users in I∈Ω[K]A\mathcal{I} \in\Omega_{[K]}^{A} are active, and active user kk requests file dk∈[N]d_k \in[N]; the server sends XX, with H(X∣F[N],I,d[I])=0H(X \mid F_{[N]}, \mathcal{I}, d[\mathcal{I}]) = 0 and H(X)≤RBH(X) \leq RB, and every active user decodes its requested file as H(Fdk∣X,Zk,I,d[I])=0H(F_{d_k} \mid X, Z_k, \mathcal{I}, d[\mathcal{I}]) = 0 for all k∈Ik \in\mathcal{I}. The pair (M,R)(M, R) is achievable if there is a scheme, for some BB and qq, that satisfies these constraints for every I∈Ω[K]A\mathcal{I} \in\Omega_{[K]}^{A} and every d[I]∈[N]Ad[\mathcal{I}] \in[N]^{A}. We denote by R(A,K,N)⋆(M)R^{\star}_{(A,K,N)}(M) the optimal hotplug worst-case load, i.e., the infimum of RR over achievable pairs (M,R)(M, R). The case K=AK = A is the classical coded caching model.

A placement is uncoded if each user stores a subset of the symbols of the files, without coding. We denote by Ru(A,K,N)⋆(M)R^{\star}_{u(A,K,N)}(M) the optimal hotplug worst-case load under uncoded placement.

A scheme is linear if every cache ZkZ_k, k∈[K]k \in[K], and every transmission XX, for every I\mathcal{I} and d[I]d[\mathcal{I}], is a linear function of (F1,…,FN)(F_1,\ldots,F_N) over Fq\mathbb{F}_q, i.e., placement and delivery are both linear codes. We denote by Rlc(A,K,N)⋆(M)R^{\star}_{\mathrm{lc}(A,K,N)}(M) the optimal hotplug worst-case load over linear schemes, over all BB and qq.

Since uncoded placement is linear, and the optimal delivery under uncoded placement is linear (Theorem 2), we have R(A,K,N)⋆≤Rlc(A,K,N)⋆≤Ru(A,K,N)⋆≤r:=min⁡(A,N)R^{\star}_{(A,K,N)} \leq R^{\star}_{\mathrm{lc}(A,K,N)} \leq R^{\star}_{u(A,K,N)} \leq r := \min(A,N).

Known Results for classical coded caching

The YMA scheme for classical coded caching

For a classical system with AA users and t∈[0:A]t \in[0:A], the placement of Maddah-Ali and Niesen (MAN) [1] splits each file into (At)\binom{A}{t} subfiles, Fn=(Fn,W:W∈Ω[A]t)F_n = (F_{n,\mathcal{W}} : \mathcal{W} \in\Omega_{[A]}^{t}), and user aa stores Fn,WF_{n,\mathcal{W}} for all nn and all W∋a\mathcal{W} \ni a. With the delivery of [2], this achieves

(MtYMA,RtYMA)=(NtA,(At+1)−(A−rt+1)(At)),t∈[0:A],r:=min⁡(A,N),(1)\left(M_t^{\mathrm{YMA}},R_t^{\mathrm{YMA}}\right)=\left(\frac{Nt}{A},\frac{\binom{A}{t+1}-\binom{A-r}{t+1}}{\binom{A}{t}}\right),\quad t\in[0:A],\quad r:=\min(A,N), \tag*{(1)}

and the lower convex envelope of these points is optimal under uncoded placement [2, 4].

The GV scheme for classical coded caching

The GV scheme [6] for AA users has a RWP: it further splits each row into pieces indexed by the gg-subsets of [N][N] and caches sums of pieces of gg distinct files of the same row; it achieves the lower convex envelope of (0,r)(0,r) and the points

(MgGV,RgGV)=(NAg,r−N(r+1)A(g+1)(rg)(Ng)),g∈[N],r:=min⁡(A,N).(2)\left(M_g^{\mathrm{GV}},R_g^{\mathrm{GV}}\right)=\left(\frac{N}{A^g},r-\frac{N(r+1)}{A(g+1)}\frac{\binom{r}{g}}{\binom{N}{g}}\right),\quad g\in[N],\quad r:=\min(A,N). \tag*{(2)}

For g=N≤Ag=N\leq A, this is the CFL point (1A,N(1−1A))\left(\frac{1}{A},N\left(1-\frac{1}{A}\right)\right) [5], which caches ∑nFn,k\sum_n F_{n,k}. For g=1g=1, this is the YMA point with t=1t=1, (NA,r−r(r+1)2A)\left(\frac{N}{A},r-\frac{r(r+1)}{2A}\right), which caches the row itself. The line through (0,N)(0,N) and the CFL point is optimal for N≤AN\leq A [5]. The line through the CFL point and the GV point with g=N−1g=N-1, i.e., M=NA(N−1)M=\frac{N}{A(N-1)}, is optimal for ⌈(A+1)/2⌉≤N≤A\lceil(A+1)/2\rceil\leq N\leq A [15]; for N=AN=A, the optimality of that GV point was shown in [6].

The IE scheme for classical coded caching

For a classical system with AA users, N≤AN \le A and t∈[0:A]t \in[0:A], the IE scheme uses the same split as the MAN placement, Fn=(Fn,W:W∈Ω[A]t)F_n = (F_{n,\mathcal{W}}:\mathcal{W} \in\Omega_{[A]}^t), but user aa does not store its P:=N(A−1t−1)P := N\binom{A-1}{t-1} subfiles (Fn,W:n∈[N],W∋a)(F_{n,\mathcal{W}}:n \in[N],\mathcal{W} \ni a); it stores fewer linear combinations of them, namely the parity symbols of a systematic code (a rank-metric code in [7]) that encodes them. These combinations mix subfiles of different files and with different indices W\mathcal{W}. In the delivery, the server sends uncoded the subfiles that are not present at any user requesting the same file, together with parity symbols of MDS codes that encode groups of subfiles of the same file; each user first uses the received symbols to eliminate, from its cached combinations, the subfiles of the files it does not request (the interference), and then decodes the subfiles of its requested file. This achieves

References

  1. [1]M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE Trans. Inf. Theory, vol. 60, no. 5, pp. 2856–2867, 2014.
  2. [2]Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “The exact rate-memory tradeoff for caching with uncoded prefetching,” IEEE Trans. Inf. Theory, vol. 64, no. 2, pp. 1281–1296, 2018.
  3. [3]Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Characterizing the rate-memory tradeoff in cache networks within a factor of 2,” IEEE Trans. Inf. Theory, vol. 65, no. 1, pp. 647–663, 2019.
  4. [4]K. Wan, D. Tuninetti, and P. Piantanida, “An index coding approach to caching with uncoded cache placement,” IEEE Trans. Inf. Theory, vol. 66, no. 3, pp. 1318–1332, 2020.arxiv.org/abs/2001.04810
  5. [5]Z. Chen, P. Fan, and K. B. Letaief, “Fundamental limits of caching: Improved bounds for users with small buffers,” IET Commun., vol. 10, no. 17, pp. 2315–2318, 2016.DOI
  6. [6]J. Gómez-Vilardebó, “Fundamental limits of caching: Improved rate-memory tradeoff with coded prefetching,” IEEE Trans. Commun., vol. 66, no. 10, pp. 4488–4497, 2018.
  7. [7]C. Tian and J. Chen, “Caching and delivery via interference elimination,” IEEE Trans. Inf. Theory, vol. 64, no. 3, pp. 1548–1560, 2018.
  8. [8]C. Tian, “Symmetry, outer bounds, and code constructions: A computer-aided investigation on the fundamental limits of caching,” Entropy, vol. 20, no. 8, p. 603, 2018.DOI
  9. [9]D. Cao and Y. Xu, “Characterizing linear memory-rate tradeoff of coded caching: The (N, K) = (3, 3) case,” arXiv:2005.05548, 2020.arxiv.org/abs/2005.05548
  10. [10]Y. Ma and D. Tuninetti, “On coded caching systems with offline users,” in Proc. IEEE ISIT, pp. 1133–1138, 2022; arXiv:2202.01299.arxiv.org/abs/2202.01299
  11. [11]Y. Ma and D. Tuninetti, “On coded caching systems with offline users, with and without demand privacy against colluding users,” arXiv:2401.06894, 2024.arxiv.org/abs/2401.06894
  12. [12]D. Tuninetti, “Hotplug coded caching: Uncoded versus row-wise coded placements,” submitted to ICC 2027 and available on arXiv:2611.03045, 2026.arxiv.org/abs/2611.03045
  13. [13]J. T. Schwartz, “Fast probabilistic algorithms for verification of polynomial identities,” J. ACM, vol. 27, no. 4, pp. 701–717, 1980.DOI
  14. [14]R. Zippel, “Probabilistic algorithms for sparse polynomials,” in Proc. EUROSAM, LNCS vol. 72, pp. 216–226, 1979.DOI
  15. [15]Vijith Kumar K P, B. K. Rai, and T. Jacob “The exact rate memory tradeoff for small caches with coded placement,” arXiv:2102.04797, 2021.
  16. [16]G. Lachaud, “The parameters of projective Reed–Muller codes,” Discrete Math., vol. 81, no. 2, pp. 217–221, 1990.DOI
  17. [17]A. B. Sørensen, “Projective Reed–Muller codes,” IEEE Trans. Inf. Theory, vol. 37, no. 6, pp. 1567–1576, 1991.DOI

Paper details

vlnc:W_su4hw25u
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents