We define $\alpha\triangleq \frac{\rho}{P}$ as the *connectivity* of the network, where $0 \leq \alpha \leq 1$. For $j \in [K]$, let $\mathcal{Z}_j$ denote the set of servers $\mathrm{U}_j$ connects to, where $|\mathcal{Z}_j|=\rho$, and $d_j \in [N]$ denotes the index of the file it requests. For example, in Fig. \[fig:f1\](a), $\mathcal{Z}_1=\{ \mathrm{S}_1, \mathrm{S}_2 \}$, $\mathcal{Z}_2=\{ \mathrm{S}_1, \mathrm{S}_2 \}$, $\mathcal{Z}_3=\{ \mathrm{S}_2, \mathrm{S}_3 \}$ and $\mathcal{Z}_4=\{ \mathrm{S}_2, \mathrm{S}_3 \}$. Let the demand vector be denoted by $\mathbf{d}\triangleq(d_1, d_2,..., d_K)$. The topology of the network, i.e., which users are connected to which servers, and the demands of the users are revealed to the servers at the beginning of the delivery phase.

The complete library must be stored at the servers in a coded manner to provide redundancy, since each user connects only to a random subset of the servers. Since any user should be able to reconstruct any requested file from its own cache memory and the servers it is connected to, the total cache capacity of a user and any $\rho$ servers must be sufficient to recover the whole library; that is, we must have $M_U+\rho M_S\geq N$.

Let $\mathcal{K}_p$ denote the set of users served by $\mathrm{S}_p$, for $p\in [P]$, and define 