$E$ happens. $\lfloor x \rfloor$ denotes the largest integer less than or equal to $x$. $\lceil x \rceil$ denotes the smallest integer greater than or equal to $x$.

Problem Setting {#sec:app:1}
===============

We consider the system model illustrated in Fig. \[fig:f1\] with $P$ servers, denoted by $\mathrm{S}_1, \mathrm{S}_2, \ldots, \mathrm{S}_P$, serving $K$ users, denoted by $\mathrm{U}_1,\mathrm{U}_2, \ldots, \mathrm{U}_K$. There is a library of $N$ files $W_1, W_2, \ldots, W_N$, each of length $F$ bits uniformly distributed over $[2^{F}]$. Each user has access to a local cache memory of capacity $M_UF$ bits, $0 \leq M_U \leq N$, while each server has a storage memory of capacity $M_SF$ bits. The caching scheme consists of two phases: placement phase and delivery phase. We consider a centralized placement scenario as in [@maddah], which is carried out centrally with the knowledge of the servers and the users participating in the delivery phase. However, neither the user demands, nor the network topology is known in advance during the placement phase. In the delivery phase, we assume that each user randomly connects to $\rho$ servers out of $P$ with a uniform distribution over all $\rho-$subsets, where $\rho \leq P$, and requests a single file from the library. 