# On Coded Caching Systems with Offline Users, with and without Demand Privacy
against Colluding Users

Yinbin Ma and Daniela Tuninetti
The authors are with the Electrical and Computer Engineering Department of the
University of Illinois Chicago, Chicago, IL 60607, USA (e-mail<EMAIL_ADDRESS>danielat@uic.edu). Parts of this paper were presented in the 2022 [1] and in
the 2023 [2] IEEE International Symposium on Information Theory (ISIT). This
work was supported in part by NSF Awards 1910309 and 2312229. University of
Illinois Chicago, Chicago, IL 60607, USA
Email:{yma52<EMAIL_ADDRESS>
###### Abstract

Coded caching is a technique that leverages locally cached contents at the end
users to reduce the network’s peak-time communication load. Coded caching has
been shown to achieve significant performance gains compared to uncoded
schemes and is thus considered a promising technique to boost performance in
future networks by effectively trading off bandwidth for storage. The original
coded caching model introduced by Maddah-Ali and Niesen does not consider the
case where some users involved in the placement phase, may be offline during
the delivery phase. If so, the delivery may not start or it may be wasteful to
perform the delivery with fictitious demands for the offline users. In
addition, the active users may require their demand to be kept private. This
paper formally defines a coded caching system where some users are offline,
and investigates the optimal performance with and without demand privacy
against colluding users. For this novel coded caching model with offline
users, achievable and converse bounds are proposed. These bounds are shown to
meet under certain conditions, and otherwise to be to within a constant
multiplicative gap of one another. In addition, the proposed achievable
schemes have lower subpacketization and lower load compared to baseline
schemes (that trivially extend known schemes so as to accommodate for privacy)
in some memory regimes.

###### Index Terms:

Coded caching with offline users; Achievablity; Demand privacy; Colluding
users; Optimality for small memory size; Multiplicative constant gap.

##  I Introduction

Coded caching, first introduced by Maddah-Ali and Niesen in [3], leverages
locally cached contents at the users to reduce the communication load during
peak-traffic times. A coded caching system has two phases. During the cache
placement phase, the server populates the users’ local caches, without knowing
the users’ future demands. During the delivery phase, the server broadcasts
coded multicast messages to satisfy the users’ demands. It is a promising
technique as Maddah-Ali and Niesen show in [3] that a coded delivery reduce
communication load significantly with a well-designed placement strategy
compared to uncoded delivery.

The achievable scheme proposed in [3] (referred to as MAN in the following)
has a combinatorial uncoded cache placement phase111Uncoded cache placement
means that bits of the files are directly copied into the caches without any
coding. and a network coded delivery phase. In [4], an improved delivery was
proposed (referred to as YMA in the following), which improves on the MAN
delivery by removing those linearly dependent multicast messages that may
occur when a file is requested by multiple users. The scheme with MAN
placement with YMA delivery matches the converse bound derived in [5] under
the constraint of uncoded placement [4]; and it is otherwise order optimal to
within a factor of two if no restrictions are imposed on the placement phase
for the sake of deriving a converse bound [6]. Wan et al. in [7] extended the
single-file retrieval model in [3] so as to include Scalar Linear Function
Retrieval (SLFR), where users can demand a linear combination of the files. By
generalizing the YMA scheme, [7] proved that SLFR attains the same load as for
single-file retrieval under uncoded placement. A general construction for SLFR
with uncoded placement and linear coding for the delivery can be found in [8].

For the the original coded caching model [3], coded placement is known not
only to strictly improve performance compared to uncoded placement, but to be
exactly optimal in some regimes: [9] shows how to achieve the cut-set bound in
the small memory regime when there are more users than files; [10] proposes a
scheme based on interference elimination for the case of more users than
files; [11] shows an improved performance compared to [10] in small memory
regime when more users than files; [12] derives the optimal performance for
the case of two users (and any number of files), and a partial
characterization for the case of two files (and any number of users); [13]
extends beyond [9] the memory regime over which the optimal coded placement
strategy is known, but it is restricted to the case when the number users and
the number files are the same.

For converse bounds without any restrictions on the placement phase and that
improve on the cut-set bound in [3], in addition to those in [6], [14]
proposes a converse bound where the worst-case and average-case loads are
within a multiplicative gap of 2.315 and 2.507 to the YMA scheme respectively;
we note that [15] derived a converse bound tighter than cut-set bound, and
[12] proposed a computer-aided methodology to derive converse bounds based on
Shannon-type inequalities (which is unfortunately limited to small instances
of the problem, as the computational complexity of the resulting linear
program scales doubly exponentially with the number of users).

A limitation of the above mentioned coded caching schemes, including the YMA
scheme, is that users need to know all the demands in order to decode the
transmitted multicast messages. This may infringe on user’s privacy. Private
Information Retrieval (PIR) [16] addresses the demand-privacy issue against
multiple servers in a single-user system. Here we are interested in protecting
demand privacy of each user against the remaining users. In [17], the demand
privacy constraint was first introduced in the classical coded caching model.
Demand-private schemes include the virtual-users scheme in [18, 19], in which
the server pretends to serve many more users than those actually present in
the system222A construction of a demand-private scheme for a system with $K$
users and $N$ files is given in [20] based on a non-private scheme for a
system with $KN$ users and $N$ files, assuming that users have local
randomness available to them.. In [17], the virtual-users scheme is shown to
be order optimal to within a factor of 8; in addition, a novel scheme that
uses Maximum Distance Separable (MDS) codes for the placement phase is proved
to be order optimal to within a factor of 2 for large memory regime. In [20],
the exact demand-private memory-load tradeoff for 2 users and 2 files was
found, where the virtual-users scheme with restricted demand type (see also
Remark 1) turns out to be optimal in the low memory regime, and the MDS-based
scheme from [17] in the large memory regime. In [21], the virtual-users scheme
with restricted demand type from [20] is generalized and shown to give an
optimal tradeoff point in the very small memory regime, that is, matching the
converse bound from [22]. Another demand-private scheme is the privacy-keys
scheme in [22], where keys are pre-stored in the caches and used to ‘confuse’
users so as to prevent them from gaining any knowledge about the demands of
the remaining users; here placement is coded, with a linear code. The virtual-
users and privacy-keys schemes guarantee privacy even against colluding users,
as defined in [22] for the classical setting, and in [23] for the Device-to-
Device settings where the notion of colluding users was first considered.

Another practical concern in coded caching is that all users present during
the placement phase must be active and synchronously send their demand to the
server before the delivery phase starts. In practical scenarios, some users
may fail to send their demand to the server due to technical failures, or may
have nothing to demand. The asynchronous-demands setting, already discussed in
[3], allows the server to start transmission as soon as the first demand
arrives. Known schemes (as in [24], and references therein) however assume
that all demands eventually arrive in finite time, otherwise the system fails
to complete the delivery, i.e., the problem definition requires that all users
present during the placement successfully decode their demanded file. We find
the latter assumption too restrictive and thus propose a model where only the
demands of the active users must be satisfied. [25] further investigates the
cache-aided multi-input single-output (MISO) model with dynamic user behavior,
and maximize the degrees-of-freedom beyond the multiplexing gain by exploiting
the global caching gain from coded caching. In their model, users can enter or
leave the network at their will. During the placement phase each user is
assigned a profile and all users with the same profile are populated the same
cache content. In the delivery phase, the server transmits multicast and
unicast messages together, depending on the presence of user profile. The
drawbacks are 1) only uncoding placement is considered; 2) when the extreme
case happens, such that all active users present with the same profile, only
unicast messages are sent from server, and no performance gain from coded
caching anymore.

The focus of this paper is on coded caching system with offline users where
the demands of the active users need to be kept private against colluding
users. Performance with offline users was investigated in [26], where a scheme
was proposed under the assumption that the number of active users is fixed and
known; and in [23] for the Device-to-Device model with random user activity,
where an ‘outage event’ (i.e., some active users may fail to decode) was
allowed. In our work, we assume that the demands of the offline users never
arrive (or arrive with infinite delay) and the demands of the remaining active
users arrive synchronously; we do not allow for outages. We refer to this
setting as hotplug coded caching333Hotplug is a computer system term that
refers to a device that can be added or removed from the running system
without having to restart the system.. We derive schemes for the hotplug
setting with and without demand-privacy constraints for the active users. We
shall see that a way to deal with offline users is to carefully design coded
placement strategies based on MDS codes. We shall also show how to compose
various linear codes so as to achieve both resiliency against offline users
while guaranteeing demand privacy at the same time. In summary, to tackle
various issues in coded caching system (such as offline users and privacy), we
propose coded placement as a potential “One Ring”444One Ring is among the most
powerful artifacts in The Lord of the Rings. solution.

###  I-A Contributions

In this paper, we show that coded placement not only benefits the load
performance, but also preserves some advanced features including serving
offline users and guaranteeing demand privacy. We first formalize the hotplug
coded caching problem, without or with demand privacy against colluding users.
To tackle offline users, we propose three new schemes that allow the demands
of the active users to be satisfied regardless of the set of offline users,
where the number (but not the identity) of the offline users is assumed known
at the time of placement, similarly to [26]555The model is motivated by the
law of large numbers for the case where the number of users, $K$, is large and
each user is active with the same probability, $p$, independently at random;
in such setting the number of active users does not fluctuate much compared to
the average value $Kp$. For the setting where the number of users is random,
the solutions proposed in this paper can be used over multiple delivery
rounds. . Our schemes use coded cache placement.

For the case without privacy constraint, we show the following.

  1. 1.

Our first new achievable scheme in Theorem IV.1 exploits MDS codes in the
placement phase and follows SLFR-fashion delivery phase, where coding is done
within each file but not across files. We show that it achieves the optimal
performance when the memory is small and the number of files is large. The
matching converse is obtained from [6].

  2. 2.

Our second new achievable scheme in Theorem IV.2 applies MDS-like coding to
the coded placement of [9]. This scheme achieves the optimal performance when
the memory is small and there are less files than users. The matching converse
is obtained from the cut-set bound in [3].

  3. 3.

Our third new achievable scheme in Theorem IV.3 also utilizes MDS codes in the
placement phase. Unlike the first scheme, the third one needs large cache size
to guarantee that non-trivial multicast messages exists. For each user in the
set of users who benefit from a given multicast message, said user obtains
additional ‘degrees of freedom’ not present in its cache about the desired
file, while the interference from non-demanded files can be removed thanks to
the cached content. The matching converse is obtained is the cut-set bound in
[3].

For the memory regimes where we cannot prove exact optimality, we prove a
constant gap result of two.

To tackle the problem of demand privacy for the hotplug model, we adopt both
the privacy-keys idea [22] into our first and third schemes for the hotplug
model without privacy (see Theorem V.1 and Theorem V.2), as well as the
virtual-users idea [20]. Regarding the virtual-users idea, our contribution is
to extend the proof of [20] from the classical to the hotplug model; based on
this, Theorem V.3 is an immediate consequence. Our new schemes preserve demand
privacy against colluding users and achieve better performance in the small
memory regime and lower subpacketization compared to baseline schemes that
trivially extended privacy-keys scheme or virtual-users scheme without offline
users. As for the case without privacy, we can show exact optimality in the
small and large memory regime, and a constant gap of less than six otherwise.

###  I-B Paper Outline

The rest of the paper is organized as follows. Section II formulates the
hotplug problem with or without demand privacy against colluding users.
Section III summarizes related known results and extends them so as to provide
baseline schemes for our considered settings. Section IV summarizes our main
results for hotplug without privacy. Section V summarizes our main results for
hotplug with privacy. Section VI illustrates the key ideas for our novel
schemes for hotplug without privacy by way of examples. Section VII shows
examples for the hotplug model with privacy. Section VIII provides some
numerical examples. Section IX concludes the paper. Proof details can be found
in Appendix.

###  I-C Notation Convention

We adopt the following notation convention.

  * •

Calligraphic symbols denote sets, bold lowercase symbols vectors, bold
uppercase symbols matrices, and sans-serif symbols system parameters.

  * •

${\mathbf{M}}[{\mathcal{Q}}]$ denotes the submatrix of ${\mathbf{M}}$ obtained
by selecting the rows indexed by ${\mathcal{Q}}$. Similarly,
${\mathbf{d}}[{\mathcal{I}}]$ is the subvector of ${\mathbf{d}}$ obtained by
selecting the elements indexed by ${\mathcal{I}}$.

  * •

For an integer $b$, we let $[b]:=\\{1,\ldots,b\\}$.

  * •

For sets ${\mathcal{S}}$ and ${\mathcal{Q}}$, we let
${\mathcal{S}}\setminus{\mathcal{Q}}:=\\{k:k\in{\mathcal{S}},k\notin{\mathcal{Q}}\\}$.

  * •

For a vector ${\mathbf{d}}$, $\mathsf{rank}({\mathbf{d}})$ is the number of
distinct elements in ${\mathbf{d}}$.

  * •

For a matrix ${\mathbf{D}}$, $\mathsf{rank}({\mathbf{D}})$ is the rank of
${\mathbf{D}}$.

  * •

For a collection $\\{Z_{1},\ldots Z_{n}\\}$ and a index set
${\mathcal{S}}\subseteq[n]$, we let
$Z_{\mathcal{S}}:=\\{Z_{i}:i\in{\mathcal{S}}\\}$.

  * •

For a ground set ${\mathcal{G}}$ and an integer $t$, we let
$\Omega_{{\mathcal{G}}}^{t}:=\\{{\mathcal{T}}\subseteq{\mathcal{G}}:|{\mathcal{T}}|=t\\}$.

  * •

For ${\mathcal{T}}\in\Omega_{{\mathcal{G}}}^{t}$, we let ${\mathcal{T}}_{i}$
be the $i$-th subset in $\Omega_{{\mathcal{G}}}^{t}$ in lexicographical order.
For example, the sets in $\Omega_{\\{1,2,3\\}}^{2}$ are indexed as
${\mathcal{T}}_{1}=\\{1,2\\}$, ${\mathcal{T}}_{2}=\\{1,3\\}$,
${\mathcal{T}}_{3}=\\{2,3\\}$.

  * •

For integers $a$ and $b$, $\binom{a}{b}$ is the binomial coefficient, or zero
if $a\geq b\geq 0$ does not hold.

  * •

The $i$-th standard basis vector is the vector ${\mathbf{e}}_{i}$ that has
only one non-zero component equal to 1 in position $i$.

##  II Problem Formulation

###  II-A Problem Formulation: Hotplug Model without Privacy

An
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug coded caching system consists of the following.

  * •

A central server stores ${\mathsf{N}}$ files, denoted as
$F_{1},\cdots,F_{\mathsf{N}}$.

  * •

Each file has ${\mathsf{B}}$ i.i.d. uniformly distributed symbols over a
finite field $\mathbb{F}_{\mathsf{q}}$, where ${\mathsf{q}}$ is a prime-power
number.

  * •

The server communicates with ${\mathsf{K}}$ users through an error-free shared
link.

  * •

Each user has a local cache that can contain up to ${\mathsf{M}}{\mathsf{B}}$
symbols, where ${\mathsf{M}}\in[0,{\mathsf{N}}]$. We refer to ${\mathsf{M}}$
as the memory size. The caches are denoted as $Z_{1},\ldots,Z_{\mathsf{K}}$.

  * •

The server sends the signal $X$ to the users through the shared link, where
$X$ has no more than ${\mathsf{R}}{\mathsf{B}}$ symbols, with
${\mathsf{R}}\in[0,{\mathsf{N}}]$. We refer to ${\mathsf{R}}$ as the load.

  * •

The system has a placement phase and a delivery phase. The placement phase
occurs at a time when the server is still unaware of which users will be
offline, and which files the active users will request. We assume that the
server knows that exactly
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
users will be active, for some fixed
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\in[{\mathsf{K}}]$.
The delivery phase occurs after the active users have sent their demands to
the server.

Placement Phase: The server populates the local caches as a function of the
files, i.e.,

$\displaystyle H(Z_{k}\mid F_{[{\mathsf{N}}]})=0,\ \forall
k\in[{\mathsf{K}}].$ (1)

Delivery Phase: User $k\in[{\mathsf{K}}]$ demands the file indexed by
$d_{k}\in[{\mathsf{N}}]$. Once the set of active users becomes known to the
server, denoted by
${\mathcal{I}}\in\Omega_{[{\mathsf{K}}]}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$,
the server sends the message $X$ as a function of the files and of the demands
of the active users, i.e.,

$\displaystyle H(X\mid{\mathcal{I}},d_{{\mathcal{I}}},F_{[{\mathsf{N}}]})=0,\
\forall{\mathcal{I}}\in\Omega_{[{\mathsf{K}}]}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>(2)

Decoding: Each active user must be able to decode its desired file with the
help of its locally cached content and the delivery signal, i.e.,

$\displaystyle H(F_{d_{k}}\mid d_{k},Z_{k},X)=0,\ \forall k\in{\mathcal{I}}.$
(3)

  * •

Performance: For ${\mathsf{M}}\in[0,{\mathsf{N}}]$, the minimum worst-case
load (or simply load, for short in the following) is defined as

$\displaystyle{\mathsf{R}}^{\star}({\mathsf{M}})=\limsup_{{\mathsf{B}}\rightarrow\infty}\
\min_{X,Z_{1},\ldots Z_{\mathsf{K}}}\
\max_{{\mathcal{I}},d_{\mathcal{I}}}\\{{\mathsf{R}}:\textrm{\small conditions
in~{}\eqref{eq:cacheplacemntNOprivacy}, \eqref{eq:encodingNOprivacy}
and~{}\eqref{eq:decodingNOprivacy} are satisfied}\\}.$ (4)

We denote by ${\mathsf{L}}({\mathsf{M}})\in\mathbb{Z}_{+}$ the
subpacketization level, which is the smallest file-length ${\mathsf{B}}$
needed to realize a given achievable scheme for memory size ${\mathsf{M}}$.
The subpacketization level is a proxy for the implementation complexity of the
proposed achievable scheme.

###  II-B Problem Formulation: Hotplug Model with Demand Privacy Against
Colluding Users

We next add the constraint of demand privacy against colluding users (or
simply privacy, for short in the following) into the hotplug model introduced
in Section II-A. As in past work on coded caching with privacy [17, 22] or
security [27], we assume that each user $j\in[{\mathsf{K}}]$ has available
some local randomness represented by the random variable (RV) $\tau_{j}$. We
assume that $\tau_{j}$ is only known to the server and to user
$j\in[{\mathsf{K}}]$, and is independent of other RVs. The local randomness
RVs help to generate the cache contents and the transmit signal, and may be
stored if needed for decoding. Mathematically, in the placement phase the
caches are filled as

$\displaystyle H(Z_{k}\mid F_{[{\mathsf{N}}]},\tau_{k})=0,\ \forall
k\in[{\mathsf{K}}];$ (5)

and, in the delivery phase, for all
${\mathcal{I}}\in\Omega_{[{\mathsf{K}}]}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$
and all
$d_{{\mathcal{I}}}\in[{\mathsf{N}}]^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$,
the transmit signal is

$\displaystyle
H(X\mid{\mathcal{I}},d_{{\mathcal{I}}},F_{[{\mathsf{N}}]},\tau_{[{\mathsf{K}}]})=0,$
(6)

the condition of correct decoding for the active users is

$\displaystyle H(F_{d_{k}}\mid d_{k},Z_{k},X)=0,\ \forall k\in{\mathcal{I}},$
(7)

and the privacy condition [22] is

$\displaystyle
I({\mathbf{d}}_{{\mathcal{I}}\setminus{\mathcal{B}}};\,X,{\mathbf{d}}_{{\mathcal{B}}},Z_{\mathcal{B}}\mid{{\mathcal{I}}},F_{[{\mathsf{N}}]})=0,\
\forall{\mathcal{B}}\subseteq{\mathcal{I}},{\mathcal{B}}\not=\emptyset,$ (8)

where ${\mathcal{B}}$ represent the set of colluding active users 666The
condition in (8) (i.e., with ${\mathcal{B}}\not=\emptyset$) implies
$I({\mathbf{d}}_{{\mathcal{I}}};\,X\mid{{\mathcal{I}}},F_{[{\mathsf{N}}]})=0$
(i.e., ${\mathcal{B}}=\emptyset$ can be included in (8)) by the argument in
[22, Appendix A] with $[{\mathsf{K}}]$ replaced by ${\mathcal{I}}$.. For
${\mathsf{M}}\in[0,{\mathsf{N}}]$, the minimum load with privacy is

$\displaystyle{\mathsf{R}}_{\text{\rm
p}}^{\star}({\mathsf{M}})=\limsup_{{\mathsf{B}}\rightarrow\infty}\
\min_{X,Z_{1},\ldots Z_{\mathsf{K}}}\
\max_{{\mathcal{I}},d_{\mathcal{I}}}\\{{\mathsf{R}}:\textrm{\small conditions
in~{}\eqref{eq:cacheplacemntWITHprivacy}, \eqref{eq:encodingWITHprivacy},
\eqref{eq:decodingWITHprivacy} and~{}\eqref{eq:privacyconstraint} are
satisfied}\\},$ (9)

where the subscript ‘p’ in (9) indicates that performance is under the privacy
constraint in (8) as so as to distinguish it from (4). Clearly,
${\mathsf{R}}^{\star}\leq{\mathsf{R}}_{\text{\rm p}}^{\star}$777For the case
${\mathsf{K}}={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}={\mathsf{N}}=2$
we have ${\mathsf{R}}^{\star}<{\mathsf{R}}_{\text{\rm p}}^{\star}$ for
${\mathsf{M}}\in(1/3,4/3)$ [20, 3], thus imposing privacy strictly worsen
performance in some memory regimes., and in both cases the load is a non-
decreasing function of the number of active users
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.

##  III Known Schemes for Classical Model and Extensions to Baseline Schemes
for Hotplug Model

In this section we summarize relevant known results for the classical (i.e.,
not hotplug) coded caching model and provide straightforward extensions to the
hotplug model, which will give us a set of baseline schemes to improve upon in
subsequent sections.

In the following, the name of a baseline scheme is indicated as superscript
among parentheses, and where the addition of the symbol ‘$+$’ or ‘$\&$’
indicate the scheme is an extension from the classical model to the hotplug
model.

###  III-A The YMA Scheme for Classical Model without Privacy

When
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}={\mathsf{K}}$,
the hotplug model is equivalent to the classical coded caching model, for
which a YMA-type scheme is optimal under the constraint of uncoded placement,
both for single-file [4] and with SLFR [28] demands. We describe next the YMA
scheme with SLFR demands, as it will be needed to introduce the privacy-keys
scheme in later sections.

##### Placement Phase

Fix $t\in[0:{\mathsf{K}}]$. Partition each file into $\binom{{\mathsf{K}}}{t}$
equal-size subfiles as

$\displaystyle
F_{i}=(F_{i,{\mathcal{W}}}:{\mathcal{W}}\in\Omega_{[{\mathsf{K}}]}^{t}),\quad\forall
i\in[{\mathsf{N}}].$ (10)

The subpacketization level is $\binom{{\mathsf{K}}}{t}$. The cache content of
user $k$ is

$\displaystyle
Z_{k}=(F_{i,{\mathcal{W}}}:i\in[{\mathsf{N}}],{\mathcal{W}}\in\Omega_{[{\mathsf{K}}]}^{t},k\in{\mathcal{W}}),\quad\forall
k\in[{\mathsf{K}}].$ (11)

The needed memory size is

$\displaystyle{\mathsf{M}}^{\text{\rm(YMA)}}_{t}:={\mathsf{N}}\frac{\binom{{\mathsf{K}}-1}{t-1}}{\binom{{\mathsf{K}}}{t}}={\mathsf{N}}\frac{t}{{\mathsf{K}}}.$
(12)

The placement in (11) is referred to as centralized placement because it
requires coordination among users during the placement phase [3].

##### SLFR Demands

We say that user $k$ demands
${\mathbf{d}}_{k}=[d_{k,1},\ldots,d_{k,{\mathsf{N}}}]\in\mathbb{F}_{\mathsf{q}}^{{\mathsf{N}}}$
if it is interested in retrieving the linear function

$\displaystyle B_{k}:=\sum_{n\in[{\mathsf{N}}]}d_{k,n}F_{n},\quad\forall
k\in[{\mathsf{K}}].$ (13)

Given the file partitioning in (11), we can partition (13) as
$B_{k}=(B_{k,{\mathcal{W}}}:{\mathcal{W}}\in\Omega_{[{\mathsf{K}}]}^{t})$
where the block $B_{k,{\mathcal{W}}}$ is defined as

$\displaystyle
B_{k,{\mathcal{W}}}:=\sum_{n\in[{\mathsf{N}}]}d_{k,n}F_{n,{\mathcal{W}}},\quad\forall
k\in[{\mathsf{K}}].$ (14)

The collection of all demand vectors forms the demand matrix
${\mathbf{D}}=[{\mathbf{d}}_{1};\ldots;{\mathbf{d}}_{\mathsf{K}}]\in\mathbb{F}_{\mathsf{q}}^{{\mathsf{K}}\times{\mathsf{N}}}$.
Note that for single-file retrieval, the demand vectors are restricted to be
standard basis vectors, i.e.,
${\mathbf{d}}_{k}\in\\{{\mathbf{e}}_{1},\ldots,{\mathbf{e}}_{\mathsf{N}}\\}$
for all $k\in[{\mathsf{K}}]$.

##### MAN-type Multicast Messages

Given the demand matrix ${\mathbf{D}}$, the server constructs the multicast
messages

$\displaystyle
X_{\mathcal{S}}=\sum_{k\in{\mathcal{S}}}\alpha_{k,{\mathcal{S}}\setminus\\{k\\}}\,B_{k,{\mathcal{S}}\setminus\\{k\\}},\
\forall{\mathcal{S}}\in\Omega_{[{\mathsf{K}}]}^{t+1},$ (15)

where the encoding coefficients
$\alpha_{k,{\mathcal{S}}\setminus\\{k\\}}\in\\{+1,-1\\}$ are selected as shown
in [28] (for a more general construction, we refer the reader to [8]) and the
blocks $B_{k,{\mathcal{S}}\setminus\\{k\\}}$ are defined in (14), for all
${\mathcal{S}}\in\Omega_{[{\mathsf{K}}]}^{t+1}$ and $k\in[{\mathsf{K}}]$.

##### YMA-type Delivery Phase

Given the demand matrix ${\mathbf{D}}$, the server selects a leader set
${\mathcal{L}}\subseteq[{\mathsf{K}}]$ such that
$\mathsf{rank}({\mathbf{D}}[{\mathcal{L}}])=\mathsf{rank}({\mathbf{D}})$, and
sends

$\displaystyle
X=({\mathcal{L}},\,{\mathbf{D}},\,X_{\mathcal{S}}:{\mathcal{S}}\in\Omega_{[{\mathsf{K}}]}^{t+1},{\mathcal{S}}\cap{\mathcal{L}}\neq\emptyset).$
(16)

##### Decoding

As shown in [28, 8], the delivery signal in (16) allows all users to
successfully decode their requested SLFR. The key observation is that it is
possible to choose the encoding coefficients in (15) in such a way that the
non-leader users, indexed by $[{\mathsf{K}}]\setminus{\mathcal{L}}$, can
locally reconstruct the not-sent multicast messages $X_{\mathcal{A}},$ for all
${\mathcal{A}}\in\Omega_{[{\mathsf{K}}]\setminus{\mathcal{L}}}^{t+1},$ from
the delivery signal in (16). Note that user $k\in{\mathcal{S}}$ can recover
the missing block $B_{k,{\mathcal{S}}\setminus\\{k\\}}$ from $X_{\mathcal{S}}$
in (15) by “caching out”
$\sum_{u\in{\mathcal{S}}\setminus\\{k\\}}B_{u,{\mathcal{S}}\setminus\\{u\\}}$,
which can be computed from $Z_{k}$ in (11).

##### Performance

For the delivery signal in (16) with $|{\mathcal{L}}|$ leaders we have

$\displaystyle
H(X)\leq|{\mathcal{L}}|\log_{\mathsf{q}}({\mathsf{K}})+{\mathsf{K}}{\mathsf{N}}+\frac{\binom{{\mathsf{K}}}{t+1}-\binom{{\mathsf{K}}-|{\mathcal{L}}|}{t}}{\binom{{\mathsf{K}}}{t}}{\mathsf{B}},$
(17)

thus, for very large ${\mathsf{B}}$ and for worst case
$|{\mathcal{L}}|=\mathsf{rank}({\mathbf{D}})=\min({\mathsf{K}},{\mathsf{N}})$,
the following is achievable.

######  Theorem III.1 (YMA).

For a $({\mathsf{K}},{\mathsf{N}})$ classical coded caching system without
privacy, the lower convex envelope of the following points is achievable

$\displaystyle({\mathsf{M}}^{\text{\rm(YMA)}}_{t},{\mathsf{R}}^{\text{\rm(YMA)}}_{t})=\biggl{(}\frac{t}{{\mathsf{K}}},\frac{\binom{{\mathsf{K}}}{t+1}-\binom{{\mathsf{K}}-\min({\mathsf{K}},{\mathsf{N}})}{t+1}}{\binom{{\mathsf{K}}}{t}}\biggr{)},\quad\forall
t\in[0:{\mathsf{K}}].$ (18)

The YMA scheme is optimal under the constraint of uncoded placement [4];
otherwise, it is optimal to within a factor of 2 [6].

###  III-B Baseline Scheme 1 for Hotplug without Privacy: Extension of YMA to
Hotplug

A trivial extension of the centralized YMA scheme in (18) to the hotplug
model, i.e.,
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}<{\mathsf{K}}$,
is to let the server assign as demand for the offline users the demand of the
first leader user. Thus, the following is achievable for the hotplug model
without privacy, by noting that in this case
$|{\mathcal{L}}|\leq\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})$,
i.e., serving the “fake” demands of the offline users does not increase the
size of the leader set for the active users.

######  Theorem III.2 (Extension of YMA to Hotplug).

For a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug system without privacy, the lower convex envelope of the following
points is achievable

$\displaystyle({\mathsf{M}}_{t}^{\text{\rm(YMA)}},{\mathsf{R}}^{\text{\rm(YMA+)}}_{t})=\biggl{(}\frac{t}{{\mathsf{K}}},\frac{\binom{{\mathsf{K}}}{t+1}-\binom{{\mathsf{K}}-\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})}{t+1}}{\binom{{\mathsf{K}}}{t}}\biggr{)},\quad\forall
t\in[0:{\mathsf{K}}].$ (19)

###  III-C Baseline Scheme 2 for Hotplug without Privacy: Decentralized
Placement

Decentralized placement refers to the case where users cache each symbol of
the library in an i.i.d. fashion with probability
$\mu:={\mathsf{M}}/{\mathsf{N}}\in[0,1]$ [29, 4]. From [6, eq(20)], for the
classical model without privacy and leader set ${\mathcal{L}}$, the load with
decentralized placement is
$\frac{1-\mu}{\mu}\big{(}1-(1-\mu)^{|{\mathcal{L}}|}\big{)}.$ Similarly to
Section III-B, a straghtforward extension of the decentralized scheme from the
classical to the hotplug model is obtained by assigning “fake” demands to
offline users in such a way as to leave the size of the leader set for the
active users unchanged.

######  Theorem III.3 (Extension of decentralized scheme to hotplug).

For a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug system without privacy, the following is achievable

$\displaystyle{\mathsf{R}}^{\text{\rm(decen+)}}({\mathsf{M}})=\frac{1-\mu}{\mu}\Big{(}1-(1-\mu)^{\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})}\Big{)},\quad\mu:={\mathsf{M}}/{\mathsf{N}}.$
(20)

Notice: (i)
${\mathsf{R}}^{\text{\rm(YMA+)}}\leq{\mathsf{R}}^{\text{\rm(decen+)}}$ [6];
and (ii) ${\mathsf{R}}^{\text{\rm(decen+)}}$ does not depend on
${\mathsf{K}}$.

###  III-D The PK Scheme for Classical Model with Privacy

A scheme that preserves privacy for the classic (i.e., not hotplug) coded
caching model with single-file retrieval was introduced in [22, Theorem 1].
The central idea was to use Privacy Keys (PK) to “obfuscate” the parts of a
multicast message to the users who are not interested in it, while the
intended user has a “key” to enable its extraction. The PK scheme works as
follows.

##### Placement Phase

Files are split is as in (10). In the following we shall use the notation
${\mathrm{T}}({\mathbf{a}},{\mathbf{b}})$ to denote the “bilinear product of
the subfiles” defined as

$\displaystyle{\mathrm{T}}({\mathbf{a}},{\mathbf{b}}):=\sum_{n\in[{\mathsf{N}}]}\sum_{j\in\left[\binom{{\mathsf{K}}}{t}\right]}a_{n}\,F_{n,{\mathcal{W}}_{j}}\,b_{j}\in\mathbb{F}_{\mathsf{q}}^{{\mathsf{B}}/\binom{{\mathsf{K}}}{t}}.$
(21)

for given vectors ${\mathbf{a}}\in\mathbb{F}_{\mathsf{q}}^{{\mathsf{N}}}$ and
${\mathbf{b}}\in\mathbb{F}_{\mathsf{q}}^{\binom{{\mathsf{K}}}{t}}$. Note that
we can express subfile $F_{i,{\mathcal{W}}_{j}}$ as
$F_{i,{\mathcal{W}}_{j}}={\mathrm{T}}({\mathbf{e}}_{i},{\mathbf{e}}_{j}),i\in[{\mathsf{N}}],j\in[\binom{{\mathsf{K}}}{t}]$;
with a slight abuse of notation, we shall sometimes write
$F_{i,{\mathcal{W}}}={\mathrm{T}}({\mathbf{e}}_{i},{\mathbf{e}}_{{\mathcal{W}}})$,
for $i\in[{\mathsf{N}}],\ {\mathcal{W}}\in\Omega_{[{\mathsf{K}}]}^{t}$.

For each user $k,\ k\in[{\mathsf{K}}]$, the server picks i.i.d uniformly at
random the key vector ${\mathbf{p}}_{k}$ from the set of all vectors whose
entries sum to ${\mathsf{q}}-1$, i.e.,
${\mathbf{p}}_{k}\in{\mathcal{P}}_{\mathsf{N}}$ where
${\mathcal{P}}_{\mathsf{N}}$ is defined as

$\displaystyle{\mathcal{P}}_{\mathsf{N}}:=\Big{\\{}{\mathbf{p}}=[p_{1},\ldots,p_{\mathsf{N}}]\in\mathbb{F}_{\mathsf{q}}^{{\mathsf{N}}}:\sum_{i\in[{\mathsf{N}}]}p_{i}={\mathsf{q}}-1\Big{\\}}.$
(22)

The server populates the cache of user user $k$ as

$\displaystyle Z_{k}$
$\displaystyle=\left\\{{\mathrm{T}}({\mathbf{e}}_{i},{\mathbf{e}}_{\\{k\\}\cup{\mathcal{Q}}}):i\in[{\mathsf{N}}],{\mathcal{Q}}\in\Omega_{[{\mathsf{K}}]\setminus\\{k\\}}^{t-1}\right\\}$
(23a) $\displaystyle\bigcup\
\left\\{{\mathrm{T}}({\mathbf{p}}_{k},{\mathbf{e}}_{{\mathcal{W}}}):{\mathcal{W}}\in\Omega_{[{\mathsf{K}}]\setminus\\{k\\}}^{t}\right\\},\
\forall k\in[{\mathsf{K}}],$ (23b) where (23a) is the uncoded part of the
cache as in (11), while (23b) is the coded part corresponding to the privacy
keys of the form ${\mathrm{T}}({\mathbf{p}}_{k},{\mathbf{e}}_{{\mathcal{W}}})$
for all sets ${\mathcal{W}}$ that do not include $k$.

Note that ${\mathbf{p}}_{k}$ is the local randomness for user $k,\
k\in[{\mathsf{K}}]$, which is not stored directly in its cache. The needed
memory size is

$\displaystyle{\mathsf{M}}^{\text{\rm(PK)}}_{t}:={\mathsf{N}}\frac{\binom{{\mathsf{K}}-1}{t-1}}{\binom{{\mathsf{K}}}{t}}+\frac{\binom{{\mathsf{K}}-1}{t}}{\binom{{\mathsf{K}}}{t}}=1+\frac{t}{{\mathsf{K}}}({\mathsf{N}}-1)\geq
1.$ (24)

Note that
${\mathsf{M}}^{\text{(YMA)}}_{t}={\mathsf{N}}\frac{t}{{\mathsf{K}}}\leq{\mathsf{M}}^{\text{\rm(PK)}}_{t}$
as users also store privacy keys.

##### Delivery Phase

User $k$ has (single-file demand) demand vector
${\mathbf{e}}_{d_{k}}\in\mathbb{F}_{\mathsf{q}}^{{\mathsf{N}}}$ (meaning that
he is interested in retrieving the file with index $d_{k}\in[{\mathsf{N}}]$).
Associated to demand vector ${\mathbf{e}}_{d_{k}}$ is the query vector

$\displaystyle{\mathbf{q}}_{k}:={\mathbf{p}}_{k}+{\mathbf{e}}_{d_{k}}\in\mathbb{F}_{\mathsf{q}}^{{\mathsf{N}}},\
\forall k\in[{\mathsf{K}}],$ (25)

which can be thought of as a one-time pad of the demand vector
${\mathbf{e}}_{d_{k}}$ by the key vector ${\mathbf{p}}_{k}$. The collection of
all query vectors gives the query matrix
${\mathbf{Q}}=[{\mathbf{q}}_{1};\ldots;{\mathbf{q}}_{\mathsf{K}}]\in\mathbb{F}_{\mathsf{q}}^{{\mathsf{K}}\times{\mathsf{N}}}$.

It is important to note that, by the definition in (22), the entries of the
key vectors sum to ${\mathsf{q}}-1$; in addition, the entries of the single-
file demand vectors sum to $1$; thus, the entries of the query vectors in (25)
sum to zero in $\mathbb{F}_{\mathsf{q}}$, that is, by design query vectors are
uniformly and independently distributed over an ${\mathsf{N}}-1$ dimensional
subspace in $\mathbb{F}_{\mathsf{q}}$. This implies that
$\mathsf{rank}({\mathbf{Q}})\leq\min({\mathsf{K}},{\mathsf{N}}-1).$

Even though we consider single-file demands, the delivery is done as if we
have SLFR demands according to the query vectors in (25), that is, the server
transmits

$\displaystyle X$
$\displaystyle=({\mathcal{L}},\,{\mathbf{Q}},\,X_{\mathcal{S}}:{\mathcal{S}}\in\Omega_{[{\mathsf{K}}]}^{t+1},{\mathcal{S}}\cap{\mathcal{L}}\neq\emptyset),$
(26)

where ${\mathcal{L}}$ is the leader set for the query matrix ${\mathbf{Q}}$,
and the blocks in (14) (in the multicast messages $X_{\mathcal{S}}$ in (15))
are constructed according to the query matrix rather than the demand matrix.

##### Decoding and Privacy

The multicast message only useful for non-leader users (and not included in
(26)) can be reconstructed locally as per the decoding procedure for the SLFR
scheme.

To understand how decoding proceeds once all multicast messages are locally
available, we rewrite the multicast message (which were designed according to
the query matrix) useful for the users indexed by ${\mathcal{S}}$ as follows
$\displaystyle X_{\mathcal{S}}$
$\displaystyle=\sum_{j\in{\mathcal{S}}}\alpha_{{\mathcal{S}},j}{\mathrm{T}}({\mathbf{q}}_{j},{\mathbf{e}}_{{\mathcal{S}}\setminus\\{j\\}})$
(27a)
$\displaystyle=\alpha_{{\mathcal{S}},v}\underbrace{{\mathrm{T}}({\mathbf{e}}_{d_{v}},{\mathbf{e}}_{{\mathcal{S}}\setminus\\{v\\}})}_{\text{demanded
by
user~{}$v$}}+\alpha_{{\mathcal{S}},v}\underbrace{{\mathrm{T}}({\mathbf{p}}_{v},{\mathbf{e}}_{{\mathcal{S}}\setminus\\{v\\}})}_{\text{privacy
key cached in $Z_{v}$}}$ (27b)
$\displaystyle+\sum_{j\in{\mathcal{S}}\setminus\\{v\\}}\alpha_{{\mathcal{S}},j}\underbrace{{\mathrm{T}}({\mathbf{q}}_{j},{\mathbf{e}}_{{\mathcal{S}}\setminus\\{j\\}})}_{\text{computable
by user~{}$v$}},\quad\forall v\in{\mathcal{S}},$ (27c) where all terms in
(27c) are computed locally from the cache content $Z_{v}$ in (23a) and
${\mathbf{Q}}$ in (26) as
$\displaystyle{\mathrm{T}}({\mathbf{q}}_{j},{\mathbf{e}}_{{\mathcal{S}}\setminus\\{j\\}})=\sum_{n\in[{\mathsf{N}}]}q_{j,n}{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{e}}_{{\mathcal{S}}\setminus\\{j\\}}),$
(27d) and
${\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{e}}_{{\mathcal{S}}\setminus\\{j\\}})$
is cached by the users indexed in ${\mathcal{S}}\setminus\\{j\\}$.

Therefore, user $v\in{\mathcal{S}}$ can retrieve
${\mathrm{T}}({\mathbf{e}}_{d_{v}},{\mathbf{e}}_{{\mathcal{S}}\setminus\\{v\\}})$
from $X_{\mathcal{S}}$ if $v\in{\mathcal{S}}$. This shows that all users can
successfully decode their demanded file. The proof that the PK scheme is
private can be found in [22], and hinges on the fact that the key vectors are
independently and uniformly disturbed.

##### Performance

For very large ${\mathsf{B}}$ and for the worst-case query matrix with
$\mathsf{rank}({\mathbf{Q}})=\min({\mathsf{K}},{\mathsf{N}}-1)$, the following
is achievable.

######  Theorem III.4 (PK).

For a $({\mathsf{K}},{\mathsf{N}})$ classical coded caching system with
privacy, the lower convex envelope of
$({\mathsf{M}},{\mathsf{R}})=(0,{\mathsf{N}})$ with the following points is
achievable

$\displaystyle({\mathsf{M}}^{\text{\rm(PK)}}_{t},{\mathsf{R}}^{\text{\rm(PK)}}_{t})=\left(1+\frac{t}{{\mathsf{K}}}({\mathsf{N}}-1),\frac{\binom{{\mathsf{K}}}{t+1}-\binom{{\mathsf{K}}-\min({\mathsf{K}},{\mathsf{N}}-1)}{t+1}}{\binom{{\mathsf{K}}}{t}}\right),\quad
t\in[0:{\mathsf{K}}].$ (28)

The PK scheme is optimal to within a factor of 5.4606 [22].

###  III-E Baseline Scheme 1 for Hotplug with Privacy: Extension of PK to
Hotplug

The same argument we used to the extend the YMA scheme from the classical to
the hotplug model can be used to extend the PK scheme from the classical to
the hotplug model.

######  Theorem III.5 (Extension of PK to Hotplug).

For a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug model with privacy, the lower convex envelope of
$({\mathsf{M}},{\mathsf{R}})=(0,{\mathsf{N}})$ and the following points is
achievable

$\displaystyle({\mathsf{M}}^{\text{\rm(PK)}}_{t},{\mathsf{R}}^{\text{\rm(PK+)}}_{t})=\left(1+\frac{t}{{\mathsf{K}}}({\mathsf{N}}-1),\frac{\binom{{\mathsf{K}}}{t+1}-\binom{{\mathsf{K}}-\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}}-1)}{t+1}}{\binom{{\mathsf{K}}}{t}}\right),\quad\forall
t\in[0:{\mathsf{K}}].$ (29)

Note that, in the low memory regime, the PK+ tradeoff is given by the segment
connecting the trivial corner point
$({\mathsf{M}},{\mathsf{R}})=(0,{\mathsf{N}})$ to
$({\mathsf{M}}^{\text{\rm(PK)}}_{0},{\mathsf{R}}^{\text{\rm(PK+)}}_{0})=(1,\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}}-1))$,
which may not be decreasing fast enough. Thus, we introduce next another
baseline scheme.

###  III-F Baseline Schemes 2 and 3 for Hotplug with Privacy: Extension of VU
to Hotplug

In [19], privacy in the classical model was achieved by introducing the idea
of virtual-users (VU). In the VU scheme, each physical user has associated to
it a distinct set of ${\mathsf{N}}$ virtual-users; each physical users picks
independently and uniformly at random the cache content of one of its
associated virtual users. The trick in the delivery phase of the VU scheme is
to assign demands to the ${\mathsf{K}}{\mathsf{N}}$ virtual users in such a
way that each of the ${\mathsf{N}}$ file is demanded exactly ${\mathsf{K}}$
times888This special ‘restricted-type’ demand vector does not in general
coincide with the worst-case demand vector [12].. It turns out that the
performance of the VU scheme is the same as that of the YMA scheme with
${\mathsf{K}}{\mathsf{N}}$ users and ${\mathsf{N}}$ files, i.e., in (18) we
replace ${\mathsf{K}}$ with ${\mathsf{K}}{\mathsf{N}}$.

Next, we extend the YMA and the decentralized schemes from the non-private
classical model to the hotplug with privacy model by the the VU idea. By
noting that
$\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}{\mathsf{N}},{\mathsf{N}})={\mathsf{N}}=\min({\mathsf{K}}{\mathsf{N}},{\mathsf{N}})$,
we conclude that the performance of the VU scheme for the classical and the
hotplug models is the same.

######  Theorem III.6 (Extensions to hotplug with VU idea).

For a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug model with privacy, the lower convex envelope of the following points
is achievable

$\displaystyle({\mathsf{M}}^{\text{\rm(YMA\&VU)}}_{t},{\mathsf{R}}^{\text{\rm(YMA\&VU)}}_{t})=\left({\mathsf{N}}\frac{t}{{\mathsf{K}}{\mathsf{N}}},\frac{\binom{{\mathsf{K}}{\mathsf{N}}}{t+1}-\binom{{\mathsf{K}}{\mathsf{N}}-{\mathsf{N}}}{t+1}}{\binom{{\mathsf{K}}{\mathsf{N}}}{t}}\right),\quad\forall
t\in[0:{\mathsf{K}}{\mathsf{N}}].$ (30)

in addition, the following is achievable

$\displaystyle{\mathsf{R}}^{\text{\rm(decen\&VU)}}({\mathsf{M}})=\frac{1-\mu}{\mu}\Big{(}1-(1-\mu)^{{\mathsf{N}}}\Big{)}.\quad\mu:={\mathsf{M}}/{\mathsf{N}}.$
(31)

Notice: (i) the subpacketization level of the YMA&VU scheme, given by
$\binom{{\mathsf{K}}{\mathsf{N}}}{t}$ for
${\mathsf{M}}/{\mathsf{N}}=t/({\mathsf{N}}{\mathsf{K}}),$ may be huge and thus
unaffordable in practical systems; and (ii)
${\mathsf{R}}^{\text{\rm(YMA\&VU)}}$ and
${\mathsf{R}}^{\text{\rm(decen\&VU)}}$ do not depend
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.

######  Remark 1.

The VU idea is very powerful as one can readily derive a scheme for a
$({\mathsf{K}},{\mathsf{N}})$-classical-private model from a
$({\mathsf{K}}{\mathsf{N}},{\mathsf{N}})$-classical-NONprivate model [20]. The
construction in [20, Theorem 4] further leverages a critical observation: in
the $({\mathsf{K}}{\mathsf{N}},{\mathsf{N}})$-classical-NONprivate model one
considers all possible $[{\mathsf{N}}]^{{\mathsf{K}}{\mathsf{N}}}$ demands,
which are much more than the $[{\mathsf{N}}]^{{\mathsf{K}}}$ possible demands
in the $({\mathsf{K}},{\mathsf{N}})$-classical-private model. By studying a
restricted $({\mathsf{K}}{\mathsf{N}},{\mathsf{N}})$-classical-NONprivate
model where only a carefully selected subset of
$[{\mathsf{N}}]^{{\mathsf{K}}}$ demands are allowed (see [20] for details),
one can obtain a better load performance. The essence of in [20, Theorem 4] is
thus that: one can readily derive a scheme for a
$({\mathsf{K}},{\mathsf{N}})$-classical-private model from a
$({\mathsf{K}}{\mathsf{N}},{\mathsf{N}})$-restricted-classical-NONprivate
model. The challenge with this approach is that restricted-classical-
NONprivate models have not been studied in the literature, except for [21].

The argument in [20, Theorem 4] extends to the hotplug model: one can derive a
scheme for a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$-hotplug-
private model from a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}{\mathsf{N}},{\mathsf{K}}{\mathsf{N}},{\mathsf{N}})$-restricted-
hotplug-NONprivate model. The proof can be found in Appendix G. The study of
restricted-hotplug-NONprivate models is an interesting open problem. $\square$

##  IV Main Results for Hotplug without Privacy

In this section we summarize our main results for the hotplug model without
the constraint of demand privacy against colluding users.

######  Theorem IV.1 (New Scheme 1).

For a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug system without privacy, the lower convex envelope of the following
point is achievable

$\displaystyle({\mathsf{M}}_{t}^{\text{\rm HT1}},{\mathsf{R}}^{\text{\rm
HT1}}_{t})$
$\displaystyle=\biggl{(}{\mathsf{N}}\frac{\binom{{\mathsf{K}}-1}{t-1}}{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}},\frac{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t+1}-\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})}{t+1}}{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}}\biggr{)},\quad\forall
t\in[0:{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>(32)

######  Remark 2 (Sketch of achievability for Theorem IV.1).

The proof that our first novel scheme attains the load in (32) can be found in
Appendix A. At a high level, we split each file into
$\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}$
equal-length subfiles and then code the subfiles with an MDS code of rate
${\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}}/{\binom{{\mathsf{K}}}{t}}$.
The placement of the MDS-coded symbols follows the MAN spirit and the delivery
the YMA spirit.

By comparing ${\mathsf{R}}^{\text{\rm(YMA)}}_{t}$ in (18) for the classical
coded caching system with
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
users (rather than ${\mathsf{K}}$) with the load ${\mathsf{R}}^{\text{\rm
HT1}}_{t}$ in (32), we notice they have the exact same expression; the
difference is in the memory requirement, which is
${\mathsf{M}}/{\mathsf{N}}=t/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
for the YMA scheme with
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
users and
${\mathsf{M}}/{\mathsf{N}}=t/{\mathsf{K}}\cdot{\binom{{\mathsf{K}}}{t}}/{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}}$
for our first new scheme with
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
active users out of ${\mathsf{K}}$ total users. In other words, we need more
cache space (quantified by the inverse of the MDS code rate) in order to serve
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
online users and tolerate
${\mathsf{K}}-{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
offline users, compared to the classical YMA coded caching scheme for
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
users. Note that the two schemes have the same memory requirement for $t=1$.

For an example of Theorem IV.1, please see Sections VI-A2 and VI-B2. $\square$

######  Remark 3 (Optimality for Theorem IV.1 in the small memory regime).

Let
${\mathsf{r}}^{\prime}:=\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})$.
Consider the following corner points in Theorem IV.1

$\displaystyle({\mathsf{M}}^{\text{\rm HT1}}_{0},{\mathsf{R}}^{\text{\rm
HT1}}_{0})$ $\displaystyle=(0,{\mathsf{r}}^{\prime}),$ (33)
$\displaystyle({\mathsf{M}}^{\text{\rm HT1}}_{1},{\mathsf{R}}^{\text{\rm
HT1}}_{1})$
$\displaystyle=\left(\frac{{\mathsf{N}}}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}},{\mathsf{r}}^{\prime}-\frac{{\mathsf{r}}^{\prime}({\mathsf{r}}^{\prime}+1)}{2{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}\right).$
(34)

The segment connecting the points (33) and (34) (achievable by memory sharing)
outperforms the baseline scheme YMA+ in (19). Furthermore, it is optimal when
the number of files is sufficiently large enough, as proved in Theorem IV.4.
$\square$

######  Theorem IV.2 (New Scheme 2).

For a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug system without privacy, if
${\mathsf{K}}\geq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\geq{\mathsf{N}}$,
the following point is achievable

$\displaystyle({\mathsf{M}}^{\text{\rm HT2}},{\mathsf{R}}^{\text{\rm
HT2}})=\biggl{(}\frac{1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}},{\mathsf{N}}\left(1-\frac{1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}\right)\biggr{)}.$
(35)

######  Remark 4 (Sketch of achievability for Theorem IV.2).

The proof of the achievabilty of (35) can be found in Appendix B. In this
scheme, we first code the files together, and then we apply another level of
MDS coding before the placement. The general delivery has two steps: first we
‘unlock’ the cache contents of the active users similarly to in [9], and then
we perform a sequence of YMA-type deliveries to subsets of active users
requesting the same file.

For an example of Theorem IV.2, please see Sections VI-A1 and VI-B1. $\square$

######  Remark 5 (Optimality for Theorem IV.2 in the small memory regime).

As shown in Theorem IV.4, our second new scheme is optimal for
${\mathsf{K}}\geq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\geq{\mathsf{N}}$
in the memory regime
${\mathsf{M}}\leq\frac{1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$
as it meets the cut-set bound
${\mathsf{R}}^{\star}({\mathsf{M}})\geq{\mathsf{N}}(1-{\mathsf{M}})$.
$\square$

######  Theorem IV.3 (New Scheme 3).

For a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug system without privacy, the following point is achievable for
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\geq
3$

$\displaystyle({\mathsf{M}}^{\text{\rm HT3}},{\mathsf{R}}^{\text{\rm
HT3}})=\left({\mathsf{N}}\frac{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}},\frac{1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}\right).$
(36)

######  Remark 6 (Sketch of achievability for Theorem IV.3).

The proof of the achievability of (36) can be found in Appendix C as the
special case of the following scheme for
${\mathsf{L}}_{t}={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
and
$t={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1$.

######  Lemma 1.

For a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug system without privacy, the lower convex envelope of the following
points is achievable: let the subpacketization ${\mathsf{L}}_{t}$ be the
largest positive integer which satisfies
${\mathsf{L}}_{t}<\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{t-1}\frac{t}{t-1}$,
then

$\displaystyle({\mathsf{M}}_{t}^{\text{\rm FLEX}},{\mathsf{R}}_{t}^{\text{\rm
FLEX}})=\left({\mathsf{N}}\frac{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{t-1}}{{\mathsf{L}}_{t}},\frac{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t+1}-\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})}{t+1}}{{\mathsf{L}}_{t}}\right),\quad\forall
t\in[2:{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>(37)

For the scheme in Lemma 1, we construct an MDS generator matrix of dimension
${\mathsf{L}}_{t}\times{\mathsf{K}}\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{t-1}$,
then partition it into ${\mathsf{K}}$ disjoint parts (one per user) where each
part is used to populate the cache of a user. Then, we construct the multicast
messages within the linear span of the caches. Users can eliminate the
‘interference’ on non-demanded files and thus recover their desired
information. Note that the constraint on the subpacketization level implies
${\mathsf{M}}_{t}^{\text{\rm FLEX}}>{\mathsf{N}}(t-1)/t$.

For an example of Theorem IV.3, please see Section VI-B3. $\square$

######  Remark 7 (Optimality for Theorem IV.3 in the large memory regime).

As shown in Theorem IV.4, our third new scheme is optimal in the memory regime
${\mathsf{M}}\geq{\mathsf{N}}\frac{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$
as it meets the cut-set bound ${\mathsf{R}}^{\star}({\mathsf{M}})\geq
1-{\mathsf{M}}/{\mathsf{N}}$. $\square$

Next we provide performance guarantees for the three new scheme we have
introduced. As a converse bound, we can use any converse result for the
classical coded caching system without privacy with
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
users and ${\mathsf{N}}$ files; this is so because the performance of our
hotplug system cannot be better than that of a system in which the server
knows a priori which set of
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
users will be active, and does the optimal placement and delivery for those
users. With this type of converse bounds, we can show the following optimality
result. The detailed proof can be found in Appendix F.

######  Theorem IV.4 (Optimality Guarantees).

For a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug system without privacy we have the following optimality guarantees.

  1. 1.

When
$\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})=1$,
${\mathsf{R}}^{\text{\rm(YMA+)}}$ is optimal.

  2. 2.

${\mathsf{R}}^{\text{\rm(YMA+)}}$ is at most a factor 2 from optimal.

  3. 3.

When
${\mathsf{K}}\geq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=2$
and ${\mathsf{N}}=2$, the optimal scheme has two non-trivial corner points:
$({\mathsf{M}}_{1}^{\text{\rm HT1}},{\mathsf{R}}_{1}^{\text{\rm
HT1}})=(1,1/2)$ and $({\mathsf{M}}^{\text{\rm HT2}},{\mathsf{R}}^{\text{\rm
HT2}})=(1/2,1)$.

  4. 4.

When
${\mathsf{K}}\geq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=2$
and ${\mathsf{N}}\geq 3$, the only non-trivial optimal corner point is
$({\mathsf{M}}_{1}^{\text{\rm HT1}},{\mathsf{R}}_{1}^{\text{\rm
HT1}})=({\mathsf{N}}/2,1/2)$.

  5. 5.

When
${\mathsf{N}}\geq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}+1)/2$,
the corner point $({\mathsf{M}}_{1}^{\text{\rm
HT1}},{\mathsf{R}}_{1}^{\text{\rm
HT1}})=({\mathsf{N}}/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1)/2)$
is optimal. Memory sharing between this point and the trivial corner point
$(0,{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}})$
gives optimality for
${\mathsf{M}}\leq{\mathsf{N}}/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
when
${\mathsf{N}}\geq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}+1)/2$.

  6. 6.

When
${\mathsf{N}}\leq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$,
the corner point $({\mathsf{M}}_{1}^{\text{\rm
HT2}},{\mathsf{R}}_{1}^{\text{\rm
HT2}})=(1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}}(1-1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}))$
is optimal. Memory sharing between this point and the trivial corner point
$(0,{\mathsf{N}})$ gives optimality for ${\mathsf{M}}\leq
1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
when
${\mathsf{N}}\leq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.

  7. 7.

When
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\geq
3$, the pont $({\mathsf{M}}^{\text{\rm HT3}},{\mathsf{R}}^{\text{\rm
HT3}})=\left({\mathsf{N}}\frac{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}},\frac{1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}\right)$
is optimal. Memory sharing between this point and the trivial corner point
$({\mathsf{N}},0)$ gives optimality for
${\mathsf{M}}\geq{\mathsf{N}}(1-1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}})$
when
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\geq
3$.

Notice: Theorem IV.4 provides a tight characterization for
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=2$
(see Item 3 and Item 4) but not for
$\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})=2$,
as even the classical coded caching model with ${\mathsf{N}}=2$ files is only
partially solved [12].

######  Remark 8 (Does the optimal hotplug performance only depend on
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$?).

It is interesting to note that the exact optimality results in Theorem IV.4 do
not depend on ${\mathsf{K}}$ (the total number of users) but only on
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
(the total number of active users). It is not obvious that this should be the
case in general. It is an intriguing open question to prove, or disprove, that
the optimal hotplug performance depends on
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
but not on ${\mathsf{K}}$. $\square$

##  V Main Results for Hotplug with Privacy

In this section we summarize our main results for the hotplug model with the
constraint of demand privacy against colluding users.

######  Theorem V.1 (Privacy-Keys idea with Theorem IV.1).

For a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug model with privacy, the lower convex envelope of
$({\mathsf{M}},{\mathsf{R}})=({\mathsf{N}},0)$ and the following points is
achievable

$\displaystyle({\mathsf{M}}^{\text{\rm HT1+PK}}_{t},{\mathsf{R}}^{\text{\rm
HT1+PK}}_{t})=\left(\frac{{\mathsf{N}}\binom{{\mathsf{K}}-1}{t-1}+\left[\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}-\binom{{\mathsf{K}}-1}{t-1}\right]^{+}}{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}},\frac{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t+1}-\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}}-1)}{t+1}}{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}}\right),\quad\forall
t\in[0:{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>(38)

######  Remark 9 (Sketch of achievability for Theorem V.1).

Theorem V.1 combines ideas from the hotplug achievable scheme without privacy
in Theorem IV.1 with the PK scheme in Theorem III.4. The proof is provided in
Appendix D. The main idea is to apply an MDS code of rate
${\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}}/{\binom{{\mathsf{K}}}{t}}$
to the subfiles, after file partitioning with subpacketization level
$\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}$,
to get a load that is the same as if the system only had
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
overall users (i.e., load as in (28) with ${\mathsf{K}}$ replaced by
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$)
which comes at a price of storing MDS-coded privacy keys, i.e.,

$\displaystyle{\mathsf{M}}^{\text{\rm HT1+PK}}_{t}\geq
1+\frac{t}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}\frac{\binom{{\mathsf{K}}-1}{t-1}}{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{t-1}}({\mathsf{N}}-1)\geq
1+\frac{t}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}({\mathsf{N}}-1),\quad\forall
t\in[0:{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>(39)

Moreover, as we shall see in the numerical examples, Theorem V.1 has a lower
subpacketization level than Theorem III.5 while maintaining a competitive
performance.

For an example of Theorem V.1, please see Sections VII-B2 and VII-B3.
$\hfill\square$

######  Theorem V.2 (Privacy-Keys ideas with Theorem IV.3).

For a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug model with privacy, the following point is achievable

$\displaystyle({\mathsf{M}}^{\text{\rm HT3+PK}},{\mathsf{R}}^{\text{\rm
HT3+PK}})=\left({\mathsf{N}}-\frac{{\mathsf{N}}-1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}},\frac{1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}\right).$
(40)

######  Remark 10 (Sketch of achievability for Theorem V.2).

The proof of Theorem V.2 is provided in Appendix E. Similarly to Theorem IV.3,
we first construct an MDS generator matrix of dimension
${\mathsf{K}}({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1)\times{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$,
partition it into ${\mathsf{K}}$ disjoint parts (one for each user), and use
it populate the caches. Each user needs to cache one addition privacy key,
with memory cost
$1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.
Then the server sends one multicast message such that each active user can
eliminate the interference from files demanded by other users, and extract its
desired information. We have the same load performance as
${\mathsf{R}}^{\text{\rm
HT3}}=1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$,
however the memory size is larger by an additive term
$1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.

For an example of Theorem V.2, please see Section VII-B4. $\hfill\square$

Theorem V.1 and Theorem V.2 adopt the privacy-keys idea into our newly
proposed achievable schemes for hotplug without privacy. Next we present
achievable tradeoff points that leverage the virtual-users ideas. Two tradeoff
points attain optimal performance in the small and large, respectively, memory
regime.

######  Theorem V.3 (Virutal-Users idea to achieve privacy in hotplug and
optimality results).

For a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug system with privacy, the following points are achievable

$\displaystyle({\mathsf{M}}^{\text{\rm HT1\&VU}},{\mathsf{R}}^{\text{\rm
HT1\&VU}})$
$\displaystyle=\left(\frac{1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}},{\mathsf{N}}-\frac{{\mathsf{N}}+1}{2{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}\right),$
(41) $\displaystyle({\mathsf{M}}^{\text{\rm HT\&VU}},{\mathsf{R}}^{\text{\rm
HT+VU}})$
$\displaystyle=\left(\frac{1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}({\mathsf{N}}-1)+1},{\mathsf{N}}\left(1-\frac{1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}({\mathsf{N}}-1)+1}\right)\right),$
(42) $\displaystyle({\mathsf{M}}^{\text{\rm HT3\&VU}},{\mathsf{R}}^{\text{\rm
HT3\&VU}})$
$\displaystyle=\left({\mathsf{N}}\left(1-\frac{1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}{\mathsf{N}}}\right),\
\frac{1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}{\mathsf{N}}}\right).$
(43)

Memory sharing between the point in (42) and the trivial point
$(0,{\mathsf{N}})$ provides the optimal tradeoff for
${\mathsf{M}}\leq\frac{1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}({\mathsf{N}}-1)+1}$.
Memory sharing between the point in (43) and the trivial point
$({\mathsf{N}},0)$ provides the optimal tradeoff for
${\mathsf{M}}\geq{\mathsf{N}}\left(1-\frac{1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}{\mathsf{N}}}\right)$.

######  Remark 11 (Proof Sketch for Theorem V.3).

The achievablity results are an immediate application of the general result
proved in Appendix G that a scheme for a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug system with privacy can be obtained from scheme for a
$({\mathsf{N}}{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}}{\mathsf{K}},{\mathsf{N}})$
hotplug system without privacy. Note that all tradeoffs points in Theorem V.3
only depend on
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
and ${\mathsf{N}}$, and not on ${\mathsf{K}}$ (see also Remark 8).

The schemes HT1&VU in (41) and HT3&VU in (43) are Theorem IV.1 (for $t=1$) and
Theorem IV.3, respectively, used with parameters
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}{\mathsf{N}},{\mathsf{K}}{\mathsf{N}},{\mathsf{N}})$.
The load in (43) is optimal as it meets the non-private cut-set bound
${\mathsf{R}}^{\star}({\mathsf{M}})\geq 1-{\mathsf{M}}/{\mathsf{N}}$.

The scheme HT&VU in (42) extends the optimal classical virtual-users scheme in
[21] to the hotplug model. Note that HT&VU is better than HT2&VU (i.e., HT2&VU
is the scheme obtained from Theorem IV.2 with parameters
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}{\mathsf{N}},{\mathsf{K}}{\mathsf{N}},{\mathsf{N}})$
which gives an achievable scheme with privacy by the virtual-users trick) as
they both meet the converse bound ${\mathsf{R}}_{\text{\rm
p}}^{\star}({\mathsf{M}})\geq{\mathsf{N}}(1-{\mathsf{M}})$, i.e., see (44) for
$\ell={\mathsf{N}}$, but the cache size in (42) is larger than
$\frac{1}{{\mathsf{N}}{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$
(from Theorem IV.2 with parameters
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}{\mathsf{N}},{\mathsf{K}}{\mathsf{N}},{\mathsf{N}})$).

For an example of Theorem V.3, please see Sections VII-B5 and VII-B6.
$\square$

######  Remark 12 (Converse bound for hotplug with privacy).

A trivial converse bound for the hotplug system with privacy can be obtained
by considering the converse bound in [22, Theorem 3] (for demand demand
privacy with colluding users in the classical setting) by replacing
${\mathsf{K}}$ with
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.
The reasoning is that we cannot do better than knowing at the time of
placement which
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
users will be active, and derive the optimal performance of these active
users. The lower bound from [22, Theorem 3] is as follows

$\displaystyle{\mathsf{R}}_{\text{\rm
p}}^{\star}({\mathsf{M}})\geq\max_{\ell\in[{\mathsf{N}}]}\Big{\\{}\ell+\frac{({\mathsf{N}}-\ell)\min\\{\ell+1,{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\\}}{({\mathsf{N}}-\ell)+\min\\{\ell+1,{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\\}}-\ell\
{\mathsf{M}}\Big{\\}},$ (44)

which is known to be good in the low memory regime [22], i.e., note
${\mathsf{R}}_{\text{\rm p}}^{\star}(0)\geq{\mathsf{N}}.$ In Section VII and
Section VIII, we combine the bound in (44) (with privacy) together with [6,
Theorem 2 and Theorem 4] (without privacy) as a converse bound for our plots,
and for the gap result next. $\hfill\square$

######  Theorem V.4 (Gap result for hotplug with prvacy).

For a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug system with privacy, (a) when
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\geq{\mathsf{N}}$,
we have ${\mathsf{R}}^{\text{\rm(YMA\&VU)}}\leq 2.00884\
{\mathsf{R}}_{\text{\rm p}}^{\star}$; and (b) when
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}<{\mathsf{N}}$,
we have ${\mathsf{R}}^{\text{\rm(PK+)}}\geq 5.4606\
{\mathsf{R}}^{\star}_{\text{\rm p}}$.

The proof of Theorem V.4 is provided in Appendix H.

##  VI Examples for Hotplug without Privacy

(a) Cache placement for memory size ${\mathsf{M}}=1$. The third user caches
the two parity bits.

$\displaystyle\begin{array}[]{|c|c c
c|}\hline\cr\text{Demand}&\text{User~{}1}&\text{User~{}2}&\text{User~{}3}\\\
\text{vector}&\text{offline}&\text{offline}&\text{offline}\\\
\hline\cr(1,1,1)&A_{1}&A_{2}&A_{1}+A_{2}\\\
(1,2,1)&A_{2}+B_{1}+B_{2}&A_{2}&A_{2}+B_{1}\\\ \hline\cr\end{array}$ (b)
Delivery for memory size ${\mathsf{M}}=1$ for two different demand vectors as
a function of which user is offline.

$0$$0.5$$1$$1.5$$2$$0$$0.5$$1$$1.5$$2$memory size ${\mathsf{M}}$worst-case
load ${\mathsf{R}}$HT in (32)&(35)YMA+ in (19)decent+ in (20) (c) Memory-load
tradeoffs.

Figure 1: Memory-load tradeoffs for the hotplug system with ${\mathsf{N}}=2$
files,
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=2$
active users, and ${\mathsf{K}}=3$ total users. The converse bound is
achievable by HT schemes in (32) and (35) for any
${\mathsf{K}}\geq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=2$
with ${\mathsf{N}}=2$, and the optimal performance does not depend on
${\mathsf{K}}$.

###  VI-A Optimal Schemes for
${\mathsf{K}}\geq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}={\mathsf{N}}=2$

We aim to show the achievability of the two non-trivial corner points of the
optimal memory-load tradefoff for the classical coded caching setting with two
users and two files [3], which is a converse bound for the hotplug system with
${\mathsf{K}}\geq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}={\mathsf{N}}=2$.
To prove the achievability of the non-trivial corner points $(1/2,1)$ and
$(1,1/2)$ (in addition to the trivial points $(2,0)$ and $(0,2)$) we proceed
as follows. We first combine the coded placement idea of [3] with our MDS
coded placement and attain the performance of HT2 scheme in Theorem IV.2,
which achieves the point $(1/2,1)$ by using MDS coded placement (where coding
is only within each file). We then derive the performance of Theorem IV.1 with
our MDS coded placement to show the achievability of the point $(1,1/2)$.

The case ${\mathsf{K}}=2$ (classical model without privacy) was solved in [3],
so it will not be discussed here. Next, we go into the proof details for the
case of ${\mathsf{K}}=3$ users only, which is the simplest case that
highlights the novelty of our new schemes. The general case ${\mathsf{K}}\geq
3$ follows from the proofs in Appendix A and Appendix B.

####  VI-A1 Case ${\mathsf{K}}=3$ and ${\mathsf{M}}=1/2$: HT2 Scheme in
Theorem IV.2

Our first new scheme with MDS-coded placement attains only one corner point on
the converse bound from [3] (given by the optimal performance of the classical
setting without privacy with two users and two files). In [3] it was shown
that the point $({\mathsf{M}},{\mathsf{R}})=(1/2,1)$ can be achieved by coded
placement in the classical setting without privacy with two users and two
files. We next combine the idea of [3] with our MDS coded placement idea to
show that $({\mathsf{M}},{\mathsf{R}})=(1/2,1)$ is achievable for
${\mathsf{K}}=3$.

Placement Phase: The ${\mathsf{N}}=2$ files are partitioned into two equal-
size subfiles; after partitioning, we treat the files as column vectors of
length 2 over a suitably large finite field as follows

$\displaystyle F_{1}=[A_{1};A_{2}]=:{\mathbf{A}},$ $\displaystyle
F_{2}=[B_{1};B_{2}]=:{\mathbf{B}},$

The cache contents are obtained by coding the files as follows

$\displaystyle Z_{1}=A_{1}+B_{1}={\mathbf{g}}_{1}({\mathbf{A}}+{\mathbf{B}}),\
\text{where}\ {\mathbf{g}}_{1}:=[1,0],$ $\displaystyle
Z_{2}=A_{2}+B_{2}={\mathbf{g}}_{2}({\mathbf{A}}+{\mathbf{B}}),\ \text{where}\
{\mathbf{g}}_{2}:=[0,1],$ $\displaystyle
Z_{3}=A_{1}+A_{2}+B_{1}+B_{2}={\mathbf{g}}_{3}({\mathbf{A}}+{\mathbf{B}}),\
\text{where}\ {\mathbf{g}}_{3}:=[1,1].$

Note that here we have two levels of coding. First we combine all the files
together as ${\mathbf{A}}+{\mathbf{B}}$, and we split this sum into two
symbols $[A_{1}+B_{1};A_{2}+B_{2}]$. Then, we code the two symbols with a rate
$2/3$ MDS code with generator matrix
$[{\mathbf{g}}_{1};{\mathbf{g}}_{2};{\mathbf{g}}_{3}]$ so as to obtain three
coded symbols. Finally, we place one coded symbol in each cache.

Delivery Phase: Out of the ${\mathsf{K}}=3$ users,
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=2$
users will be active during the delivery. When the pair of active users
requests the same file, the server transmits the requested file, and the load
is $1$ file. Otherwise, for the pair of active users $(i,j)$ with $d_{i}=1,\
d_{j}=2,\ i\not=j,$ the signal sent is the server is

$\displaystyle X=({\mathbf{g}}_{j}{\mathbf{A}},\
{\mathbf{g}}_{i}{\mathbf{B}}).$

Decoding: User $i$, who requested file ${\mathbf{A}}$, does

$\displaystyle\begin{bmatrix}Z_{i}-{\mathbf{g}}_{i}{\mathbf{B}}\\\
{\mathbf{g}}_{j}{\mathbf{A}}\\\
\end{bmatrix}=\begin{bmatrix}{\mathbf{g}}_{i}\\\ {\mathbf{g}}_{j}\\\
\end{bmatrix}{\mathbf{A}}.$

Since the matrix $[{\mathbf{g}}_{i};{\mathbf{g}}_{j}]$ is $2\times 2$ and full
rank matrix, user $i$ can invert it and recover file
${\mathbf{A}}=[A_{1};A_{2}]$. Similarly for user $j$, who requested file
${\mathbf{B}}$.

Performance: We can serve any pair of users, regardless of the demands, with
load ${\mathsf{R}}^{\text{\rm HT2}}=1$.

####  VI-A2 Case ${\mathsf{K}}=3$ and ${\mathsf{M}}=1$: HT1 Scheme in Theorem
IV.1

In Fig. 1 we show the cache contents and the delivery signals for memory size
${\mathsf{M}}=1$ and ${\mathsf{K}}=3$ users.

Placement Phase: The files are partitioned into two equal-size subfiles as
$F_{1}=[A_{1},A_{2}]$ and $F_{2}=[B_{1},B_{2}]$. The subfiles of each file are
coded with an MDS code of rate $2/3$. The cache contents are

$\displaystyle Z_{1}$ $\displaystyle=[A_{1},B_{1}],$ $\displaystyle Z_{2}$
$\displaystyle=[A_{2},B_{2}],$ $\displaystyle Z_{3}$
$\displaystyle=[A_{1}+A_{2},B_{1}+B_{2}].$

Note that the third user caches the parity symbols. Fig. 1(a) shows the cache
contents.

Delivery Phase: Regardless of which user is active and what the other two
users demand, each active user must receive the missing half of the demanded
file. Fig. 1(b) gives the signals sent by the server according to Theorem
IV.1, for two different demand vectors as a function of which user is offline;
all the other demand vectors can be dealt similarly.

Decoding: Consider, for example, the case where user $1$ is offline, user $2$
wants $F_{2}=[B_{1},B_{2}]$, and user $3$ wants $F_{1}=[A_{1},A_{2}]$. The
server sends $X=A_{2}+B_{1}+B_{2}$. User $2$ has $[A_{2},B_{2}]$ in its cache
and misses $B_{1}$; by $X-A_{2}-B_{2}$, it recovers $B_{1}$. User $3$ has
$A_{1}+A_{2}$ in its cache and misses another independent linear combination
of $[A_{1},A_{2}]$; by $X-(B_{1}+B_{2})$ he recovers $A_{2}$; then, with
$A_{2}$ and the cached content he recovers $A_{1}$. All other cases are dealt
similarly.

Performance: The load is ${\mathsf{R}}_{1}^{\text{\rm HT1}}=1/2$.

####  VI-A3 Overall Performance

In Fig. 1(c) the red solid line shows the memory-load tradeoff attained by HT1
in (32) and HT2 in (35), which is the lower convex envelope of the corner
points $(1/2,1)$ and $(1,1/2)$, achieved by our novel schemes, with the
trivial corner points $(0,2)$ and $(2,0)$; this optimal tradeoff is actually
achievable for any ${\mathsf{K}}\geq 3$ and only depends on
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}={\mathsf{N}}=2$.
The blue line represents the memory-load tradeoff of YMA+ scheme in Theorem
III.2 with
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})=(2,3,2)$,
where the demand of offline user is chosen the same as the first active user.
For comparison, we also added the performance of the decentralized coded
caching scheme in violet dashed line, given by (20); the decentralized
performance does not depend on ${\mathsf{K}}$ and is an upper bound for the
centralized performance for any ${\mathsf{K}}$. This show that load savings
are possible when the system is aware that only
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=2$
users out of ${\mathsf{K}}\geq 3$ can be active.

###  VI-B Schemes for
${\mathsf{K}}\geq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}={\mathsf{N}}=3$

We consider now the hotplug system with
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=3$
active users and ${\mathsf{N}}=3$ files. We shall show the achievability of
our HT’s schemes in Theorem IV.1, in Theorem IV.2, and in Theorem IV.3.

The classical model with three users, i.e., ${\mathsf{K}}=3$, and three files
was addressed in [12], so we do not repeat it here. The achievable scheme in
[12] for three users and three files gives us the achievability for our
hotplug with
${\mathsf{K}}={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=3$
users, while the converse in [12] for three users and three files gives us a
converse bound for any
${\mathsf{K}}\geq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=3$.
We consider here in detail only the case of ${\mathsf{K}}=4$ users. The
general case ${\mathsf{K}}\geq 4$ follows the proofs in Appendix A, Appendix B
and Appendix C.

####  VI-B1 Case ${\mathsf{K}}=4$ and ${\mathsf{M}}=1/3$: HT2 Scheme in
Theorem IV.2

We can achieve ${\mathsf{R}}^{\text{\rm HT2}}=2$ for memory
${\mathsf{M}}=1/3$, similarly to Section VI-A1.

####  VI-B2 Case ${\mathsf{K}}=4$ and ${\mathsf{M}}=1$: HT1 Scheme in Theorem
IV.1

We can achieve ${\mathsf{R}}^{\text{\rm HT1}}=1$ for memory ${\mathsf{M}}=1$,
similarly to Section VI-A2.

####  VI-B3 Case ${\mathsf{K}}=4$ and ${\mathsf{M}}=2$: HT3 Scheme in Theorem
IV.3

We now explain how scheme HT3 works. Scheme HT3 was not needed in the previous
example.

Placement Phase: We partition each files into three equal length sub-files and
treat the files as column vectors of length 3 over a suitably large finite
field as follows

$\displaystyle F_{1}=[F_{1,1},F_{1,2},F_{1,3}],$ $\displaystyle
F_{2}=[F_{2,1},F_{2,2},F_{2,3}],$ $\displaystyle
F_{3}=[F_{3,1},F_{3,2},F_{3,3}].$

User $k$ is assigned a $2\times 3$ generator matrix

$\displaystyle{\mathbf{G}}_{k}=\begin{bmatrix}{\mathbf{g}}_{k,1}\\\
{\mathbf{g}}_{k,2}\end{bmatrix}:{\mathbf{g}}_{k,i}=[1,\ 2k+i-2,\
(2k+i-2)^{2}],\quad\forall i\in[2],\forall k\in[4].$

Equivalently, if we concatenate all $\\{{\mathbf{g}}_{k,i}:i\in[2],k\in[4]\\}$
together, we obtain a Vandermonde matrix of dimension $8\times 3$. The cache
contents are as follows

$\displaystyle
Z_{k}=\big{[}{\mathbf{G}}_{k}F_{n}:n\in[{\mathsf{N}}]\big{]},\quad\forall
k\in[{\mathsf{K}}].$

Delivery Phase: WLOG, assume the active user triple is
${\mathcal{I}}=\\{1,2,3\\}$ and their demands are
${\mathbf{d}}[{\mathcal{I}}]=[d_{1},d_{2},d_{3}]$. For this set of active
users, the generator matrixes are

$\displaystyle{\mathbf{G}}_{1}=\begin{bmatrix}1&1&1\\\ 1&2&4\end{bmatrix},\
{\mathbf{G}}_{2}=\begin{bmatrix}1&3&9\\\ 1&4&16\end{bmatrix},\
{\mathbf{G}}_{3}=\begin{bmatrix}1&5&25\\\ 1&6&36\end{bmatrix}.$

Define the vectors

$\displaystyle{\mathbf{v}}_{1}=[2,9,39]=[-1,3]{\mathbf{G}}_{2}=[3,-1]{\mathbf{G}}_{3},$
$\displaystyle{\mathbf{v}}_{2}=[2,7,17]=[-3,5]{\mathbf{G}}_{1}=[5,-3]{\mathbf{G}}_{3},$
$\displaystyle{\mathbf{v}}_{3}=[2,5,11]=[-1,3]{\mathbf{G}}_{1}=[3,-1]{\mathbf{G}}_{2},$

which have the following properties

  * •

$[{\mathbf{G}}_{i};{\mathbf{v}}_{i}]$ is a $3\times 3$ full rank matrix, for
all $i\in[3]$; and

  * •

${\mathbf{v}}_{i}$ lies in the linear span of ${\mathbf{G}}_{j}$ for every
$j\in[3]\setminus\\{i\\}$.

The server sends the message $X$ as follows,

$\displaystyle X$ $\displaystyle=\sum_{j\in[3]}{\mathbf{v}}_{j}F_{d_{j}}.$

From the point of view of active user $1$ we can write

$\displaystyle X$
$\displaystyle={\mathbf{v}}_{1}F_{d_{1}}+{\mathbf{v}}_{2}F_{d_{2}}+{\mathbf{v}}_{3}F_{d_{3}}$
$\displaystyle=\underbrace{{\mathbf{v}}_{1}F_{d_{1}}}_{\text{demanded by user
}1}+\ [-3,5]\underbrace{{\mathbf{G}}_{1}F_{d_{2}}}_{\text{cached by user }1}+\
[-1,3]\underbrace{{\mathbf{G}}_{1}F_{d_{3}}}_{\text{cached by user }1},$

so user $1$ can recover ${\mathbf{v}}_{1}F_{d_{1}}$, and further restore
$F_{d_{1}}$ as $[{\mathbf{G}}_{1};{\mathbf{v}}_{1}]$ is full rank. Similarly
for the other two active users.

Performance: We can serve any triplet of users, regardless of their demands,
with load ${\mathsf{R}}^{\text{\rm HT3}}=1/3$.

####  VI-B4 Overall Performance

Fig. 2 shows the memory-load tradeoffs for the hotplug system with
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}={\mathsf{N}}=3$.
In Fig. 2, the lower convex envelop of our three optimal corner points is
shown by the red sold line, which do not depend on ${\mathsf{K}}$. The
converse in Fig. 2, in dash-dotted grey line, is derived from [12, Fig. 5],
which matches the lower convex envelop of our corner points except for
${\mathsf{M}}\in(1/3,1)$ which is open even in the classical setting [12]. The
solid blue line is the YMA+ scheme in (19) for ${\mathsf{K}}=4$ users, while
the violet dotted line is decen+ scheme in (20) also for ${\mathsf{K}}=4$
users.

$0$$0.5$$1$$1.5$$2$$2.5$$3$$0$$0.5$$1$$1.5$$2$$2.5$$3$memory size
${\mathsf{M}}$worst-case load ${\mathsf{R}}$HT in (32) (35) (36)YMA+ in
(19)decen+ in (20)Converse from [12] Figure 2: Memory-load tradeoffs for the
hotplug system with ${\mathsf{N}}=3$ files,
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=3$
active users, and ${\mathsf{K}}=4$ total users. The converse is achievable for
any
${\mathsf{K}}\geq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=3$
with ${\mathsf{N}}=3$, except for ${\mathsf{M}}\in(1/3,1)$ which is open even
in the classical setting [12]. The performance of our scheme does not depend
on ${\mathsf{K}}$.

##  VII Example for Hotplug Model with Demand Privacy

###  VII-A Uncoded Scheme

Each user caches the first ${\mathsf{B}}{\mathsf{M}}/{\mathsf{N}}$ symbols of
each file, and the server sends the remaining
${\mathsf{B}}(1-{\mathsf{M}}/{\mathsf{N}})$ symbols of each file regardless of
the demands; the attained tradeoff is
${\mathsf{R}}^{\text{\rm(uncoded)}}({\mathsf{M}})={\mathsf{N}}-{\mathsf{M}}$;
this scheme is clearly private and the users can compute locally any
functions, not just downloading single files. Thus, we attain the trivial
corner points $({\mathsf{M}},{\mathsf{R}})=(0,{\mathsf{N}})=(0,3)$ and
$({\mathsf{M}},{\mathsf{R}})=({\mathsf{N}},0)=(3,0)$. This holds for any set
of parameters and does not depend on ${\mathsf{K}}$ or
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.

###  VII-B Schemes for
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})=(3,6,3)$
with privacy

We provide an example to illustrate our new proposed schemes for the
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})=(3,6,3)$
hotplug model with demand privacy against colluding users.

####  VII-B1 HT1+PK Scheme in Theorem V.1: Case $t=0$

Placement Phase: For $t=0$ there is no file split and no MDS coding. Each user
$j\in[6]$ only caches a privacy key

$\displaystyle
Z_{j}=T({\mathbf{p}}_{j},1)=\sum_{n\in[3]}p_{j,n}F_{n},\quad\forall j\in[6],$

where ${\mathbf{p}}_{j}=[p_{j,1},p_{j,2},p_{j,3}]$ is sampled i.i.d. uniformly
at random from the set of vectors such that
$\sum_{n\in[3]}p_{j,n}={\mathsf{q}}-1$. The memory size is ${\mathsf{M}}=1$.

Delivery Phase: For active user set ${\mathcal{I}}=\\{a,b,c\\}$ and
corresponding demands ${\mathbf{d}}[{\mathcal{I}}]=(d_{a},d_{b},d_{c})$, we
let ${\mathbf{q}}_{j}={\mathbf{p}}_{j}+{\mathbf{e}}_{d_{j}}$ for every
$j\in{\mathcal{I}}$; note that the entries of each ${\mathbf{q}}_{j}$ sum to
zero in $\mathbb{F}_{\mathsf{q}}$. Then the server sends

$\displaystyle X_{\\{a\\}}$ $\displaystyle={\mathrm{T}}({\mathbf{q}}_{a},1),$
$\displaystyle X_{\\{b\\}}$ $\displaystyle={\mathrm{T}}({\mathbf{q}}_{b},1),$

as well as the query matrix ${\mathbf{Q}}[{\mathcal{I}}]$ and ${\mathcal{I}}$.
We note that there exist two coefficients, say $\alpha_{a}$ and $\alpha_{b}$,
from $\mathbb{F}_{\mathsf{q}}$ such that
${\mathbf{q}}_{c}=\alpha_{a}{\mathbf{q}}_{a}+\alpha_{2}{\mathbf{q}}_{b}$
(because the matrix $[{\mathbf{q}}_{a};{\mathbf{q}}_{b};{\mathbf{q}}_{c}]$ has
rank 2 on $\mathbb{F}_{\mathsf{q}}$), so that

$\displaystyle X_{\\{c\\}}$
$\displaystyle={\mathrm{T}}({\mathbf{q}}_{c},1)=\alpha_{a}{\mathrm{T}}({\mathbf{q}}_{a},1)+\alpha_{b}{\mathrm{T}}({\mathbf{q}}_{b},1),$
(45)

i.e., $X_{\\{c\\}}$ is linearly dependent to $X_{\\{a\\}}$ and $X_{\\{b\\}}$,
and thus need not be sent.

Decoding: From the delivery and the cache content, each user
$j\in{\mathcal{I}}$ has its privacy key ${\mathrm{T}}({\mathbf{p}}_{j},1)$,
thus it can extract the desired file
${\mathrm{T}}({\mathbf{e}}_{d_{j}},1)=F_{d_{j}}$. Thus, having decoded the
whole library, the delivery is obviously private.

Performance: The cache size is ${\mathsf{M}}=1$ and the load is
${\mathsf{R}}_{\text{\rm p}}=2$. Note that in this case
${\mathsf{R}}^{\text{\rm(uncoded)}}(1)=2$ as well, so we do not need to use
our scheme; we have introduce it here to show a case where some multicast
messages need not be sent.

####  VII-B2 HT1+PK Scheme in Theorem V.1: Case $t=1$

Placement Phase: Partition each file as

$\displaystyle F_{n}$ $\displaystyle=[F_{n,1},F_{n,2},F_{n,3}]$
$\displaystyle=[{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{e}}_{\\{1\\}}),{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{e}}_{\\{2\\}}),{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{e}}_{\\{3\\}})],\quad\forall
n\in[3].$

Let ${\mathbf{G}}=[{\mathbf{g}}_{\ell}:\ell\in[6]],$ be the generator matrix
of an MDS code of rate $3/6$ , i.e., any $3$ vectors ${\mathbf{g}}$’s are
linear independent. Sample ${\mathbf{p}}_{j}\in\mathbb{F}_{\mathsf{q}}^{3}$
i.i.d. uniformly at random from the set of vectors such that
$\sum_{n\in[3]}p_{j,n}={\mathsf{q}}-1$, for each user $j\in[6]$. The caches
are populated as

$\displaystyle Z_{j}$
$\displaystyle=\\{{\mathbf{p}}_{j}\\}\cup\\{{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{g}}_{j}):n\in[3]\\}$
$\displaystyle\bigcup\\{{\mathrm{T}}({\mathbf{p}}_{j},{\mathbf{g}}_{\xi_{j,\ell}}):\ell\in[2]\\},\quad\forall
j\in[6],$

where $\\{\xi_{j,1},\xi_{j,2}\\}$ are two indices different from $j$. The
terms of the form ${\mathrm{T}}({\mathbf{p}}_{j},{\mathbf{g}}_{\xi_{j,\ell}})$
are privacy keys that helps in the decoding process. The memory size is
${\mathsf{M}}=5/3$.

Note that, by definition of ${\mathbf{G}}$, its $3\times 3$ sub-matrix
$[{\mathbf{g}}_{j};{\mathbf{g}}_{\xi_{j,1}};{\mathbf{g}}_{\xi_{j,2}}]$ is full
rank for all $j\in[6]$. This fact is important as it allows users to locally
compute certain privacy keys as follows. Consider user $1$. It has cached
${\mathbf{p}}_{1}$ as well as
${\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{g}}_{1})$ for $n\in[3]$. With these,
he can compute

$\displaystyle{\mathrm{T}}({\mathbf{p}}_{1},{\mathbf{g}}_{1})=\sum_{n\in[3]}p_{1,n}{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{g}}_{1}).$

With ${\mathrm{T}}({\mathbf{p}}_{1},{\mathbf{g}}_{1})$ and the cached privacy
keys ${\mathrm{T}}({\mathbf{p}}_{1},{\mathbf{g}}_{\xi_{1,1}})$ and
${\mathrm{T}}({\mathbf{p}}_{1},{\mathbf{g}}_{\xi_{1,2}})$, it can compute

$\displaystyle{\mathrm{T}}({\mathbf{p}}_{1},{\mathbf{g}}_{u})=a_{u,1}{\mathrm{T}}({\mathbf{p}}_{1},{\mathbf{g}}_{1})+a_{u,2}{\mathrm{T}}({\mathbf{p}}_{1},{\mathbf{g}}_{\xi_{1,1}})+a_{u,3}{\mathrm{T}}({\mathbf{p}}_{1},{\mathbf{g}}_{\xi_{1,2}}),\quad\forall
u\in[6]\setminus\\{1,\xi_{1,1},\xi_{1,2}\\},$

since $[{\mathbf{g}}_{1};{\mathbf{g}}_{\xi_{1,1}};{\mathbf{g}}_{\xi_{1,2}}]$
if full rank by the MDS property and thus we can express
${\mathbf{g}}_{u}=a_{u,1}{\mathbf{g}}_{1}+a_{u,2}{\mathbf{g}}_{\xi_{1,1}}+a_{u,3}{\mathbf{g}}_{\xi_{1,2}}\in\mathbb{F}_{\mathsf{q}}^{3}$
for some choice of $[a_{u,1},a_{u,2},a_{u,3}]\in\mathbb{F}_{\mathsf{q}}^{3}$.
In other words, user $u$ has all bilinear combinations of the form
${\mathrm{T}}({\mathbf{p}}_{u},\cdot)$ and
${\mathrm{T}}(\cdot,{\mathbf{g}}_{u}),\ u\in[6]$.

Delivery Phase: As an example, consider active user set
${\mathcal{I}}=\\{4,5,6\\}$ and demands ${\mathbf{d}}[{\mathcal{I}}]=[1,2,3]$.
Let
${\mathbf{q}}_{j}={\mathbf{e}}_{d_{j}}+{\mathbf{p}}_{j},j\in{\mathcal{I}}$.
The server sends

$\displaystyle
X_{\\{4,5\\}}={\mathrm{T}}({\mathbf{q}}_{4},{\mathbf{g}}_{5})+{\mathrm{T}}({\mathbf{p}}_{5},{\mathbf{g}}_{4})={\mathrm{T}}({\mathbf{e}}_{1}+{\mathbf{p}}_{4},{\mathbf{g}}_{5})+{\mathrm{T}}({\mathbf{e}}_{2}+{\mathbf{p}}_{5},{\mathbf{g}}_{4}),$
$\displaystyle
X_{\\{4,6\\}}={\mathrm{T}}({\mathbf{q}}_{4},{\mathbf{g}}_{6})+{\mathrm{T}}({\mathbf{p}}_{6},{\mathbf{g}}_{4})={\mathrm{T}}({\mathbf{e}}_{1}+{\mathbf{p}}_{4},{\mathbf{g}}_{6})+{\mathrm{T}}({\mathbf{e}}_{3}+{\mathbf{p}}_{6},{\mathbf{g}}_{4}),$
$\displaystyle
X_{\\{5,6\\}}={\mathrm{T}}({\mathbf{p}}_{5},{\mathbf{g}}_{6})+{\mathrm{T}}({\mathbf{q}}_{6},{\mathbf{g}}_{5})={\mathrm{T}}({\mathbf{e}}_{2}+{\mathbf{p}}_{5},{\mathbf{g}}_{6})+{\mathrm{T}}({\mathbf{e}}_{3}+{\mathbf{p}}_{6},{\mathbf{g}}_{5}),$

as well as the query matrix ${\mathbf{Q}}[{\mathcal{I}}]$ and the active user
set ${\mathcal{I}}$.

Decoding: We now show each how each active user can correctly decode its
desired subfiles. User $4$ misses
${\mathrm{T}}({\mathbf{e}}_{1},{\mathbf{g}}_{5})$ (in $X_{\\{4,5\\}}$) and
${\mathrm{T}}({\mathbf{e}}_{1},{\mathbf{g}}_{6})$ (in $X_{\\{4,6\\}}$). Since
it has all bilinear combinations of the form
${\mathrm{T}}({\mathbf{p}}_{4},\cdot)$ and
${\mathrm{T}}(\cdot,{\mathbf{g}}_{4})$, it can recover
${\mathrm{T}}({\mathbf{e}}_{1},{\mathbf{g}}_{5})$ (from $X_{\\{4,5\\}}$) and
${\mathrm{T}}({\mathbf{e}}_{1},{\mathbf{g}}_{6})$ (from $X_{\\{4,6\\}}$).
Finally, with
${\mathrm{T}}({\mathbf{e}}_{1},{\mathbf{g}}_{j}):j\in{\mathcal{I}},$ it can
compute $F_{1}$ since $\\{{\mathbf{g}}_{j}:j\in{\mathcal{I}}\\}$ are linearly
independent by the MDS property. Similarly for the other users.

Performance: We showed that $({\mathsf{M}},{\mathsf{R}})=(5/3,3/3)$ is
achievable.

####  VII-B3 HT1+PK Scheme in Theorem V.1: Case $t=2$

Placement Phase: Partition the files into 3 parts as

$\displaystyle F_{n}$
$\displaystyle=[F_{n,\\{1,2\\}},F_{n,\\{1,3\\}},F_{n,\\{2,3\\}}]$
$\displaystyle=[{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{e}}_{\\{1,2\\}}),{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{e}}_{\\{1,3\\}}),{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{e}}_{\\{2,3\\}})],\quad\forall
n\in[3].$

Consider the MDS generator matrix
${\mathbf{G}}=[{\mathbf{g}}_{{\mathcal{T}}}:{\mathcal{T}}\in\Omega_{[6]}^{2}]$
of rate $3/15$, i.e., any $3$ vectors ${\mathbf{g}}$’s are linear independent.
Sample ${\mathbf{p}}_{j}\in\mathbb{F}_{\mathsf{q}}^{3}$ i.i.d. uniformly at
random from the set of vectors such that
$\sum_{i=1}^{3}p_{j,i}={\mathsf{q}}-1$, for each user $j,j\in[6]$. The
placement is

$\displaystyle
Z_{j}=\\{{\mathbf{p}}_{j}\\}\cup\\{{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{g}}_{\\{j,u\\}}):n\in[3],u\in[6]\setminus\\{j\\}\\},\quad
j\in[6].$

As for the case $t=1$, each user $j,j\in[6]$, compute the all privacy keys of
the form
${\mathrm{T}}({\mathbf{p}}_{j},{\mathbf{g}}_{{\mathcal{T}}}):{\mathcal{T}}\in\Omega_{[6]}^{2}$,
and
${\mathrm{T}}(\cdot,{\mathbf{g}}_{\\{j\\}\cup{\mathcal{W}}}):{\mathcal{W}}\in\Omega_{[6]\setminus\\{j\\}}^{1}$.

Delivery Phase: As an example, consider active user set
${\mathcal{I}}=\\{4,5,6\\}$ and demands ${\mathbf{d}}[{\mathcal{I}}]=[1,2,3]$.
Here
$t+1=|{\mathcal{I}}|={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.
The server sends the active set ${\mathcal{I}}$, the query vector
${\mathbf{q}}_{j}={\mathbf{e}}_{d_{j}}+{\mathbf{p}}_{j},j\in{\mathcal{I}}$,
and

$\displaystyle X_{{\mathcal{I}}}$
$\displaystyle=\sum_{j\in{\mathcal{I}}}{\mathrm{T}}({\mathbf{q}}_{j},{\mathbf{g}}_{{\mathcal{I}}\setminus\\{j\\}})$
$\displaystyle={\mathrm{T}}({\mathbf{e}}_{1}+{\mathbf{p}}_{4},{\mathbf{g}}_{\\{5,6\\}})+{\mathrm{T}}({\mathbf{e}}_{2}+{\mathbf{p}}_{5},{\mathbf{g}}_{\\{4,6\\}})+{\mathrm{T}}({\mathbf{e}}_{3}+{\mathbf{p}}_{6},{\mathbf{g}}_{\\{4,5\\}}).$

Decoding: Each active user decodes its desired file similarly to the case
$t=1$, namely user 4 recovers
${\mathrm{T}}({\mathbf{e}}_{1},{\mathbf{g}}_{\\{5,6\\}})$, and user 5 recovers
${\mathrm{T}}({\mathbf{e}}_{2},{\mathbf{g}}_{\\{4,6\\}})$, and user 6 recovers
${\mathrm{T}}({\mathbf{e}}_{3},{\mathbf{g}}_{\\{4,5\\}})$. Then, with the
cached content and leveraging the MDS property, each active user recovers its
desired file.

Performance: This shows that $({\mathsf{M}},{\mathsf{R}})=(15/3,1/3)$ is
achievable. Here $5={\mathsf{M}}>{\mathsf{N}}=3$, i.e., each user caches more
than the whole library. The point to include this case here was to show a case
where users need not store extra privacy keys.

####  VII-B4 HT3+PK Scheme in Theorem V.2

Placement Phase: Partition each file into three equal size parts as

$\displaystyle F_{n}$
$\displaystyle=[F_{n,\\{1,2\\}},F_{n,\\{1,3\\}},F_{n,\\{2,3\\}}]$
$\displaystyle=[{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{e}}_{\\{1,2\\}}),{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{e}}_{\\{1,3\\}}),{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{e}}_{\\{2,3\\}})],\quad\forall
n\in[3].$

Consider the MDS generator matrix
${\mathbf{G}}=[{\mathbf{g}}_{k,i}:k\in[6],i\in[2]]$ of rate $3/12$, i.e., any
$3$ vectors ${\mathbf{g}}$’s are linear independent. Sample
${\mathbf{p}}_{j}\in\mathbb{F}_{\mathsf{q}}^{3}$ i.i.d. uniformly at random
from the set of vectors such that $\sum_{i=1}^{3}p_{j,i}={\mathsf{q}}-1$, for
each user $j\in[6]$.

We select a vector $\xi_{j}$ that it is linear independent of
$\\{{\mathbf{g}}_{j,1},{\mathbf{g}}_{j,2}\\}$. Then we populate the cache of
user $j$ as follows

$\displaystyle Z_{j}$
$\displaystyle=\\{{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{g}}_{j,i}):n\in[3],i\in[2]\\}$
(46a) $\displaystyle\
\cup\\{{\mathrm{T}}({\mathbf{p}}_{j},\xi_{j})\\}\cup\\{{\mathbf{p}}_{j}\\},\quad
j\in[6].$ (46b)

For example, we can choose ${\mathbf{G}}$ be a Vandermonde matrix and $\xi$ be
a vector which independent of ${\mathbf{G}}$ and set

$\displaystyle{\mathbf{G}}=\begin{bmatrix}1&1&1&\ldots&1\\\ 1&2&3&\ldots&12\\\
1&4&9&\ldots&12^{2}\end{bmatrix}^{T},\
\xi_{1}=\xi_{2}=\ldots\xi_{6}=[1,13,13^{2}].$

Note that each user $j,j\in[6]$, despite only caching one privacy key
${\mathrm{T}}({\mathbf{p}}_{j},\xi_{j})$, can compute locally with the help of
its cached content in (46a) all bilinear combinations of the form
${\mathrm{T}}({\mathbf{p}}_{j},\cdot)$; it can also compute all bilinear
combinations of the form ${\mathrm{T}}(\cdot,{\mathbf{g}}_{j,1})$ and
${\mathrm{T}}(\cdot,{\mathbf{g}}_{j,2})$.

Delivery Phase: As an example, consider active user set ${\mathcal{I}}$ and
demands ${\mathbf{d}}[{\mathcal{I}}]$. Let
$\\{\phi^{({\mathcal{I}})}_{j}:j\in[{\mathcal{I}}]\\}$ be a set of vectors of
length $3$ such that:

  * •

for $k\in{\mathcal{I}}\setminus\\{j\\}$, $\phi^{({\mathcal{I}})}_{j}$ lies in
the linear span of $\\{{\mathbf{g}}_{k,1},{\mathbf{g}}_{k,2}\\}$; and

  * •

the matrix
$[\phi^{({\mathcal{I}})}_{j};{\mathbf{g}}_{j,1};{\mathbf{g}}_{j,2}]$ is full
rank for all $j\in[{\mathcal{I}}]$.

For example, for ${\mathcal{I}}=\\{1,2,3\\}$ we can choose

$\displaystyle\phi^{(\\{1,2,3\\})}_{1}=[2,9,39]=-{\mathbf{g}}_{2,1}+3{\mathbf{g}}_{2,2}=3{\mathbf{g}}_{3,1}-{\mathbf{g}}_{3,2},$
$\displaystyle\phi^{(\\{1,2,3\\})}_{2}=[2,7,17]=-3{\mathbf{g}}_{1,1}+5{\mathbf{g}}_{1,2}=5{\mathbf{g}}_{3,1}-3{\mathbf{g}}_{3,2},$
$\displaystyle\phi^{(\\{1,2,3\\})}_{3}=[2,5,11]=-{\mathbf{g}}_{1,1}+3{\mathbf{g}}_{1,2}=3{\mathbf{g}}_{2,1}-1{\mathbf{g}}_{2,2}.$

Let
${\mathbf{q}}_{j}={\mathbf{e}}_{d_{j}}+{\mathbf{p}}_{j},j\in{\mathcal{I}}$.
The server sends ${\mathbf{Q}}[{\mathcal{I}}]$ and ${\mathcal{I}}$ and

$\displaystyle X_{\mathcal{I}}$
$\displaystyle=\sum_{j\in{\mathcal{I}}}{\mathrm{T}}({\mathbf{q}}_{j},\phi^{({\mathcal{I}})}_{j})$
$\displaystyle={\mathrm{T}}({\mathbf{e}}_{d_{j}},\phi^{({\mathcal{I}})}_{j})+\text{``terms
known at user~{}$j$''},\quad\forall j\in{\mathcal{I}}.$

Decoding: The sent multicast message allows each active user to recover
${\mathrm{T}}({\mathbf{e}}_{d_{j}},\phi^{({\mathcal{I}})}_{j}),j\in{\mathcal{I}}.$
Indeed, for ${\mathcal{I}}=\\{1,2,3\\}$ and user $1$, we can write

$\displaystyle X_{\\{1,2,3\\}}$
$\displaystyle={\mathrm{T}}({\mathbf{q}}_{1},\phi^{(\\{1,2,3\\})}_{1})+{\mathrm{T}}({\mathbf{q}}_{2},\phi^{(\\{1,2,3\\})}_{2})+{\mathrm{T}}({\mathbf{q}}_{1},\phi^{(\\{1,2,3\\})}_{3})$
$\displaystyle={\mathrm{T}}({\mathbf{e}}_{d_{1}}+{\mathbf{p}}_{1},\phi^{(\\{1,2,3\\})}_{1})+{\mathrm{T}}({\mathbf{q}}_{2},-3{\mathbf{g}}_{1,1}+5{\mathbf{g}}_{1,2})+{\mathrm{T}}({\mathbf{q}}_{3},-{\mathbf{g}}_{1,1}+3{\mathbf{g}}_{1,2})$
$\displaystyle={\mathrm{T}}({\mathbf{e}}_{d_{1}},\phi^{(\\{1,2,3\\})}_{1})+\text{``terms
known at user~{}1''},$

so it recovers ${\mathrm{T}}({\mathbf{e}}_{d_{1}},\phi^{(\\{1,2,3\\})}_{1})$.
User $1$ also has ${\mathrm{T}}({\mathbf{e}}_{d_{1}},{\mathbf{g}}_{1,1})$ and
${\mathrm{T}}({\mathbf{e}}_{d_{1}},{\mathbf{g}}_{1,2})$, and thus by the MDS
property, it can recover file $F_{d_{1}}$.

Performance: The point $({\mathsf{M}},{\mathsf{R}})=(7/3,1/3)$ is achievable.

####  VII-B5 HT&VU Scheme in Theorem V.3

Placement Phase: Partition each file into $7$ parts as,

$\displaystyle F_{n}$
$\displaystyle=(F_{n,\ell}:\ell\in[7])=({\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{e}}_{\ell}):\ell\in[7]),\
\forall n\in[3].$

Consider the MDS generator matrix ${\mathbf{G}}=[{\mathbf{g}}_{j}:j\in[18]]$
of rate $7/18$, i.e., any $7$ vectors ${\mathbf{g}}$’s are linear independent.
Sample the scalar $p_{j}\in[3]$ i.i.d. uniformly at random for each user
$j\in[6]$.

The placement is,

$\displaystyle
Z_{j}=\\{p_{j}\\}\cup\\{\sum_{n=1}^{3}{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{g}}_{3(j-1)+p_{j}})\\},\
\forall j\in[6].$

Delivery Phase: Let $\Psi:[3]^{3}\rightarrow[3]^{3}$ denote the cyclic shift
operator, such that $\Psi(1,2,3)=(3,1,2)$. Let us denote a vector
$\mathbb{I}_{3}:=(1,2,3)$, and define the subtraction under modular $3$ as
$\ominus$, for example $1\ominus 1=0,1\ominus 2=2$. Consider a active user set
${\mathcal{I}}=\\{j_{1},j_{2},j_{3}\\}\in\Omega_{6}^{3}$ and their demands
$d_{{\mathcal{I}}}\in\\{d_{j_{1}},d_{j_{2}},d_{j_{3}}\\}$, the server creates
an vector of length $3$ for each user $j\in{\mathcal{I}}$ as

$\displaystyle\widetilde{{\mathbf{d}}}_{j}:=\Psi^{p_{j}\ominus
d_{j}}(\mathbb{I}_{3}),$ (47)

where the operator $\Psi^{i}$ denotes the $i$-times cyclic shift operator,
which is the operator $\Psi$ applied $i$ times. We define the expended active
user set $\widetilde{{\mathcal{I}}}$ of size $9$ as,

$\displaystyle\widetilde{{\mathcal{I}}}:=\left((j-1){\mathsf{N}}+\ell:j\in{\mathcal{I}},\ell\in[3]\right),$
(48)

and

$\displaystyle p_{\mathcal{I}}\ominus d_{\mathcal{I}}:=\left(p_{j_{1}}\ominus
d_{j_{1}},p_{j_{2}}\ominus d_{j_{2}},p_{j_{3}}\ominus d_{j_{3}}\right),$ (49)

Therefore, the server sends $(\widetilde{{\mathcal{I}}},p_{\mathcal{I}}\ominus
d_{\mathcal{I}})$, and

$\displaystyle
X=\left\\{{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{g}}_{j}):j\in\widetilde{{\mathcal{I}}},\ell\in[3],n\in[3]\setminus\\{\tilde{d}_{j,\ell}\\}\right\\},$

where $\tilde{d}_{j,\ell}$ is the $\ell$-th element of
$\widetilde{{\mathbf{d}}}_{j}$.

Decoding: User $j\in[{\mathcal{I}}]$, who knows
$\\{{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{g}}_{3(j-1)+p_{j}}):n\in[3]\setminus\\{d_{j}\\}\\}$
from $X$, can “unlocks”
${\mathrm{T}}({\mathbf{e}}_{d_{j}},{\mathbf{g}}_{3(j-1)+p_{j}})$ from its
cache. Next, for every $i\in{\mathcal{I}}$ and $\ell\in[3]$ such that
$\tilde{d}_{i,\ell}\neq d_{j}$, the bilinear combination
${\mathrm{T}}({\mathbf{e}}_{d_{j}},{\mathbf{g}}_{3(i-1)+\ell})$ is contained
in $X$, in total $6$. Since user $j$ knows $7$ independent coded subfiles and
the MDS rate is $7/18$, it can restore $F_{d_{j}}$.

Performance: The point $({\mathsf{M}},{\mathsf{R}})=(1/7,18/7)$ is achievable.

####  VII-B6 HT1&VU and HT3&VU Schemes in Theorem V.3

These tradeoffs is attained from non-private HT1 and HT3 Schemes respectively
in Theorem IV.3 with parameters
$(\widetilde{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}},\widetilde{{\mathsf{K}}},{\mathsf{N}})=(9,18,3)$
and a restricted demands. Each real user $j\in[6]$, together with 2 extra
virtual users forms a group. The server populates the cache content for all
users including virtual ones, then the user uniformly chooses one content from
each group at random. In the delivery phase, once the real users sent their
demands, the server transmits an expended demands and expended active user
set, as shows in (47) and (48) respectively. Then it transmits the multicast
messages generated by expended active set and demands given by the non-private
hotplug scheme. The examples for HT1 and HT3 schemes are referred to Section
VI.

Performance: The point $({\mathsf{M}},{\mathsf{R}})=(1/3,14/6)$ and
$({\mathsf{M}},{\mathsf{R}})=(24/9,1/9)$ are achievable respectively.

####  VII-B7 Overall Performance

Fig. 3 compares the performance of the PK+ scheme in Theorem III.5, the YMA&VU
scheme in Theorem III.6, and the new schemes, i.e., the line labeled ‘HT+PK’
is the convex hull of the corner points from Theorems V.1 and V.2, and the
three tradeoffs labeled ‘HT&VU’ from Theorem V.3. The converse bound is
derived as detailed in Remark 12.

This is a case where our HT+PK schemes outperforms the PK+ scheme but overall
YMA&VU is better. Two tradeoff derived from HT&VU and HT3&VU schemes
respectively, are optimal, and the tradeoff derived from HT1&VU has a similar
performance with YMA&VU. In Section VIII we show that this is not always the
case. We choose this case as an example as it is the smallest example where we
can clearly and simply show all the new aspects of the proposed schemes.

$0$$0.5$$1$$1.5$$2$$2.5$$3$$0$$0.5$$1$$1.5$$2$$2.5$$3$memory size
${\mathsf{M}}$worst-case load ${\mathsf{R}}$HT&VU (41)(42)(43)HT+PK
(38)(40)PK+ (29)YMA&VU (30)Converse [6, 22] Figure 3: Memory-load tradeoffs
for the hotplug model with privacy when
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})=(3,6,3)$.

##  VIII Numerical Evaluations

In this Section we provide some numerical examples, to illustrate the
performance of our new schemes. For the hotplug model without privacy, the
schemes we mention in this section include Theorem IV.1 and Theorem IV.3; the
converse is derived from [6, Theorems 2 and 4]. Theorem IV.2 is used in
examples with
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\geq{\mathsf{N}}$.
For the hotplug model with privacy, the schemes in this section include
Theorem V.1 and Theorem V.2; the converse is derived as detailed in Remark 12.

$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$$0$$1$$2$$3$$4$$5$memory size
${\mathsf{M}}$worst-case load ${\mathsf{R}}$HT (32)(36)YMA+ (19)Converse [6]
(a) Case
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})=(5,15,20)$.

$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$$0$$2$$4$$6$$8$$10$$12$memory size
${\mathsf{M}}$worst-case load ${\mathsf{R}}$HT (32)(36)YMA+ (19)Converse [6]
(b) Case
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})=(12,15,20)$.

Figure 4: Memory-load tradeoffs for the hotplug system with
$({\mathsf{K}},{\mathsf{N}})=(15,20)$ and different values of
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.
$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$$0$$1$$2$$3$$4$$5$memory size
${\mathsf{M}}$worst-case load ${\mathsf{R}}$HT (32)(36)YMA+
(${\mathsf{K}}=20$) (19)YMA+ (${\mathsf{K}}=6$) (19)Converse [6] Figure 5:
Memory-load tradeoffs for the hotplug system for with
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})=(5,20)$
and various values of ${\mathsf{K}}$.

###  VIII-A Hotplug without Privacy

$\bullet$ Case
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})=(5,20)$:
Fig. 5 shows the memory-load tradeoff for the case
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})=(5,20)$
and various ${\mathsf{K}}$. The performance of HT schemes and of the converse
bound does not depend on the value of ${\mathsf{K}}$, while that of the YMA+
scheme worsen as ${\mathsf{K}}$ increases. The last segment is optimal as HT3
scheme matches the converse bound.

$\bullet$ Case $({\mathsf{K}},{\mathsf{N}})=(15,20)$: Fig. 4 shows the memory-
load tradeoff for two different values of
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
for fixed $({\mathsf{K}},{\mathsf{N}})=(15,20)$. For
${\mathsf{M}}\in[0,{\mathsf{N}}/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}]$
in Fig. 4(a), the HT1 scheme with MDS coded placement in Theorem IV.1
outperforms the YMA+ scheme and is exactly optimal in the small memory regime.
The last segment is optimal as HT3 scheme matches the converse bound.

$0$$5$$10$$15$$20$$0$$5$$10$$15$$20$memory size ${\mathsf{M}}$worst-case load
${\mathsf{R}}$HT+PK (38)(40)PK+ (29)YMA&VU (30)Converse [6, 22] (a) Case
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})=(12,30,20)$.

$0$$5$$10$$15$$20$$0$$5$$10$$15$$20$memory size ${\mathsf{M}}$worst-case load
${\mathsf{R}}$HT+PK (38)(40)PK+ (29)YMA&VU (30)Converse [6, 22] (b) Case
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})=(25,30,20)$.

Figure 6: Memory-load tradeoffs for the hotplug model with private demands
when $({\mathsf{K}},{\mathsf{N}})=(30,10)$ and various
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.
$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$10^{9}$memory
size ${\mathsf{M}}$subpacketization levelPK+ (38)(40)HT+PK (29) Figure 7:
Subpacketization level for the hotplug system with private demands when
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})=(25,30,20)$.

###  VIII-B Hotplug with Privacy

$\bullet$ Fig 6 shows the memory-load tradeoffs for two values of
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
for fixed $({\mathsf{K}},{\mathsf{N}})=(30,20)$. In Fig 6(a), with
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=12$,
HT+PK schemes have good load performance in both small and large memory
regimes. In Fig 6(b), with
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=20$,
HT+PK schemes have good load performance only in small memory regime. We do
not provide the HT&VU tradeoffs from Theorem V.3 as they are very closed to
two trivial corner points, i.e. $(0,{\mathsf{N}})$ and $({\mathsf{N}},0)$.

$\bullet$ Fig. 7 shows the subpacketization level for the case
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})=(30,25,10)$.
The subpacketization level of HT+PK scheme is better than the PK+ scheme; we
did not plot the subpacketization level of the YMA&VU scheme since it is
doubly exponential in the number of files, and thus way off the shown scale.

##  IX Conclusion

In this paper, we introduced the novel hotplug coded caching model to address
a practical limitation of the original coded caching system, namely, to allow
the server to start the delivery phase for a subset of active users, while the
remaining users are offline. We proposed new achievable schemes exploit MDS
codes for the placement phase, and are exactly optimal in some regimes, and
optimal to within a factor of 2 otherwise. This work shows that load savings
are possible when the system is aware that only a subset of users will be
active. Interestingly, when optimality can be be shown, the optimal
performance only depends on the number active users and not on the total
number of users; we are tempted to conjecture that this is true in general.

We also considered the hotplug model with demand privacy against colluding
users. New achievable schemes that combine ideas from privacy-keys, virtual-
users, and MDS coding are proposed. The performance of the new schemes is
better in general than baseline schemes, and attain lower subpacketization
levels. In the low and large memory regime we can prove exact optimality, and
a constant gap otherwise.

Current work includes further extending exact optimality results, including to
scalar linear file retrieval, and to different statistical models for the
users’ activity.

##  Appendix A Proof of Theorem IV.1

##### Placement Phase

Fix
$t\in[0:{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}]$
and partition each file into
$\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}$
equal-size subfiles as

$\displaystyle
F_{i}=(F_{i,{\mathcal{W}}}:{\mathcal{W}}\in\Omega_{[{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}]}^{t}),\quad\forall
i\in[{\mathsf{N}}].$ (50)

Then, for every $i\in[{\mathsf{N}}]$, we treat the subfiles of each file as
the information symbols of an MDS code with generator matrix ${\mathbf{G}}$ of
dimension
$\binom{{\mathsf{K}}}{t}\times\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}$,
i.e., any
$\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}$
rows are linearly independent over $\mathbb{F}_{{\mathsf{q}}}$, where
${{\mathsf{q}}}$ is a sufficiently large prime number. The MDS-coded symbols
are

$\displaystyle\begin{bmatrix}C_{i,{\mathcal{T}}_{1}}\\\
C_{i,{\mathcal{T}}_{2}}\\\ \vdots\\\
C_{i,{\mathcal{T}}_{\binom{{\mathsf{K}}}{t}}}\end{bmatrix}$
$\displaystyle={\mathbf{G}}\ \begin{bmatrix}F_{i,{\mathcal{W}}_{1}}\\\
F_{i,{\mathcal{W}}_{2}}\\\ \vdots\\\
F_{i,{\mathcal{W}}_{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}}}\end{bmatrix},\quad\forall
i\in[{\mathsf{N}}].$ (51)

The cache contents are

$\displaystyle
Z_{k}=(C_{i,{\mathcal{T}}}:i\in[{\mathsf{N}}],{\mathcal{T}}\in\Omega_{[{\mathsf{K}}]}^{t},k\in{\mathcal{T}}),\quad\forall
k\in[{\mathsf{K}}].$ (52)

Thus the memory size is ${\mathsf{M}}^{\text{\rm HT1}}_{t}$ as in Theorem
IV.1, which is the cache required by the MAN scheme for ${\mathsf{K}}$ users
divided by the rate of the MDS code used to ‘pre-code’ each file.

##### Delivery Phase

For any set of active users indexed by
${\mathcal{I}}\in\Omega_{[{\mathsf{K}}]}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$
with demands
$d_{\mathcal{I}}=[d_{i_{1}},d_{i_{2}},\ldots,d_{i_{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}}]$,
the server forms the the following multicast signals