betaFeedback

WorksComputer Science

Hotplug Coded Caching: Uncoded versus Row-Wise Coded Placements

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\leq K users is active in the delivery phase. In all regimes where the optimal hotplug tradeoff is known, it depends only on AA, not on KK; whether this holds in general is open. We show that: (i) Under uncoded placement, YMA delivery with MAN placement, where offline users are assigned the demands of active users, is optimal. Hence, offline users cause a strict load penalty at intermediate memory sizes, while the MAN placement is optimal for every number of active users; (ii) Under row-wise placement (RWP), where each cache is a function of the user's own row of each file, every classical scheme can be embedded in a Reed-Solomon code. The resulting hotplug scheme has the tradeoff of the classical model with AA users, for every A≤KA\leq K: there is no load penalty, but the placement depends on KK. We then derive a converse for RWP, which shows that: (a) for 2≤N≤A2\leq N\leq A, the scheme of Gomez-Vilardebo (GV) is RWP optimal for AM≤N/(N−1)AM\leq N/(N-1), which settles the RWP tradeoff for N=2N=2; (b) YMA is RWP optimal at AM=NAM=N; and (c) for N=A=3N=A=3, GV is RWP optimal for M≤1M\leq 1. Hence, the Reed-Solomon embeddings of these schemes are optimal among embedded RWP schemes.

Introduction

Classical coded caching trades off network load for storage at the end users. Maddah-Ali and Niesen [1] introduced a shared-link model with cache-aided users, and proposed a scheme with an uncoded combinatorial placement and a coded delivery (referred to as MAN), which is to within a constant factor of a cut-set bound. Let KK be the number of users, NN the number of files, and M∈[0,N]M \in[0,N] the cache size. Under the constraint of uncoded placement, the exact worst-case memory-load tradeoff was characterized by Wan et al. [2] for N≥KN \ge K, through an acyclic index coding converse, and by Yu et al. [3] for all NN and KK; the YMA scheme of [3] is also optimal to within a factor of two without restrictions on the placement [4]. Coded placement strictly improves on uncoded placement at small memory sizes: the scheme of Chen, Fan and Letaief (CFL) [5] is optimal for KM≤1KM \le1 when N≤KN \le K, and the scheme of Gómez-Vilardebó (GV) [6] is optimal for KM≤N/(N−1)KM \le N/(N - 1) when ⌈(K+1)/2⌉≤N≤K\lceil(K + 1)/2\rceil\le N \le K [7]. Linear coded placement schemes based on rank-metric codes were developed in [8, 9], which outperform YMA and GV in some regimes; [10, 19] derived computer-aided converse bounds.

The classical model requires every user that took part in the placement phase to also take part in the delivery phase. In [11] we introduced the hotplug model, in which only AA of the KK users are active in the delivery phase, and the identity of the active users is unknown at the time of placement. In [11, 12] we proposed schemes based on Maximum Distance Separable (MDS) coded placement that are exactly optimal in the small and large memory regimes, and optimal to within a factor of two otherwise. In all cases where we could establish exact optimality, the optimal hotplug tradeoff depends only on the number of active users AA, and not on the total number of users KK; whether this holds in general was left open. Hotplug placement delivery arrays were proposed in [13, 14]; their algorithms provide examples of tradeoffs that outperform the baseline scheme in [11], but no closed-forms are available.

Models of random users’ inactivity have also been proposed [15, 16], which cannot be compared to hotplug. Decentralized placement [17] is compatible with hotplug, since the placement does not depend on which users, or how many, will be active; the decentralized load is the limit of the centralized load when the number of users tends to infinity.

Main Contributions

(1) Uncoded placement. We show that the extension of YMA in [11] (referred to as YMA+), in which the offline users are assigned the demands of the active users, is optimal under uncoded placement (Theorem 1). Hence, under uncoded placement and when min⁡(A,N)≥2\min(A,N) \ge2, a system with A<KA < K active users pays a strict load penalty at intermediate memory sizes with respect to a classical system with AA users (Corollary 1). Moreover, the MAN placement is universal: it is optimal for every number of active users (Corollary 2). The penalty is thus in the load only: the active users do not see the symmetric MAN placement structure of AA users, but the restriction of a KK-user structure to an unknown subset. Hence, matching the classical load with AA users requires coded placement.

(2) Reed–Solomon embedding of RWP placement (RWP). In an RWP for a classical system (i.e., K=AK = A), each file is a matrix with AA rows, and the cache of a user is a function of its row of every file; the caches are thus independent and M≤N/AM \le N/A. We show that every classical RWP scheme can be embedded in a Reed–Solomon code, which yields a hotplug scheme for every K≥AK \ge A whose memory-load tradeoff is the same as that of the classical model (Theorem 2), i.e., there is no load penalty for offline users. This greatly generalizes some schemes of [11] and gives a tradeoff complementary to that of uncoded placement: the placement depends on both AA and KK, but the load depends only on $A. (3) Converse for RWP placement. We then ask how good RWP is. We derive a converse bound for RWP in the classical model (Theorem 3), in the spirit of the acyclic index coding bound for uncoded placement [2]. It shows that, for every 2≤N≤A2 \le N \le A, the GV scheme is optimal among RWP schemes for AM≤1+1/(N−1)AM \le1 + 1/(N-1); thus the RWP tradeoff is fully characterized for N=2N = 2. It also shows that the YMA point with one cached subfile per file, at AM=NAM = N, is RWP optimal for every NN and AA (Corollary 4). For N=A=3N = A = 3, a separate converse shows that the GV scheme is optimal among RWP schemes for AM≤NAM \le N (Theorem 4). Consequently, the Reed–Solomon embeddings of these schemes are optimal among embedded RWP schemes for every K≥AK \ge A (Corollary 5).

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}} := \{\mathcal{T} \subseteq\mathcal{G}: |\mathcal{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}.

Problem Setting

An (A,K,N)(A,K,N) hotplug model consists of a server with NN files and KK cache-aided users connected to the server via a shared link. File FnF_n, n∈[N]n \in[N], contains BB i.i.d. uniformly distributed symbols over Fq\mathbb{F}_q, for a prime power qq. In the placement phase, the server fills ZkZ_k, the cache of user k∈[K]k \in[K], as

H(Zk∣F[N])=0,H(Zk)≤M.(1)H(Z_k \mid F_{[N]}) = 0,\qquad H(Z_k) \le M. \tag*{(1)}

In the delivery phase, a set I∈ΩA[K]\mathcal{I} \in\Omega_A^{[K]} of users is active, unknown at the time of placement; active user k∈Ik \in\mathcal{I} requests file dk∈[N]d_k \in[N]. The server sends XX as

H(X∣F[N],I,d[I])=0,H(X)≤R.(2)H(X \mid F_{[N]},\mathcal{I},\mathbf{d}[\mathcal{I}]) = 0,\qquad H(X) \le R. \tag*{(2)}

Every active user decodes its demanded file as

H(Fdk∣X,Zk,I,d[I])=0,∀k∈I.(3)H(F_{d_k} \mid X,Z_k,\mathcal{I},\mathbf{d}[\mathcal{I}]) = 0,\qquad\forall k \in\mathcal{I}. \tag*{(3)}

The optimal worst-case load R(A,K,N)∗(M)R^*_{(A,K,N)}(M) is the infimum of the achievable RR over all qq, BB and schemes that satisfy (1), (2) and (3) for every I\mathcal{I} and d[I]\mathbf{d}[\mathcal{I}]. The case A=KA = K is the classical MAN model with AA users. We let r:=min⁡(A,N)r := \min(A,N).

Uncoded placement: If every cache is a subset of the symbols of the files, the placement is said to be uncoded, and the optimal worst-case load is Ru(A,K,N)∗(M)≥R(A,K,N)∗(M)R^*_{\mathrm{u}(A,K,N)}(M) \ge R^*_{(A,K,N)}(M).

RWP placement: For a classical system with AA users, a placement is RWP if each file is split into AA rows, Fn=(Fn,1,…,Fn,A)F_n = (F_{n,1},\ldots,F_{n,A}), n∈[N]n \in[N], and the cache of user k∈[A]k \in[A] is a function of the kk-th row of every file, i.e., Zk=ϕ(F1,k,…,FN,k)Z_k = \phi(F_{1,k},\ldots,F_{N,k}), where using the same function ϕ\phi at every user is without loss of generality [10]. Since a row has entropy N/AN/A, RWP is restricted to AM≤NAM \le N. The optimal RWP load is denoted by Rrow(A,N)∗(M)≥R(A,A,N)∗(M)R^*_{\mathrm{row}(A,N)}(M) \ge R^*_{(A,A,N)}(M). RWP may be uncoded, and uncoded placement can be RWP, thus, no general ordering between Rrow(A,N)∗R^*_{\mathrm{row}(A,N)} and Ru(A,A,N)∗R^*_{\mathrm{u}(A,A,N)} exists.

Known Results

YMA+ (uncoded) scheme MT2022offline for hotplug

For KK users and t∈[0:K]t \in[0:K], the MAN placement splits Fn=(Fn,W:W∈Ωt[K])F_n = (F_{n,\mathcal{W}}:\mathcal{W} \in\Omega_t^{[K]}), n∈[N]n \in[N], and user k∈[K]k \in[K] stores Fn,WF_{n,\mathcal{W}} for all nn and W∋k\mathcal{W} \ni k; hence, M=Nt/KM = Nt/K. For A<KA < K, YMA+ [11] assigns to the offline users the demand of an active user and runs the YMA delivery [3] for all KK users, with at most rr distinct demands. YMA+ thus achieves the lower convex envelope of

(Mt,Rt)=(NtK,ct),ct:=(Kt+1)−(K−rt+1)(Kt),t∈[0:K].(4)(M_t,R_t) = \left(\frac{Nt}{K},c_t\right),\qquad c_t := \frac{\binom{K}{t+1}-\binom{K-r}{t+1}}{\binom{K}{t}},\qquad t \in[0:K]. \tag*{(4)}

denoted by R(A,K,N)(YMA+)(M)R^{(\mathrm{YMA+})}_{(A,K,N)}(M). For A=KA = K this is YMA, which is optimal under uncoded placement [2, 3]. For every set of active users, the caches of the active users and the delivery form a classical scheme for AA users, hence

R(A,N)(dec)(M)2.00884≤(i)R(A,A,N)∗(M)≤R(A,K,N)∗(M)≤R(A,K,N)(YMA+)(M)≤(ii)R(A,N)(dec)(M),(5)\frac{R^{(\mathrm{dec})}_{(A,N)}(M)}{2.00884} \overset{(i)}{\le} R^*_{(A,A,N)}(M) \le R^*_{(A,K,N)}(M) \le R^{(\mathrm{YMA+})}_{(A,K,N)}(M) \overset{(ii)}{\le} R^{(\mathrm{dec})}_{(A,N)}(M), \tag*{(5)}

where the lower bounds depend only on AA, and the inequalities marked as (i) and (ii) are from [4], with μ:=M/N\mu:= M/N

R(A,N)(dec)(M)=lim⁡K→∞R(A,K,N)(YMA+)(M)=1−μμ(1−(1−μ)r),R^{(\mathrm{dec})}_{(A,N)}(M) = \lim_{K\to\infty} R^{(\mathrm{YMA+})}_{(A,K,N)}(M) = \frac{1-\mu}{\mu}\left(1-(1-\mu)^r\right),

being the load with decentralized placement [3, 17]. The chain of inequalities in (5) shows that YMA+ is optimal to within a factor of two [12].

GV (row-wise) scheme gomez2018fundamental for classical coded caching

The GV scheme [6] for AA users is an RWP scheme that 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

(Mg,Rg)=(NAg,r−N(r+1)A(g+1)(rg)(Ng)−1),g∈[N].(6)(M_g,R_g) = \left(\frac{N}{Ag},r-\frac{N(r+1)}{A(g+1)}\binom{r}{g}\binom{N}{g}^{-1}\right),\qquad g \in[N]. \tag*{(6)}

For g=N≤Ag = N \le 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)2N)\left(\frac{N}{A},r-\frac{r(r+1)}{2N}\right), which caches the row itself. The line through (0,N)(0,N) and the CFL point is optimal for N≤AN \le A [5]. The line through the CFL point and the GV point with g=N−1g = N-1 is optimal for N=AN = A [6] and for ⌈(A+1)/2⌉≤N≤A\lceil(A+1)/2\rceil\le N \le A [7].

MDS-coded placement MT2022offline,MT2024arxiv for hotplug

Our past work showed that the following points of a classical system with AA users are achievable in the hotplug model for every K≥AK \ge A: the CFL point for A≥NA \ge N [11], Scheme new2 (HT2 in [12]), the YMA point with t=1t = 1 [11], Scheme new1 (HT1 with t=1t = 1 in [12]), and the YMA point with t=A−1t = A-1 for A≥3A \ge3 [12], Scheme HT3. Together with (5), these results imply R(A,K,N)∗=R(A,A,N)∗R^*_{(A,K,N)} = R^*_{(A,A,N)} whenever the latter is attained by one of these points. In [11], Scheme new1 we also added an MDS layer to the MAN placement with t≥2t \ge2, which attains the YMA load of a classical system with AA users, but with a memory size that depends on both AA and KK.

Main Results

We state next our main results, with proof sketches; the full proofs can be found in Appendix.

Uncoded placement for hotplug

Theorem 1 (Optimality of YMA+). For an (A,K,N)(A,K,N) hotplug model, Ru⋆(A,K,N)(M)=R(A,K,N)(YMA+)(M)R_{\mathrm{u}}^{\star(A,K,N)}(M)=R^{(\mathrm{YMA+})}_{(A,K,N)}(M) for all M∈[0,N]M\in[0,N].

Proof Sketch: For the converse, we apply the acyclic index coding bound of [2] to the active users only and average it over the set of active users, their ordering and their distinct demands, which gives R≥∑sxscsR\ge\sum_s x_sc_s, where xsx_s is the fraction of the library cached by exactly ss of the KK users; minimizing over the distribution {xs}\{x_s\} subject to ∑ssxs≤KM/N\sum_s sx_s\le KM/N, as in [2, 3], gives the YMA+ load. □\square

Corollary 1 (Penalty of offline users). For an (A,K,N)(A,K,N) hotplug model under uncoded placement, we have:

(C1.I) if r≥2r\ge2 and K>AK>A, then for every t∈[A−1]t\in[A-1]

Ru⋆(A,K,N)(NtA)>Ru⋆(A,A,N)(NtA);(7)R_{\mathrm{u}}^{\star(A,K,N)}\left(\frac{Nt}{A}\right)>R_{\mathrm{u}}^{\star(A,A,N)}\left(\frac{Nt}{A}\right); \tag*{(7)}

(C1.II) Ru⋆(A,K,N)(M)=Ru⋆(A,A,N)(M)R_{\mathrm{u}}^{\star(A,K,N)}(M)=R_{\mathrm{u}}^{\star(A,A,N)}(M) for M∈[0,NK]∪[N(K−1)K,N]M\in\left[0,\frac{N}{K}\right]\cup\left[\frac{N(K-1)}{K},N\right], i.e., the dependance on KK is in the mid-memory regime.

Corollary 2 (Universality of the MAN placement). For an (A,K,N)(A,K,N) hotplug model, the MAN placement followed by YMA+ for the aa users that turn out to be active, attains Ru⋆(a,K,N)(M)R_{\mathrm{u}}^{\star(a,K,N)}(M) simultaneously for every a∈[K]a\in[K].

In words, for hotplug under uncoded placement, not knowing which users will be active has a load cost (Corollary 1), whereas not knowing how many has none (Corollary 2). Since the inequality in (7) is strict, an optimality result for the hotplug model that matches the classical lower bound in (5) necessarily requires coded placement.

Reed–Solomon embedding of RWP for hotplug

Theorem 2 (Reed–Solomon embedding). Let a classical scheme for AA users with RWP, over a field Fq0\mathbb{F}_{q_0}, achieve (M,R)(M,R), with possibly nonlinear cache placement and delivery functions. Then (M,R)(M,R) is also achievable in the (A,K,N)(A,K,N) hotplug model for every K≥AK\ge A, over any extension field Fq\mathbb{F}_q of Fq0\mathbb{F}_{q_0} with q≥K−1q\ge K-1.

Proof Sketch: The main idea is to view each file as a matrix Fn∈FqA×B/AF_n\in\mathbb{F}_q^{A\times B/A}, n∈[N]n\in[N]. Let ea∈FqAe_a\in\mathbb{F}_q^A be the standard basis vector with a one in position a∈[A]a\in[A]. In the classical model with RWP, the cache contents are Za=ϕ(eaF1,…,eaFN)Z_a=\phi(e_aF_1,\ldots,e_aF_N), a∈[A]a\in[A]. In hotplug, users are assigned the “MDS vectors”

gk:=[1,αk,…,αkA−1],k∈[K−1],gK:=[0,…,0,1](8)g_k:=[1,\alpha_k,\ldots,\alpha_k^{A-1}],\quad k\in[K-1],\qquad g_K:=[0,\ldots,0,1] \tag*{(8)}

where α1,…,αK−1∈Fq\alpha_1,\ldots,\alpha_{K-1}\in\mathbb{F}_q are distinct, which requires q≥K−1q\ge K-1; users cache Zk=ϕ(gkF1,…,gkFN)Z_k=\phi(g_kF_1,\ldots,g_kF_N), k∈[K]k\in[K], thus same cache size as in the classical model. Any AA of the vectors in (8) are linearly independent (Vandermonde). Once the set of active users I={i1,…,iA}\mathcal{I}=\{i_1,\ldots,i_A\} is known, let GIG_{\mathcal{I}} be the invertible matrix with rows gi1,…,giAg_{i_1},\ldots,g_{i_A}, and define the library Fn′:=GIFnF'_n:=G_{\mathcal{I}}F_n, n∈[N]n\in[N]. Since ejFn′=gijFne_jF'_n=g_{i_j}F_n, the cache ZijZ_{i_j} is the cache of classical user jj for the library (Fn′)n(F'_n)_n. The server then uses the classical transmission for the library (Fn′)n(F'_n)_n and demands (dij)j∈[A](d_{i_j})_{j\in[A]}; user iji_j decodes Fdij′F'_{d_{i_j}} and recovers Fdij=GI−1Fdij′F_{d_{i_j}}=G_{\mathcal{I}}^{-1}F'_{d_{i_j}}. □\square

Remark 1. Under uncoded placement, the optimal placement does not depend on the number of active users (Corollary 2), but the load depends on KK (Corollary 1). The Reed–Solomon (RS) embedding has the opposite behavior: the load depends only on AA, but the placement function depends on AA (the number of rows, i.e., the dimension of the RS code) and on KK (the length of the RS code). If only a<Aa<A users turn out to be active, the server can still deliver to any AA-subset of users that contains them, with load RR, but this is in general not optimal.

Remark 2. Theorem 2 applied to the GV scheme in (6) gives the achievability of the GV points of a classical system with AA users, for every K≥AK\ge A. It recovers HT2 and HT1 with t=1t=1 of [12]; HT1 with t≥2t\ge2 and HT3 are not RWP. Theorem 2 is more general than [12]: (a) it applies to every RWP scheme, with a linear or nonlinear placement and delivery; and (b) any RWP scheme that improves on GV in the open range of Corollary 4 immediately yields an improved hotplug scheme in the same regime. For example, in the scheme of Amiri and Gündüz [18], user kk caches Fn,k+Fn+1,kF_{n,k}+F_{n+1,k}, n∈[N−1]n\in[N-1], at M=(N−1)/AM=(N-1)/A; this is an RWP, hence it yields a hotplug scheme with the same load for every K≥AK\ge A. In this case the embedding gives no new point, since the scheme of [18] is strictly dominated by GV for N≥3N\ge3, and it coincides with CFL for N=2N=2.

Converse for RWP in the classical model

Motivated by the ability to embed any classical RWP scheme in the hotplug model for any K≥AK\ge A, we next study the fundamental limits of RWP for uncoded caching with AA users. For such a classical system, let hs:=H(Zk∣FS)h_s:=H(Z_k\mid F_{\mathcal{S}}) for ∣S∣=s∈[0:N]|\mathcal{S}|=s\in[0:N]; by the symmetry argument in [10], without loss of generality H(Zk∣FS)H(Z_k\mid F_{\mathcal{S}}) does not depend on the user k∈[A]k\in[A] or on the subset S∈([N]s)\mathcal{S}\in\binom{[N]}{s}. For every placement, hsh_s is non-increasing in ss (conditioning reduces entropy) and concave in ss (submodularity of entropy), and

0=hN≤hN−1≤⋯≤h1≤h0=M,(9)0=h_N\le h_{N-1}\le\cdots\le h_1\le h_0=M, \tag*{(9)}

where, without loss of generality, h0=Mh_0=M: otherwise the unused memory can be filled with uncoded symbols of the user’s row, which preserves the RWP structure and does not increase the load.

Theorem 3 (RWP converse). For an (A,N)(A,N) classical coded caching model with M≤N/AM\le N/A,

Rrow(A,N)⋆(M)≥min⁡h∈H(M)max⁡ℓ∈[R][L(1+hL)−∑i=0L−1hi],(10)R_{\mathrm{row}(A,N)}^{\star}(M)\ge\min_{h\in\mathcal{H}(M)}\max_{\ell\in[R]}\left[L(1+h_L)-\sum_{i=0}^{L-1}h_i\right], \tag*{(10)}

where H(M)\mathcal{H}(M) is the set of concave (hs)(h_s) that satisfy (9) and

max⁡(0,h0−sA)≤hs≤min⁡(h0,N−sA).(11)\max\left(0,h_0-\frac{s}{A}\right)\le h_s\le\min\left(h_0,\frac{N-s}{A}\right). \tag*{(11)}

Proof Sketch: Fix L∈[r]L \in[r], distinct users u1,…,uLu_1,\ldots,u_L requesting distinct files d1,…,dLd_1,\ldots,d_L; let F<i:=(Fdℓ:ℓ<i)F_{<i}:=(F_{d_\ell}:\ell<i) and Z<i:=(Zuℓ:ℓ<i)Z_{<i}:=(Z_{u_\ell}:\ell<i). Then, for every LL

R≥H(X)≥I(X;F<L+1,Z<L+1)=H(F<L+1,Z<L+1)−H(F<L+1,Z<L+1∣X)=L+LhL−H(F<L+1,Z<L+1∣X)≥L+LhL−∑iH(Zui∣F<i)=L+LhL−∑ihi−1.(12)R \ge H(X) \ge I(X;F_{<L+1},Z_{<L+1}) =H(F_{<L+1},Z_{<L+1})-H(F_{<L+1},Z_{<L+1}\mid X) =L+Lh_L-H(F_{<L+1},Z_{<L+1}\mid X) \ge L+Lh_L-\sum_i H(Z_{u_i}\mid F_{<i}) =L+Lh_L-\sum_i h_{i-1}. \tag*{(12)}

The bound in (11) follows from the RWP structure. □

Theorem 3 plays the role of the acyclic index coding bound for uncoded placement in [2]: the conditional cache entropies hsh_s replace the amounts of data cached by a given number of users, and the minimization over H(M)\mathcal{H}(\mathsf{M}) replaces the optimization over the placement distribution. For N≤AN\le A, the optimization in (10) has a closed form.

Corollary 3 (Theorem 3 for N≤AN\le A). For an (A,N)(A,N) classical coded caching model with M≤N/A≤1M\le N/A\le1,

Rrow(A,N)⋆(M)≥N−1A∑j∈[N]min⁡(AM,j).(13)R^\star_{\mathrm{row}(A,N)}(M)\ge N-\frac{1}{A}\sum_{j\in[N]}\min(AM,j). \tag*{(13)}

i.e., piecewise linear among (qA,N−q(2N−q+1)2A)\left(\frac{q}{A},N-\frac{q(2N-q+1)}{2A}\right), q∈[0:N]q\in[0:N].

Remark 3. For N>AN>A, (10) is a linear program in (h1,…,hN−1)(h_1,\ldots,h_{N-1}) that does not appear to have a simple closed-form solution, but it is easy to solve numerically.

Corollary 4 (RWP optimality). For an (A,N)(A,N) classical model we have: (C4.I) If 2≤N≤A2\le N\le A,

Rrow(A,N)⋆(M)={N(1−M),0≤M≤1A,N−1A−(N−1)M,1A≤M≤NA(N−1).R^\star_{\mathrm{row}(A,N)}(M)= \begin{cases} N(1-M), & 0\le M\le\frac{1}{A},\\ N-\frac{1}{A}-(N-1)M, & \frac{1}{A}\le M\le\frac{N}{A(N-1)}. \end{cases}

i.e., the GV scheme is RWP optimal on the segment between the points with g=Ng=N and g=N−1g=N-1, for every N≤AN\le A.

(C4.II) *For N=2≤AN=2\le A and M∈[0,2A]M\in[0,\frac{2}{A}],

Rrow(A,2)⋆(M)=max⁡{2−2M,2−1A−M}.R^\star_{\mathrm{row}(A,2)}(M)=\max\{2-2M,2-\frac{1}{A}-M\}.

(C4.III) *For AM≤NAM\le N, and every NN and AA,

Rrow(A,N)⋆(M)≥r−r(r+1)2A.(14)R^\star_{\mathrm{row}(A,N)}(M)\ge r-\frac{r(r+1)}{2A}. \tag*{(14)}

with equality at AM=NAM=N, attained by YMA\mathrm{YMA} with t=1t=1.

Corollary 4 has the following consequences:

  • (C4.I) extends the optimality of the GV point with g=N−1g=N-1, known among all placements for ⌈(A+1)/2⌉≤N≤A\lceil(A+1)/2\rceil\le N\le A [7], to every 2≤N≤A2\le N\le A among RWP schemes. Its optimality without placement restrictions for N<⌈(A+1)/2⌉N<\lceil(A+1)/2\rceil remains open.

  • For N=2N=2, the tradeoff without restrictions on the placement is known for A≤3A\le3 [1], [10], while for A≥4A\ge4 it is open on (1A,2(1−2A))\left(\frac{1}{A},2(1-\frac{2}{A})\right), except that for A=4A=4 it is known on [23,2]\left[\frac{2}{3},2\right] [8], [10]; in all cases the open range contains (1A,2A]\left(\frac{1}{A},\frac{2}{A}\right]. (C4.II) characterizes the optimal RWP tradeoff; for its optimality without placement restrictions, see § 5.

  • (C4.III) holds for every NN and AA, i.e., also for N>AN>A.

  • The corner points of (13) are at M=qAM=\frac{q}{A}, q∈[0:N]q\in[0:N], while the GV points are at M=1AgM=\frac{1}{Ag}, g∈[N]g\in[N]; hence a GV point has the same memory size as a corner point of (12) if and only if qg=Nqg=N. In this case, a direct computation gives they have the same load if and only if g=Ng=N (the CFL point, q=1q=1) or g=1g=1 (the YMA point with t=1t=1, q=Nq=N). For example, for N=4N=4 and q=g=2q=g=2, the GV point lies 13A\frac{1}{3A} above the converse. The GV point with g=N−1g=N-1 is RWP optimal even though, for N≥3N\ge3, its memory size is not a corner point of (12): it lies on the segment of (12) with q=1q=1.

  • For 3≤N≤A3\le N\le A, the right-hand side of (12) lies strictly below the lower convex envelope of the GV points for NN−1<AM<N\frac{N}{N-1}<AM<N, where the RWP optimal load remains open in general; the case N=A=3N=A=3 is settled by Theorem 4 next.

Optimality of RWP in the hotplug model

Theorem 4 (RWP optimality for N=A=3N=A=3). For N=A=3N=A=3 and M∈[0,1]M\in[0,1],

Rrow(3,3)⋆(M)=max⁡{3−3M,83−2M,73−43M}.(15)R^\star_{\mathrm{row}(3,3)}(M)=\max\left\{3-3M,\frac{8}{3}-2M,\frac{7}{3}-\frac{4}{3}M\right\}. \tag*{(15)}

i.e., the GV scheme is optimal among RWP schemes, linear or not; its corner points are (0,3)(0,3), (13,2)\left(\frac{1}{3},2\right), (12,53)\left(\frac{1}{2},\frac{5}{3}\right) and (1,1)(1,1). In particular, no RWP scheme attains (35,32)\left(\frac{3}{5},\frac{3}{2}\right).

Proof Sketch: The first two terms in (14) follow from Corollary 3, which on [0,1][0,1] coincides with the outer bound of Tian [10] for (N,K)=(3,3)(N,K)=(3,3), valid for every placement. The third term, 3R+4M≥73R+4M\ge7, is a separate RWP converse, strictly tighter than Tian’s bound on (12,1)\left(\frac{1}{2},1\right); it follows by summing Shannon inequalities that involve only XX, one cache, whole files, and one row of at most two files, together with decoding, the RWP identities, and user–file symmetry. Since 3⋅32+4⋅35=695<73\cdot\frac{3}{2}+4\cdot\frac{3}{5}=\frac{69}{5}<7, the linear scheme of Cao and Xu [19] at (35,32)\left(\frac{3}{5},\frac{3}{2}\right), which is optimal among linear schemes, is not RWP, and no RWP scheme attains the same point¹. □

Corollary 5 (Optimal Reed–Solomon embedded schemes). Let RRS(A,K,N)⋆(M)R^\star_{\mathrm{RS}(A,K,N)}(M) be the minimum load over the hotplug schemes obtained from a classical RWP scheme for AA users by the embedding of Theorem 2. Then RRS(A,K,N)⋆(M)=Rrow(A,N)⋆(M)R^\star_{\mathrm{RS}(A,K,N)}(M)=R^\star_{\mathrm{row}(A,N)}(M) for every K≥AK\ge A and every AM≤NAM\le N; in particular, these loads do not depend on KK, and they are given by Corollary 4 and Theorem 4 wherever these characterize Rrow(A,N)⋆(M)R^\star_{\mathrm{row}(A,N)}(M).

Examples

We provide two examples to further clarify the relationship between various achievable schemes.

a) Case N=A=3N=A=3: Figure 1 shows the various tradeoffs in the small memory regime for N=A=3N=A=3. Under uncoded placement (Theorem 1), the optimal load at M=1M=1 is 11 for K=3K=3, 119\frac{11}{9} for K=4K=4, and 1915\frac{19}{15} for K=6K=6. The Reed–Solomon embedding of the GV scheme for 3 users (Theorem 2) attains the points (13,2)\left(\frac{1}{3},2\right), (12,53)\left(\frac{1}{2},\frac{5}{3}\right) and (1,1)(1,1) for every K≥3K\geq3. By Theorem 4, memory sharing among these points is RWP optimal on [0,1][0,1], for every K≥3K\geq3. On [0,1][0,1], Corollary 3 coincides with the converse of Tian [10], which holds for every placement, and it is tight only on [0,12]\left[0,\frac{1}{2}\right] and at M=1M=1.

Figure 1. Hotplug model with A=N=3A=N=3: optimal load under uncoded placement for K∈{3,4,6}K\in\{3,4,6\} (Theorem 1) and its limit for K→∞K\to\infty, i.e., the load of decentralized placement; load of the Reed–Solomon embedding of the GV scheme for 3 users, which does not depend on KK (Theorem 2) and is RWP optimal (Theorem 4); the point (35,32)\left(\frac{3}{5},\frac{3}{2}\right) of Cao and Xu [19] for the classical system, which is optimal under linear coding, with memory sharing with (12,53)\left(\frac{1}{2},\frac{5}{3}\right) and (1,1)(1,1); and Corollary 3, which on [0,1][0,1] coincides with the converse of [10] for every placement.

The optimal tradeoff under linear coding for the classical system is known [19]: its corner points are at M∈{13,12,32,1,2}M\in\left\{\frac{1}{3},\frac{1}{2},\frac{3}{2},1,2\right\}, where (35,32)\left(\frac{3}{5},\frac{3}{2}\right) is attained by the non-RWP scheme of Cao and Xu [19]. With the schemes known to us, the hotplug model matches it for M∈[0,12]∪[1,3]M\in\left[0,\frac{1}{2}\right]\cup[1,3], by Theorem 2 and HT3 [12]. Whether the optimal load under linear coding of the hotplug model at M=35M=\frac{3}{5} equals 32\frac{3}{2} for K≥4K\geq4 is thus open; it hinges on whether this point can be attained in the hotplug model, for example by embedding the scheme of Cao and Xu [19]. By Theorem 4, such an embedding cannot be obtained from a RWP scheme.

b) Case N=2N=2 and A≥4A\geq4: For the classical model with N=2N=2 files, the optimal tradeoff is known for A≤3A\leq3 [1, 10], and all its corner points are achievable in the hotplug model for every K≥AK\geq A, by Theorem 2 and HT3 [12]. For A≥4A\geq4, which is not covered by [7], the classical tradeoff is known only for M≤1AM\leq\frac{1}{A} [5] and M≥2(1−2A)M\geq2\left(1-\frac{2}{A}\right) [10 Theorem 4.12], and it is matched in the hotplug model in both ranges: for M≤1AM\leq\frac{1}{A} by Theorem 2, and for M≥2(1−2A)M\geq2\left(1-\frac{2}{A}\right) by the YMA points of a classical system with AA users with t=A−1t=A-1 [12 Scheme HT3] and t=A−2t=A-2.

For A=4A=4 (see Figure 2), the scheme of Tian and Chen [8] attains (23,1)\left(\frac{2}{3},1\right), which meets the converse of [10]; hence the classical tradeoff is known for M∈[0,14]∪[23,2]M\in\left[0,\frac{1}{4}\right]\cup\left[\frac{2}{3},2\right], whereas, with the schemes known to us, the hotplug model matches it for M∈[0,14]∪[1,2]M\in\left[0,\frac{1}{4}\right]\cup[1,2]. In particular, in the hotplug model at M=23M=\frac{2}{3} with K=3mK=3m, m≥2m\geq2, YMA+ attains R(YMA+)=1+m−13(3m−1)R^{(\mathrm{YMA+})}=1+\frac{m-1}{3(3m-1)}, which increases to R(dec)=1+19R^{(\mathrm{dec})}=1+\frac{1}{9} as m→∞m\to\infty; memory sharing between the embedded YMA points with t=1t=1 and t=2t=2 attains R=1+118R=1+\frac{1}{18}; and memory sharing between the CFL point (Theorem 2) and the embedded YMA point with t=2t=2 attains R=1+127R=1+\frac{1}{27}, for every K≥4K\geq4. Whether R(4,K,2)∗(23)=1R^{*}_{(4,K,2)}\left(\frac{2}{3}\right)=1 for K≥5K\geq5 is thus open; it hinges on whether this point can be attained in the hotplug model, for example by embedding the scheme of [8].

Figure 2. Hotplug model with N=2N=2 and A=4A=4: optimal load under uncoded placement for K∈{4,6,8}K\in\{4,6,8\} (Theorem 1) and its limit for K→∞K\to\infty; load of the Reed–Solomon embedding of the YMA points for users with A=4A=4, which equals the RWP optimum (Corollary 4) and does not depend on KK (Theorem 2); load of the non-RWP scheme of Tian and Chen [8] for the classical system with 4 users; and the converse of [10] for the classical system, which holds for every placement.

Conclusions

Under uncoded placement, YMA+ is optimal for the hotplug model: the MAN placement is optimal for every number of active users, and offline users strictly increase the load at intermediate memory sizes. The Reed–Solomon embedding of RWP schemes gives the complementary tradeoff, with a load that depends only on the number of active users. Our converse for RWP establishes the RWP optimality of the GV scheme at its two smallest memory points for every N≤AN\leq A, characterizes the RWP tradeoff for N=2N=2 and for N=A=3N=A=3, and establishes the RWP optimality of the YMA point with t=1t=1 for all parameters. Open questions are the RWP tradeoff for NN−1<AM<N\frac{N}{N-1}<A M<N when N≥3N\geq3 (except N=A=3N=A=3), and whether the optimal load of the hotplug model, without any restrictions on the placement, depends only on AA and not on KK. Our results show that, if it does, the optimal schemes must use coded placement.

Acknowledgment

This work was funded in part by NSF under award 2312229.

Use of AI Disclosure

The Author used Anthropic’s Claude (Opus 5.5) during the development and preparation of this manuscript. It assisted in: numerically solving linear programs to search for row-wise schemes and converse bounds, including the extraction of the sparsest Shannon-inequality certificate underlying the proof of Theorem 4; numerically checking the closed-form expressions in the examples; generating the figures; and polishing the text. The Author verified every result, proof, statement and reference in the final manuscript and assumes full responsibility for its contents.

References

Appendix

Proof of Theorem 1

Achievability is YMA+ in (4). By Pascal’s rule, cs=∑i∈[r](K−si)/(Ki)c_s=\sum_{i\in[r]}\binom{K-s}{i}/\binom{K}{i}, and (cs)s(c_s)_s is non-increasing and convex; hence R(A,K,N)(YMA+)R^{(\mathrm{YMA+})}_{(A,K,N)} is the piecewise linear interpolation c^(KM/N)\hat c(KM/N) of (cs)s(c_s)_s. For the converse, fix a scheme with uncoded placement and partition each file as Fn=(Fn,W:W⊆[K])F_n=(F_{n,\mathcal W}:\mathcal W\subseteq[K]), where Fn,WF_{n,\mathcal W} is cached exactly by the users in W\mathcal W. Let xs:=1NB∑n∈[N]∑W∈([K]s)∣Fn,W∣x_s:=\frac{1}{NB}\sum_{n\in[N]}\sum_{\mathcal W\in\binom{[K]}{s}}|F_{n,\mathcal W}| be the fraction of the library cached by exactly ss users; then ∑sxs=1\sum_s x_s=1 and ∑ssxs≤KM/N\sum_s sx_s\le KM/N.

Fix I\mathcal I, an ordered list u=(u1,…,ur)\mathbf u=(u_1,\ldots,u_r) of distinct users in I\mathcal I, and demands with distinct du1,…,durd_{u_1},\ldots,d_{u_r}. Let Qi:=(Fdui,W:W∩{u1,…,ui}=∅)Q_i:=(F_{d_{u_i},\mathcal W}:\mathcal W\cap\{u_1,\ldots,u_i\}=\varnothing), and let E\mathcal E be the rest of the library. Then ZuiZ_{u_i} is a function of (E,Q1,…,Qi−1)(\mathcal E,Q_1,\ldots,Q_{i-1}), and by (3) and induction on ii, H(Q1,…,Qr∣X,E)=0H(Q_1,\ldots,Q_r|X,\mathcal E)=0. Hence

R≥H(Q1,…,Qr)=∑i∈[r]∑W:W∩{u1,…,ui}=∅∣Fdui,W∣B.(16)R\ge H(Q_1,\ldots,Q_r)=\sum_{i\in[r]}\sum_{\mathcal W:\mathcal W\cap\{u_1,\ldots,u_i\}=\varnothing}\frac{|F_{d_{u_i},\mathcal W}|}{B}. \tag*{(16)}

the acyclic index coding bound [2] applied to the active users only. Average (15) over I\mathcal I uniform in ([K]A)\binom{[K]}{A}, u\mathbf u uniform given I\mathcal I, and the distinct demands uniform. Then {u1,…,ui}\{u_1,\ldots,u_i\} is uniform in ([K]i)\binom{[K]}{i} and avoids a given W\mathcal W with probability (K−∣W∣i)/(Ki)\binom{K-|\mathcal W|}{i}/\binom{K}{i}, so that R≥∑sxscs≥c^(∑ssxs)≥c^(KM/N)R\ge\sum_s x_sc_s\ge\hat c(\sum_s sx_s)\ge\hat c(KM/N) by Jensen’s inequality and monotonicity.

Proof of Corollary 1

(C1.I): For real τ\tau, let qi(K)(τ):=∏ℓ=0i−1[K−τ−ℓK−ℓ]+q_i^{(K)}(\tau):=\prod_{\ell=0}^{i-1}\left[\frac{K-\tau-\ell}{K-\ell}\right]_+; it is convex, non-increasing, and equals (K−τi)/(Ki)\binom{K-\tau}{i}/\binom{K}{i} at integers, so R(A,K,N)∗(M)≥∑i∈[r]qi(K)(KM/N)R^*_{(A,K,N)}(M)\ge\sum_{i\in[r]}q_i^{(K)}(KM/N). At M=Nt/AM=Nt/A, for ℓ≥1\ell\ge1, 1−tKA(K−ℓ)>1−tA−ℓ1-\frac{tK}{A(K-\ell)}>1-\frac{t}{A-\ell} when K>AK>A; hence qi(K)(Kt/A)≥qi(A)(t)q_i^{(K)}(Kt/A)\ge q_i^{(A)}(t), strictly for i=2i=2.

(C1.II): On [0,N/K][0,N/K] the load is r−r(r+1)2NMr-\frac{r(r+1)}{2N}M, and on [N(K−1)/K,N][N(K-1)/K,N] it is 1−M/N1-M/N, for every KK.

Proof of Corollary 2

The MAN placement does not depend on aa, YMA+ attains ctc_t with r=min⁡(a,N)r=\min(a,N), and the abscissas Nt/KNt/K of the corner points of c^\hat c do not depend on aa.

Proof of Theorem 2

Since the classical scheme is correct for every realization of the library, running mm instances in parallel we may assume that every row is a vector over Fq\mathbb F_q, q=q0m≥K−1q=q_0^m\ge K-1. The vectors gkg_k in (8) are the columns of the generator matrix of a [K,A][K,A] (extended) Reed–Solomon code, so that any AA of them are linearly independent: for AA vectors with k<Kk<K the determinant is a Vandermonde determinant, and if gKg_K is included, expanding along it leaves an (A−1)×(A−1)(A-1)\times(A-1) Vandermonde determinant.

Placement. The coded row kk of file nn is F~n,k:=∑j∈[A]gk,jFn,j\widetilde F_{n,k}:=\sum_{j\in[A]}g_{k,j}F_{n,j}, and user kk stores Zk:=ϕ(F~1,k,…,F~N,k)Z_k:=\phi(\widetilde F_{1,k},\ldots,\widetilde F_{N,k}), of the same size as the classical cache.

Delivery. Given I={i1,…,iA}\mathcal I=\{i_1,\ldots,i_A\}, the library Fn′:=(F~n,i1,…,F~n,iA)=GIFnF'_n:=(\widetilde F_{n,i_1},\ldots,\widetilde F_{n,i_A})=\mathbf G_{\mathcal I}F_n, where GI\mathbf G_{\mathcal I} acts on the rows of FnF_n, consists of independent and uniformly distributed files, since GI\mathbf G_{\mathcal I} is invertible. Then Zij=ϕ(F1,j′,…,FN,j′)Z_{i_j}=\phi(F'_{1,j},\ldots,F'_{N,j}) is the cache of classical user jj for the library (Fn′)n(F'_n)_n. The server sends (I,d(I))(\mathcal I,\mathbf d(\mathcal I)) and the classical transmission for the library (Fn′)n(F'_n)_n and the classical demands (dij)j∈[A](d_{i_j})_{j\in[A]}, of load RR.

Decoding. User iji_j runs the decoder of classical user jj, obtains Fdij′F'_{d_{i_j}}, and computes Fdij=GI−1Fdij′F_{d_{i_j}}=\mathbf G_{\mathcal I}^{-1}F'_{d_{i_j}}. The map Fn↦Fn′F_n\mapsto F'_n acts on each file separately, which is why the demanded file can be recovered.

Properties of RWP

Lemma 1 (Symmetrization). Every RWP scheme for AA users, with possibly different cache functions ϕ1,…,ϕA\phi_1,\ldots,\phi_A, can be converted into a RWP scheme with the same cache function at every user, and the same memory and load.

Proof. Split every row subfile into AA pieces, Fn,α=(Fn,α(r))r∈[A]F_{n,\alpha}=(F^{(r)}_{n,\alpha})_{r\in[A]}, and let every user store Φ(y(1),…,y(A)):=(ϕr(y(r)))r∈[A]\Phi(y^{(1)},\ldots,y^{(A)}):=(\phi_r(y^{(r)}))_{r\in[A]} of its own row. For c∈[A]c\in[A], run an instance of the original scheme in which user aa plays the role of user c+ac+a (mod $A), on the pieces Fn,a(c+a)F^{(c+a)}_{n,a}; within each instance the roles are distinct, so every instance is a copy of the original scheme, with $1/A$ of the file size.

Lemma 2. For the RWP, (11) holds, and

H(ZB∣FS)=∣B∣h∣S∣,∀B⊆[A], ∀S⊆[N].(17)H(Z_{\mathcal B}|F_{\mathcal S})=|\mathcal B|h_{|\mathcal S|},\qquad\forall\mathcal B\subseteq[A],\ \forall\mathcal S\subseteq[N]. \tag*{(17)}

Proof. Fix k∈[A]k\in[A] and S⊆[N]\mathcal S\subseteq[N] with ∣S∣=s|\mathcal S|=s, and let FS,k:=(Fn,k:n∈S)F_{\mathcal S,k}:=(F_{n,k}:n\in\mathcal S). Since ZkZ_k is a function of (Fn,k:n∈[N])(F_{n,k}:n\in[N]) and all row subfiles are independent, (Zk,FS,k)(Z_k,F_{\mathcal S,k}) is independent of (Fn,j:n∈S, j≠k)(F_{n,j}:n\in\mathcal S,\ j\ne k); hence

hs=H(Zk∣FS)=H(Zk∣FS,k).(18)h_s=H(Z_k|F_{\mathcal S})=H(Z_k|F_{\mathcal S,k}). \tag*{(18)}

Upper bound in (11). Conditioning reduces entropy, so hs≤H(Zk)=h0h_s\le H(Z_k)=h_0. Moreover, given FSF_{\mathcal S}, ZkZ_k is a function of (Fn,k:n∉S)(F_{n,k}:n\notin\mathcal S), which is independent of FSF_{\mathcal S}; hence hs≤H(Fn,k:n∉S)=N−sAh_s\le H(F_{n,k}:n\notin\mathcal S)=\frac{N-s}{A}.

Lower bound in (11). Clearly, hs≥0h_s\ge0, and by (17), h0=H(Zk)≤H(Zk,FS,k)=H(FS,k)+H(Zk∣FS,k)=sA+hsh_0=H(Z_k)\le H(Z_k,F_{\mathcal S,k})=H(F_{\mathcal S,k})+H(Z_k|F_{\mathcal S,k})=\frac{s}{A}+h_s.

Equality (16). Given FSF_{\mathcal S}, the caches are functions of distinct rows of the files not in S\mathcal S, which are independent.

Proof of Theorem 3

Fix L∈[r]L\in[r], distinct users u1,…,uLu_1,\ldots,u_L requesting distinct files f1,…,fLf_1,\ldots,f_L, and let F<i:=(Ffℓ)ℓ<iF_{<i}:=(F_{f_\ell})_{\ell<i}, Z<i:=(Zuℓ)ℓ<iZ_{<i}:=(Z_{u_\ell})_{\ell<i}, F:=F<L+1F:=F_{<L+1}, Z:=Z<L+1Z:=Z_{<L+1}. Then R≥H(X)≥I(X;F,Z)=H(F,Z)−H(F,Z∣X)R\ge H(X)\ge I(X;F,Z)=H(F,Z)-H(F,Z|X), with H(F,Z)=L+LhLH(F,Z)=L+Lh_L by (16), and H(F,Z∣X)=∑i∈[L]H(Zui∣X,Z<i,F<i)≤∑i∈[L]H(Zui∣F<i)=∑i∈[L]hi−1H(F,Z|X)=\sum_{i\in[L]}H(Z_{u_i}|X,Z_{<i},F_{<i})\le\sum_{i\in[L]}H(Z_{u_i}|F_{<i})=\sum_{i\in[L]}h_{i-1}, where the equality uses the chain rule and H(Ffi∣X,Zui)=0H(F_{f_i}|X,Z_{u_i})=0, and the last step uses (16). The resulting bound holds for every LL, and the entropies of the symmetrized scheme belong to H(M)\mathcal H(M) by (9) and Lemma 2.

Proof of Corollary 3

With L=NL=N and hN=0h_N=0, the bracket in (10) is N−∑i=0N−1hiN-\sum_{i=0}^{N-1}h_i, and hi≤min⁡(M,N−iA)h_i\leq\min(M,\frac{N-i}{A}) by (9) and (11); substituting j=N−ij=N-i gives (13). With q:=⌊AM⌋q:=\lfloor AM\rfloor, the sum equals q(q+1)2+(N−q)AM\frac{q(q+1)}{2}+(N-q)AM, which gives the corner points. The bound is the exact value of (10): hs=min⁡(M,N−sA)h_s=\min(M,\frac{N-s}{A}) belongs to H(M)\mathcal{H}(M), and, writing the bracket as ∑i∈[L](1−iδi)\sum_{i\in[L]}(1-i\delta_i) with δi:=hi−1−hi≤1A\delta_i:=h_{i-1}-h_i\leq\frac{1}{A}, each term is non-negative for i≤N≤Ai\leq N\leq A, so that the maximum over LL is attained at L=NL=N.

Proof of Corollary 4

(C4.I): For q=0q=0 and q=1q=1, (13) gives the two lines. They are attained by memory sharing among (0,N)(0,N), the CFL point (1A,N−NA)(\frac{1}{A},N-\frac{N}{A}), and the GV point with g=N−1g=N-1, (NA(N−1),N−N+1A)(\frac{N}{A(N-1)},N-\frac{N+1}{A}), which lies on the second line, with AM=N+1N∈(1,2]AM=\frac{N+1}{N}\in(1,2].

(C4.II): For N=2N=2, NA(N−1)=2A=NA\frac{N}{A(N-1)}=\frac{2}{A}=\frac{N}{A}, so item (C4.I) covers the whole range.

(C4.III): Take L=rL=r in (10) and let δi:=hi−1−hi\delta_i:=h_{i-1}-h_i. Telescoping gives L(1+hL)−∑i=0L−1hi=∑i∈[L](1−iδi)L(1+h_L)-\sum_{i=0}^{L-1}h_i=\sum_{i\in[L]}(1-i\delta_i). By concavity, δi\delta_i is non-decreasing in ii; with hN=0h_N=0 and hr−1≤N−r+1Ah_{r-1}\leq\frac{N-r+1}{A} by (11), for every i≤ri\leq r, δi≤δr≤δr+⋯+δNN−r+1=hr−1N−r+1≤1A\delta_i\leq\delta_r\leq\frac{\delta_r+\cdots+\delta_N}{N-r+1}=\frac{h_{r-1}}{N-r+1}\leq\frac{1}{A}. Hence R≥r−1A∑i∈[r]iR\geq r-\frac{1}{A}\sum_{i\in[r]}i, i.e., (14), for every h∈H(M)h\in\mathcal{H}(M). The YMA point with t=1t=1 attains it at M=N/AM=N/A.

Proof of Corollary 5

By Theorem 2, every RWP load is achievable in the hotplug model for every K≥AK\geq A. Conversely, in a hotplug scheme obtained by embedding an RWP, the active users form a classical RWP scheme for the library (GiFn)n(G_iF_n)_n, whose files are again independent and uniformly distributed; hence its load is at least Rrow(A,N)⋆(M)R^\star_{\mathrm{row}(A,N)}(M), for every K≥AK\geq A.

Proof of Theorem 4

We use the following notation. Files AA, BB, CC have unit size; row kk of file AA is AkA_k, of size 1/31/3, and B1C1B_1C_1 denotes (B1,C1)(B_1,C_1). User kk caches ZkZ_k, a function of (Ak,Bk,Ck)(A_k,B_k,C_k), and hs:=H(Zk∣s files)h_s:=H(Z_k\mid s\text{ files}), so h0≤Mh_0\leq M. Consider the demand in which users 11, 22, 33 request AA, BB, CC, with transmission XX, H(X)≤RH(X)\leq R. By time sharing over the joint permutations of users/rows and files, we may assume that every entropy below is invariant under these permutations. The facts used are:

  • decoding: AA is a function of (X,Z1)(X,Z_1), BB of (X,Z2)(X,Z_2), CC of (X,Z3)(X,Z_3);

  • RWP identities (caches depend only on their own row, rows are independent):

    H(Z3∣A,B)=H(Z3∣A,B3)=h2,H(Z_3\mid A,B)=H(Z_3\mid A,B_3)=h_2,

    H(Z2∣A)=h1,H(Z_2\mid A)=h_1,

    H(Z3∣A2)=h0,H(Z_3\mid A_2)=h_0,

    H(B1C1∣Z1,A1)=H(Z1,A1,B1C1)−H(Z1,A1)=1−(13+h1)=23−h1,H(B_1C_1\mid Z_1,A_1)=H(Z_1,A_1,B_1C_1)-H(Z_1,A_1)=1-(\frac{1}{3}+h_1)=\frac{2}{3}-h_1,

    H(Z1,A,B,C2)=73+h2H(Z_1,A,B,C_2)=\frac{7}{3}+h_2;

Only XX, one cache, whole files and one row of at most two files appear. Let

a:=H(X,Z1)=H(X,Z1,A),a:=H(X,Z_1)=H(X,Z_1,A),
P:=H(X,Z1,A,B,C2)≥H(Z1,A,B,C2)=73+h2.P:=H(X,Z_1,A,B,C_2)\geq H(Z_1,A,B,C_2)=\frac{7}{3}+h_2.

We bound aa in three ways, each obtained by completing (X,Z1,A)(X,Z_1,A) differently.

(i) Through user 2. Since H(Z2∣X,A)≤H(Z2∣A)=h1H(Z_2\mid X,A)\leq H(Z_2\mid A)=h_1 and BB is decoded from (X,Z2)(X,Z_2),

a≥H(X,A)≥H(X,Z2,A,B)−h1=H(X,Z1,A,B)−h1,a\geq H(X,A)\geq H(X,Z_2,A,B)-h_1 =H(X,Z_1,A,B)-h_1,

where the last step swaps users 1,21,2 (and files A,BA,B). Next, H(C2∣X,Z1,A,B)≤H(C2∣X,A,B)H(C_2\mid X,Z_1,A,B)\leq H(C_2\mid X,A,B) gives

H(X,Z1,A,B)≥P−H(X,A,B,C2)+H(X,A,B),H(X,Z_1,A,B)\geq P-H(X,A,B,C_2)+H(X,A,B),

and H(X,A,B)≥H(X,Z3,A,B)−h2=3−h2H(X,A,B)\geq H(X,Z_3,A,B)-h_2=3-h_2. Therefore

a≥163−h1−H(X,A,B,C2).a\geq\frac{16}{3}-h_1-H(X,A,B,C_2).

(ii) Through row 2. H(B,C2∣X,Z1,A)≤H(B,C2∣X,A2)H(B,C_2\mid X,Z_1,A)\leq H(B,C_2\mid X,A_2) gives a≥P−H(X,B,A2)−H(X,A2)a\geq P-H(X,B,A_2)-H(X,A_2). Moreover, CC is decoded from (X,Z3)(X,Z_3), so

H(X,A2)≥H(X,Z3,C,A2)−h0=H(X,Z1,A,B3)−h0≥H(X,A,B3)−h0,H(X,A_2)\geq H(X,Z_3,C,A_2)-h_0 =H(X,Z_1,A,B_3)-h_0\geq H(X,A,B_3)-h_0,

where the equality applies the cyclic shift 1→2→3→11\to2\to3\to1 of users/rows with C→AC\to A, A→BA\to B. Therefore

a≥73+h2−h0+H(X,A,B3)−H(X,B,A2C2).a\geq\frac{7}{3}+h_2-h_0+H(X,A,B_3)-H(X,B,A_2C_2).

(iii) Through row 1. H(B1C1∣X,Z1,A)≤H(B1C1∣Z1,A1)=23−h1H(B_1C_1\mid X,Z_1,A)\leq H(B_1C_1\mid Z_1,A_1)=\frac{2}{3}-h_1, hence, swapping users 1,21,2,

a≥H(X,A,B1C1)−23+h1=H(X,B,A2C2)−23+h1.a\geq H(X,A,B_1C_1)-\frac{2}{3}+h_1=H(X,B,A_2C_2)-\frac{2}{3}+h_1.

Summing. The terms h1h_1 and H(X,B,A2C2)H(X,B,A_2C_2) cancel, and

3a≥7−h0+h2+H(X,A,B3)−H(X,A,B,C2).3a\geq7-h_0+h_2+H(X,A,B_3)-H(X,A,B,C_2).

Swapping users 2,32,3 (and files B,CB,C), and using that (X,Z3,A,B3)(X,Z_3,A,B_3) determines CC and conversely (A,C,B3)(A,C,B_3) determines Z3Z_3,

H(X,A,B,C2)=H(X,A,C,B3)=H(X,Z3,A,B3)≤H(X,A,B3)+h2.H(X,A,B,C_2)=H(X,A,C,B_3)=H(X,Z_3,A,B_3) \leq H(X,A,B_3)+h_2.

Hence 3a+h0≥73a+h_0\geq7. Finally R≥H(X)≥H(X,Z1)−H(Z1)=a−h0R\geq H(X)\geq H(X,Z_1)-H(Z_1)=a-h_0, so 3R+4h0≥3a+h0≥73R+4h_0\geq3a+h_0\geq7, and h0≤Mh_0\leq M.

The proof is complete, with four multipliers, of 14 Shannon inequalities (a sparse dual solution of the genie LP restricted to single-row genies); the three bounds (i)–(iii) are the three ways the LP completes (X,Z1,A)(X,Z_1,A) to the whole library. No pair of caches and no two-row genie is needed.

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. doi: https://doi.org/10.1109/TIT.2014.2306938
  2. [2]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. doi: https://doi.org/10.1109/TIT.2020.2967753.
  3. [3]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. doi: https://doi.org/10.1109/TIT.2017.2785237.
  4. [4]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. doi: https://doi.org/10.1109/TIT.2018.2870566.
  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: https://doi.org/10.1049/iet-com.2015.1205.
  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. doi: https://doi.org/10.1109/TCOMM.2018.2834364.
  7. [7]V. Kumar K. P., B. K. Rai, and T. Jacob, “The exact rate memory tradeoff for small caches with coded placement,” arXiv:2102.04797, 2021.
  8. [8]C. Tian and J. Chen, “Caching and delivery via interference elimination,” IEEE Trans. Inf. Theory, vol. 64, no. 3, pp. 1548–1560, 2018. doi: https://doi.org/10.1109/TIT.2018.2794543
  9. [9]K. Zhang, “Fundamental limits of caching: Symmetry structure and coded placement schemes,” Ph.D. dissertation, Dept. Elect. Comput. Eng., Texas A&M Univ., College Station, TX, USA, 2020.
  10. [10]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: https://doi.org/10.3390/e20080603.
  11. [11]Y. Ma and D. Tuninetti, “On coded caching systems with offline users,” in Proc. IEEE ISIT, pp. 1133–1138, 2022. doi: https://doi.org/10.1109/ISIT50566.2022.9834866
  12. [12]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
  13. [13]C. Rajput and B. S. Rajan, “Improved hotplug caching scheme using PDAs,” in Proc. IEEE ISIT, pp. 1574–1579, 2024. doi: https://doi.org/10.1109/ISIT57864.2024.10619483.
  14. [14]M. Chinnapadamala, C. Rajput, and B. S. Rajan, “A new hotplug coded caching scheme using PDAs,” in Proc. IEEE ITW, pp. 478–483, 2024. doi: https://doi.org/10.1109/ITW616385.2024.10806946
  15. [15]J. Liao and O. Tirkkonen, “Coded caching in presence of user inactivity,” in Proc. IEEE WCNC, pp. 1437–1442, 2022. doi: https://doi.org/10.1109/WCNC51071.2022.9771827.
  16. [16]Ç. Yapar, K. Wan, R. F. Schaefer, and G. Caire, “On the optimality of D2D coded caching with uncoded cache placement and one-shot delivery,” IEEE Trans. Commun., vol. 67, no. 12, pp. 8179–8192, 2019. doi: https://doi.org/10.1109/TCOMM.2019.2940671.
  17. [17]M. A. Maddah-Ali and U. Niesen, “Decentralized coded caching attains order-optimal memory-rate tradeoff,” IEEE/ACM Trans. Netw., vol. 23, no. 4, pp. 1029–1040, 2015. doi: https://doi.org/10.1109/TNET.2014.2317316.
  18. [18]M. Mohammadi Amiri and D. Gündüz, “Fundamental limits of coded caching: Improved delivery rate-cache capacity tradeoff,” IEEE Trans. Commun., vol. 65, no. 2, pp. 806–815, Feb. 2017. doi: https://doi.org/10.1109/TCOMM.2016.2638841.
  19. [19]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

Paper details

vlnc:W_e2jfs7qr
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

Anthropic’s Claude (Opus 5.5)

View statement
Looking for related papers…
Contents