and all files are of the same size. To fully utilize this homogeneity, we define the following useful notations. For any positive integer $i$, we denote the set of all permutations of $\{1,...,i\}$ by $\mathcal{P}_i$. For any set $\mathcal{S}\subseteq \{1,...,i\}$ and any permutation $p\in \mathcal{P}_i$, we define $ p\mathcal{S}=\{p(s)\ |\ s\in{S}\}$. For any subsets $\mathcal{A}\subseteq \{1,...,N\}$ and $\mathcal{B}\subseteq \{1,...,K\}$, we define $$\begin{aligned}
                H^*(W_{\mathcal{A}},Z_{\mathcal{B}})\triangleq \frac{1}{N!K!} \sum_{p\in \mathcal{P}_N, q\in \mathcal{P}_K} H(W_{p\mathcal{A}},Z_{q\mathcal{B}}).
            \end{aligned}$$ Similarly, we define the same notation for conditional entropy in the same way. We can verify that the functions defined above satisfies all Shannon’s inequalities. I.e., for any sets of random variables $\mathcal{A}$, $\mathcal{B}$ and $\mathcal{C}$, we have $$\begin{aligned}
                H^*(\mathcal{A}|\mathcal{B})\geq H^*(\mathcal{A}|\mathcal{B}, \mathcal{C}).
            \end{aligned}$$

Note that from the homogeneity of the problem, for any $\epsilon$-achievable rate $R$, Lemma \[lemma:ga\] holds for any demands, under any possible relabeling of the users. Thus, by considering the class of demands where at least $\min\{N,K\}$ files are requested, we have $$\begin{aligned}
                R\geq &\frac{1}{F}(\sum_{k=1}^{\min\{N,K\}} H(W_{q(k)}|Z_{\{p(1),...,p(k)\}}, W_{\{q(1),...,q(k-1)\}}))\nonumber\\&- \min\{N,K\}(\frac{1}{F}+\epsilon)
                \end{aligned}$$ for any $p\in \mathcal{P}_K$ and $q\in \mathcal{P}_N$. Averaging the above bound over all possible $p$ and $q$, we have $$\begin{aligned}
                R\geq &\frac{1}{F}(\sum_{k=1}^{\min\{N,K\}} H^*(W_{k}|Z_{\{1,...,k\}}, W_{\{1,...,k-1\}}))\nonumber\\&- \min\{N,K\}(\frac{1}{F}+\epsilon).
                \end{aligned}$$ Recall that $R^*$ is defined to be the minimum $\epsilon$-achievable rate over 