Formulation {#sec:sys}
====================================

In this section, we formally introduce the system model for the caching problem. Then we define the rate-memory tradeoff for both peak rate and average rate based on the introduced framework, and state the corresponding main problems studied in this paper.

System Model
------------

We consider a system with one server connected to $K$ users through a shared, error-free link (see Fig. \[fig:net\]). The server has access to a database of $N$ files $1, . . . , N$, each of size $F$ bits. We assume that the contents of all files, denoted by $W_1,...,W_N$, are i.i.d. random variables, each of which is uniformly distributed on set $\{1,...,2^F\}$. Each user $k$ has an isolated cache memory of size $MF$ bits, where $M\in[0,N]$. For convenience, we define a parameter $r=\frac{KM}{N}$.

![Caching system considered in this paper. The figure illustrates the case where $K=N=3$, and $M=1$.[]{data-label="fig:net"}](net.pdf){width="50.00000%"}

The system operates in two phases: a placement phase and a delivery phase. In the placement phase, the users are given access to the entire database. Each user can fill the contents of their caches using the database without knowledge of their future demands.[^7] We denote the cached content of each user $k$ 