The Capacity of Private Information Retrieval from Decentralized Uncoded Caching Databases

Abstract

We consider the private information retrieval (PIR) problem from decentralized uncoded caching databases. There are two phases in our problem setting, a caching phase, and a retrieval phase. In the caching phase, a data center containing all the K files, where each file is of size L bits, and several databases with storage size constraint $\mu KL$ bits exist in the system. Each database independently chooses $\mu KL$ bits out of the total $KL$ bits from the data center to cache through the same probability distribution in a decentralized manner. In the retrieval phase, a user (retriever) accesses N databases in addition to the data center, and wishes to retrieve a desired file privately. We characterize the optimal normalized download cost to be $D^{*}={\sum }_{n=1}^{N+1}\left(\genfrac{}{}{0pt}{}{N}{n-1}\right){\mu }^{n-1}{(1-\mu )}^{N+1-n}\left(1+\frac{1}{n}+\cdots +\frac{1}{n^{K-1}}\right)$. We show that uniform and random caching scheme which is originally proposed for decentralized coded caching by Maddah-Ali and Niesen, along with Sun and Jafar retrieval scheme which is originally proposed for PIR from replicated databases surprisingly results in the lowest normalized download cost. This is the decentralized counterpart of the recent result of Attia, Kumar, and Tandon for the centralized case. The converse proof contains several ingredients such as interference lower bound, induction lemma, replacing queries and answering string random variables with the content of distributed databases, the nature of decentralized uncoded caching databases, and bit marginalization of joint caching distributions.

1. Introduction

Private information retrieval (PIR) refers to the problem of downloading a desired file from distributed databases while keeping the identity of the desired file private against the databases. In the classical setting of PIR (see Figure 1), there are N non-communicating databases, each storing the same set of K files. The user (retriever) wishes to download one of these K files without letting the databases know the identity of the desired file. A simple but highly inefficient way is to download all the files from a particular database, which results in the normalized download cost of $\frac{D}{L}=K$, where L is the file size and D is the total number of downloaded bits from the N databases. The PIR problem has originated in the computer science community [1,2,3,4,5] and has drawn attention in the information theory society with early examples [6,7,8,9,10,11]. Recently, Sun and Jafar [12] have characterized the optimal normalized download cost for the classical PIR problem to be $\frac{D}{L}=\left(1+\frac{1}{N}+\cdots +\frac{1}{N^{K-1}}\right)$. After [12], many interesting variants of the classical PIR problem have been investigated in [13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54]. Most of these previous works consider the case where the contents of the databases are fixed a priori in an uncontrollable manner; a vast majority of them consider the case of replicated databases where each database stores the same set of K files, and many of the rest consider the case of coded databases where each database stores coded versions of the original files.

Coded caching refers to the problem of placing files in users’ local storage caches ahead of time properly and designing efficient delivery schemes at the time of specific user requests in such a way to minimize the traffic during the delivery phase. In the original setup [55] (see Figure 1), a server with K files connects to N users through an error-free shared link, where each user has a local memory which can store up to M files. The system operates in two phases, a placement phase, and a delivery phase. In the placement phase, the server places the files into each user’s local memory. In the delivery phase, each user requests a file from the server, and the server aims to satisfy all the requests with the lowest traffic load. If the set of users in the two phases are identical, the server can arrange the content in each user’s local memory in an optimized manner, which is called centralized coded caching. Reference [55] proposes a symmetric batch caching scheme, which is shown to be optimal for the case of centralized uncoded placement in [56]. If the set of users in the two phases varies, the server cannot arrange the files in user caches in a centralized manner. Instead, the server treats each user identically and independently which is called decentralized coded caching [57]. Reference [57] proposes a uniform and random caching scheme, which is shown to be optimal for the case of decentralized uncoded placement in [56]. Many interesting variants of coded caching problems have been investigated in [58,59,60,61,62,63,64,65,66,67,68,69,70,71,72].

The references that are most closely related to our work here are [38,44]. References [38,44] formulate a new type of PIR problem where the content of each database is not fixed a priori, but can be optimized to minimize the download cost. These papers bring PIR and coded caching problems together in a practically relevant and theoretically interesting manner. In their problem setting (see Figure 2), there is a data center (server) containing all the K files where each file is of size L bits, and the system operates in two phases. In the caching phase, there are N databases in the system with a common storage size constraint $\mu$, i.e., each database can at most store $\mu KL$ bits, $\frac{1}{N}\le \mu \le 1$. In the retrieval phase, a user (retriever) accesses the N databases, and wishes to download a desired file privately. They consider the problem of optimally storing content from the data center to the databases in the caching phase in such a way that the normalized download cost during the retrieval phase is minimized. They focus on the centralized uncoded caching case, i.e., the set of users in the two phases are identical so that the data center can assign the files to each database in a centralized manner, and caching is uncoded in that each database stores a subset of the bits from the data center (no coding), i.e., each database stores $\mu KL$ bits out of the total $KL$ bits. Surprisingly, they show that the symmetric batch caching scheme proposed in [55] results in the lowest normalized download cost in the retrieval phase.

We consider the PIR problem from decentralized uncoded caching databases. In our problem setting (see Figure 3), the system also operates in two phases as in [38,44]. However, the set of databases active in the two phases is different, and we do not know in advance which databases the user (retriever) can access in the retrieval phase. Therefore, we consider a decentralized setting for the caching phase, i.e., the data center treats each database identically and independently, or equivalently, each database chooses a subset of bits to store independently according to the same probability distribution. Here, we aim at designing the optimal probability distribution in the caching phase and PIR scheme in the retrieval phase such that the normalized download cost in the retrieval phase is minimized. Another main difference between our work and references [38,44] is that, in the caching phase, references [38,44] require that the N databases altogether can reconstruct the entire K files, i.e., when the user (retriever) connects to the N databases, their collective content is equivalent to the content in the data center, so the user (retriever) can download any desired file. While this can be guaranteed in the centralized setting, in the decentralized setting, where cache placement is probabilistic, we cannot guarantee that any given N databases contain all the bits that exist in the data center. Thus, in order to formulate a meaningful PIR problem, we allow the user (retriever) access the data center as well as the databases in the retrieval phase. Finally, we remark about another sub-branch of PIR literature that considers caching: [30,31,32,33,39,52]; there the user (retriever) itself has a cache memory where it stores a subset of the bits available in the databases. That problem is unrelated to the setting here even though it is also referred to as PIR with caching; in essence, it is PIR with side information.

In this work, for PIR from decentralized caching databases, we show that uniform and random caching scheme, originally proposed in [57] for decentralized coded caching, results in the lowest expected normalized download cost in the retrieval phase. For the achievability, we apply the PIR scheme in [12] successively for all resulting subfile parts. For the converse, we first apply the lower bound derived in [44], which replaces the random variables for queries and answering strings by the content of the distributed databases in a novel manner extending the lower bounding techniques in Lemma 5 and Lemma 6 in [12]. To compare different probability distributions in the caching phase, we focus on the marginal distributions on each separate bit. Then, by using the nature of decentralization and uncoded caching, we further lower bound the normalized download cost. Finally, we show the matching converse for the expected normalized download cost to be $\frac{D}{L}={\sum }_{n=1}^{N+1}\left(\genfrac{}{}{0pt}{}{N}{n-1}\right){\mu }^{n-1}{(1-\mu )}^{N+1-n}\left(1+\frac{1}{n}+\cdots +\frac{1}{n^{K-1}}\right)$, which yields an exact capacity result for the problem.

2. System Model

We consider a system consisting of one data center and several databases (at least N databases). The data center stores K independent files, labeled as $W_1$, $W_2$, …, $W_K$, where each file is of size L bits. Therefore,

$$\begin{array}{c}\hfill H\left(W_1\right)=\cdots =H\left(W_K\right)=L,H(W_1,\dots ,W_K)=H\left(W_1\right)+\cdots +H\left(W_K\right).\end{array}$$

(1)

Each database has a storage capacity of $\mu KL$ bits, where $0\le \mu \le 1$.

The system operates in two phases: In the caching phase, we consider the case of uncoded caching, i.e., each database stores a subset of bits from the data center. Due to the storage size constraint, each database at most stores $\mu KL$ bits out of the total $KL$ bits from the data center. Here, we denote i-th database as DB${}_i$ and use random variable $Z_i$ to denote the stored content in DB${}_i$. Therefore, the storage size constraint for DB${}_i$ is

$$\begin{array}{c}\hfill H\left(Z_i\right)\le \mu KL.\end{array}$$

(2)

We consider the decentralized setting for the caching phase, i.e., each database chooses a subset of bits to store independently according to the same probability distribution, denoted by $P_H$. Rigorously, let random variable $H_i$ denote the indices of the stored bits in DB${}_i$. For N databases, the decentralized caching scheme $\mathcal{H}$ can be specified as

$$\begin{array}{c}\hfill \mathbb{P}(\mathcal{H}=(H_1,\dots ,H_N))=\prod _{i=1}^N{P}_H\left(H_i\right).\end{array}$$

(3)

In the retrieval phase, the user accesses N databases and the data center. We note that we do not know in advance which N databases are available or which N databases the user will have access to. Here, we also assume that in the retrieval phase, the data center and N databases do not communicate with each other (no collusion). To simplify the notation, we use DB${}_0$ to denote the data center, and therefore $Z_0=(W_1,\dots ,W_K)$ since the data center stores all the K files. The user privately generates an index $\theta \in \left[K\right]=\{1,\dots ,K\}$, and wishes to retrieve file $W_{\theta }$ such that it is impossible for either the data center or any individual database to identify $\theta$. For random variables $\theta$, and $W_1,\dots ,W_K$, we have

$$\begin{array}{c}\hfill H\left(\theta ,W_1,\dots ,W_K\right)=H\left(\theta \right)+H\left(W_1\right)+\cdots +H\left(W_K\right).\end{array}$$

(4)

In order to retrieve file $W_{\theta }$, the user sends $N+1$ queries $Q_0^{\left[\theta \right]},\dots ,Q_N^{\left[\theta \right]}$ to DB${}_0$, …, DB${}_N$, where $Q_n^{\left[\theta \right]}$ is the query sent to DB${}_n$ for file $W_{\theta }$. Note that the queries are independent of the realization of the K files. Therefore,

$$\begin{array}{c}\hfill I(W_1,\dots ,W_K;Q_0^{\left[\theta \right]},\dots ,Q_N^{\left[\theta \right]})=0.\end{array}$$

(5)

Upon receiving the query $Q_n^{\left[\theta \right]}$, DB${}_n$ replies with an answering string $A_n^{\left[\theta \right]}$, which is a function of $Q_n^{\left[\theta \right]}$ and $Z_n$. Therefore, $\forall \theta \in \left[K\right],\forall n\in \left\{0\right\}\cup \left[N\right]$,

$$\begin{array}{c}\hfill H(A_n^{\left[\theta \right]}|Q_n^{\left[\theta \right]},Z_n)=0.\end{array}$$

(6)

After receiving the answering strings $A_0^{\left[\theta \right]},\dots ,A_N^{\left[\theta \right]}$ from DB${}_0$, …, DB${}_N$, the user needs to decode the desired file $W_{\theta }$ reliably. By using Fano’s inequality, we have the following reliability constraint

$$\begin{array}{c}\hfill H\left(W_{\theta }|Q_0^{\left[\theta \right]},\dots ,Q_N^{\left[\theta \right]},A_0^{\left[\theta \right]},\dots ,A_N^{\left[\theta \right]}\right)=o\left(L\right),\end{array}$$

(7)

where $o\left(L\right)$ denotes a function such that $\frac{o\left(L\right)}{L}\to 0$ as $L\to \infty$.

To ensure that individual databases do not know which file is retrieved, we have the following privacy constraint, $\forall n\in \left\{0\right\}\cup \left[N\right]$, $\forall \theta \in \left[K\right]$,

$$\begin{array}{c}\hfill (Q_n^{\left[1\right]},A_n^{\left[1\right]},W_1,\dots ,W_K)\sim (Q_n^{\left[\theta \right]},A_n^{\left[\theta \right]},W_1,\dots ,W_K),\end{array}$$

(8)

where $A\sim B$ means that A and B are identically distributed.

Given that each file is of size L bits, for a fixed K, $\mu$ and decentralized caching probability distribution $P_H$, let $\mathcal{H}$ denote the indices of the cached bits in the N databases available in the retrieval phase. The probability distribution of $\mathcal{H}$ is specified in (3). Let $D_{\mathcal{H}}^{\left[\theta \right]}$ represent the number of downloaded bits via the answering strings $A_{0:N}^{\left[\theta \right]}$, where $A_{0:N}^{\left[\theta \right]}=(A_0^{\left[\theta \right]},\dots ,A_N^{\left[\theta \right]})$. Then,

$$\begin{array}{c}\hfill D_{\mathcal{H}}^{\left[\theta \right]}=\sum _{n=0}^{N}H\left(A_n^{\left[\theta \right]}\right).\end{array}$$

(9)

We further denote $D_{\mathcal{H}}$ as the expected number of downloaded bits with respect to different file requests, i.e., $D_{\mathcal{H}}=E_{\theta }\left[D_{\mathcal{H}}^{\left[\theta \right]}\right]$. Finally, we denote D as the expected number of downloaded bits with respect to different realization of the cached bit indices, i.e., $D=E_{\mathcal{H}}\left[D_{\mathcal{H}}\right]$. A pair $\left(D,L\right)$ is achievable if there exists a PIR scheme satisfying the reliability constraint (7) and the privacy constraint (8). The optimal normalized download cost $D^{*}$ is defined ass

$$\begin{array}{c}\hfill D^{*}=inf\left\{\frac{D}{L}:\left(D,L\right)\mathrm{is}\mathrm{achievable}\right\},\end{array}$$

(10)

as $L\to \infty$. In this work, we aim at characterizing the optimal normalized download cost and finding the optimal decentralized caching probability distribution.

Next, we illustrate the system model and the problem considered with a simple example of $K=3$ files and $N=2$ databases in the retrieval phase; see Figure 4. Consider a data center storing $K=3$ files where each file is of size 4 bits. In the caching phase, there are 4 databases in the system, and each database can at most store 4 bits. Each database can always store the first file, which is of size 4 bits, as caching option 1 in Figure 4. Or, each database can uniformly and randomly choose 4 bits out of a total of 12 bits from the data center to store. One of the realization is shown as caching option 2 in Figure 4. Each database can also choose two bits from the first file and one bit each from the remaining two files to store, where one of the realization is shown as caching option 3 in Figure 4. We require each database to use the same probability distribution to choose the bits to store in order to satisfy the decentralized requirement. In this example, we assume that the user can access the data center and $N=2$ databases in the retrieval phase, say the first and the third database, and the user wishes to download a file privately. Our questions are as follows: What is the optimal probability distribution to use in the caching phase? What is the optimal PIR scheme to use in the retrieval phase? How can we jointly design the schemes in the two phases such that the expected normalized download cost is the lowest in the second phase?

3. Main Results and Discussion

We characterize the optimal normalized download cost for PIR from decentralized uncoded caching databases in the following theorem.

Theorem 1.

For PIR from decentralized uncoded caching databases with K files, where each file is of size L bits, N databases in addition to a data center available in the retrieval phase, and a storage size constraint $\mu KL$, $0<\mu <1$, bits for each database, the optimal normalized download cost is

$$\begin{array}{c}\hfill D^{*}=\sum _{n=1}^{N+1}\left(\genfrac{}{}{0pt}{}{N}{n-1}\right){\mu }^{n-1}{(1-\mu )}^{N+1-n}\left(1+\frac{1}{n}+\cdots +\frac{1}{n^{K-1}}\right).\end{array}$$

(11)

The achievability scheme is provided in Section 4, and the converse proof is shown in Section 5. We first use the following example to show the main ingredients of Theorem 1.

3.1. Motivating Example: $K=3$ and $N=2$

In this example, we consider the case where the data center stores $K=3$ independent files labeled as A, B, and C, where each file is of size L bits. In the caching phase, several databases with storage capacity of $3\mu L$ bits are present in the system. We will show that the optimal normalized download cost is $\frac{D}{L}=\frac{17}{18}{\mu }^2-\frac{5}{2}\mu +3$ when $N=2$ databases in addition to the data center are available in the retrieval phase.

3.1.1. Achievability Scheme

In the caching phase, to satisfy the storage size constraint, each database randomly and uniformly stores $3\mu L$ bits out of a total of $3L$ bits from the data center. Each database operates independently through the same probability distribution resulting in decentralized caching.

In the retrieval phase, suppose $N=2$ databases, labeled as DB${}_1$ and DB${}_2$, in addition to the data center, labeled as DB${}_0$, are available to the user, and the user wishes to retrieve file A privately. Let us first focus on one file, say A. We can partition file A into four subfiles

$$\begin{array}{c}\hfill A=(A_0,A_{0,1},A_{0,2},A_{0,1,2}),\end{array}$$

(12)

where, for $S\subseteq \{0,1,2\}$, $A_S$ denotes the bits of file A which are stored in databases in S. For example, $A_0$ denotes the bits of file A only stored in DB${}_0$ and $A_{0,2}$ denotes the bits of file A stored in DB${}_0$ and DB${}_2$ and so on. Since each bit is stored in the data center, 0 exists in the label of every partition. By the law of large numbers,

$$\begin{array}{c}\hfill |A_S| = L{\mu }^{|S|-1}{(1-\mu )}^{3-|S|}+o\left(L\right),\end{array}$$

(13)

when the file size is large enough. We can do the same partitions for files B and C.

To retrieve file A privately, we first retrieve the subfile $A_{0,1,2}$ privately. We apply the PIR scheme proposed in [12] to retrieve the subfile $A_{0,1,2}$. Subfile $A_{0,1,2}$ is replicated in 3 databases and the total number of files is three since we also have $B_{0,1,2}$ and $C_{0,1,2}$. Therefore, we download

$$\begin{array}{c}\hfill L{\mu }^2\left(1+\frac{1}{3}+\frac{1}{9}\right)+o\left(L\right)\end{array}$$

(14)

bits. We also need to retrieve the subfile $A_{0,1}$ privately. Subfile $A_{0,1}$ is replicated in 2 databases and the total number of files is 3 since we also have $B_{0,1}$ and $C_{0,1}$. By applying the PIR scheme in [12], we download

$$\begin{array}{c}\hfill L\mu (1-\mu )\left(1+\frac{1}{2}+\frac{1}{4}\right)+o\left(L\right)\end{array}$$

(15)

bits. Next, we need to retrieve the subfile $A_{0,2}$ privately. Using [12], we download

$$\begin{array}{c}\hfill L\mu (1-\mu )\left(1+\frac{1}{2}+\frac{1}{4}\right)+o\left(L\right)\end{array}$$

(16)

bits. Finally, we need to retrieve $A_0$ privately. Using [12], we download

$$\begin{array}{c}\hfill L{(1-\mu )}^2(1+1+1)+o\left(L\right)\end{array}$$

(17)

bits. By adding (14)–(17), we show that the normalized download cost

$$\begin{array}{c}\hfill \frac{17}{18}{\mu }^2-\frac{5}{2}\mu +3\end{array}$$

(18)

is achievable.

3.1.2. Converse Proof

Here, we show that among all the decentralized caching probability distributions $P_H$, the lowest normalized download cost for $N=2$ databases is as shown in (18). Given a decentralized caching probability distribution $P_H$, we have a resulting $\mathcal{H}$ in the retrieval phase.

We lower bound $D_{\mathcal{H}}$ first. In the retrieval phase, the stored content of DB${}_0$, DB${}_1$, and DB${}_2$ are fixed and uncoded, i.e., $Z_0$, $Z_1$ and $Z_2$ are fixed and uncoded. We can apply the lower bound in Equation (31) in [44] as the lower bound for $D_{\mathcal{H}}$. Therefore,

$$\begin{array}{c}{D}_{\mathcal{H}}\ge L+\frac{4}{27}\sum _{k=1}^{3}H\left(W_k\right)+\frac{11}{108}\sum _{i=0}^2\sum _{k=1}^{3}H(W_k|Z_i)+\frac{17}{54}\sum _{i=0}^2\sum _{k=1}^{3}H(W_k|Z_{[0:2]\backslash i})+o\left(L\right)\end{array}$$

(19)

$$\begin{array}{c}=\frac{13}{9}L+\frac{11}{108}\sum _{i=1}^2\sum _{k=1}^{3}H(W_k|Z_i)+\frac{17}{54}\sum _{k=1}^{3}H(W_k|Z_1,Z_2)+o\left(L\right)\end{array}$$

(20)

$$\begin{array}{c}\ge \frac{13}{9}L+\frac{11}{108}\left(3L-3\mu L+3L-3\mu L\right)+\frac{17}{54}\sum _{k=1}^{3}H(W_k|Z_1,Z_2)+o\left(L\right)\end{array}$$

(21)

$$\begin{array}{c}=\frac{37}{18}L-\frac{11}{18}\mu L+\frac{17}{54}H(W_{1:3}|Z_1,Z_2)+o\left(L\right),\end{array}$$

(22)

where (20) holds due to $Z_0=(W_1,W_2,W_3)$, and (21) holds due to (2). We note that different $\mathcal{H}$ results in different $Z_1$ and $Z_2$.

We lower bound D now. From (22), we have

$$\begin{array}{c}\hfill D=E_{\mathcal{H}}\left[D_{\mathcal{H}}\right]\ge \frac{37}{18}L-\frac{11}{18}\mu L+\frac{17}{54}{E}_{\mathcal{H}}\left[H(W_{1:3}|Z_1,Z_2)\right]+o\left(L\right).\end{array}$$

(23)

Let random variables $X_{i,j}^{\left(n\right)}$, $i=1,\dots ,L$, $j=1,\dots ,K$, be the indicator functions showing that the i-th bit of file $W_j$ is cached in DB${}_n$ or not, i.e., $X_{i,j}^{\left(n\right)}=1$ means that the i-th bit of file $W_j$ is stored in DB${}_n$ and $X_{i,j}^{\left(n\right)}=0$ means that it is not stored in DB${}_n$. For DB${}_1$ we have

$$\begin{array}{c}\hfill X_{1,1}^{\left(1\right)}+\cdots +X_{L,1}^{\left(1\right)}+X_{1,2}^{\left(1\right)}+\cdots +X_{L,2}^{\left(1\right)}+X_{1,3}^{\left(1\right)}+\cdots +X_{L,3}^{\left(1\right)}\le 3\mu L,\end{array}$$

(24)

due to the storage size constraint in (2). We note that $P_H$ induces probability measures on random variables $X_{i,j}^{\left(n\right)}$, and let $X_{i,j}^{\left(n\right)}=1$ with probability $p_{i,j}$, where we remove the superscript n since each database adopts the same probability distribution $P_H$ to choose the cached bits due to the decentralized property. By taking expectation on (24) and applying the linearity of expectation, we have

$$\begin{array}{c}\hfill E[X_{1,1}^{\left(1\right)}]+\cdots +E[X_{L,3}^{\left(1\right)}]\le 3\mu L,\end{array}$$

(25)

which yields

$$\begin{array}{c}\hfill p_{1,1}+\cdots +p_{L,3}\le 3\mu L.\end{array}$$

(26)

Let random variables $V_{i,j}$, $i=1,\dots ,L$, $j=1,\dots ,K$, be the indicator functions showing that the i-th bit of file $W_j$ is not cached in DB${}_1$ and DB${}_2$, i.e., $V_{i,j}=1$ means that the i-th bit of file $W_j$ is not stored in either DB${}_1$ or DB${}_2$. Therefore, we have

$$\begin{array}{c}\hfill V_{i,j}=(1-X_{i,j}^{\left(1\right)})(1-X_{i,j}^{\left(2\right)}).\end{array}$$

(27)

Now, we can evaluate $E_{\mathcal{H}}\left[H(W_{1:3}|Z_1,Z_2)\right]$ in (23) as follows

$$\begin{array}{cc}\hfill E_{\mathcal{H}}\left[H(W_{1:3}|Z_1,Z_2)\right]& =E[V_{1,1}+\cdots +V_{L,3}]\hfill \end{array}$$

(28)

$$\begin{array}{c}=E\left[V_{1,1}\right]+\cdots +E\left[V_{L,3}\right]\end{array}$$

(29)

$$\begin{array}{c}={(1-p_{1,1})}^2+\cdots +{(1-p_{L,3})}^2.\end{array}$$

(30)

Therefore, continuing from (23), we have

$$\begin{array}{c}\hfill D\ge \frac{37}{18}L-\frac{11}{18}\mu L+\frac{17}{54}\left[{(1-p_{1,1})}^2+\cdots +{(1-p_{L,3})}^2\right]+o\left(L\right),\end{array}$$

(31)

where $p_{1,1}$, …, $p_{L,3}$ are subject to (26). To further lower bound the right hand side of (31), we minimize the right hand side with respect to $p_{i,j}$ subject to (26). Hence, we consider the following Lagrangian

$$\begin{array}{c}\hfill L(p_{1,1},\dots ,p_{L,3},\lambda )={(1-p_{1,1})}^2+\cdots +{(1-p_{L,3})}^2+\lambda \left(p_{1,1}+\cdots +p_{L,3}-3\mu L\right).\end{array}$$

(32)

From the KKT conditions, we have

$$\begin{array}{c}\hfill \lambda =2(1-p_{i,j}),i=1,\dots ,L,j=1,2,3.\end{array}$$

(33)

Thus, we can further lower bound (31) by letting $p_{1,1}=\cdots =p_{L,3}=\mu$, and we have

$$\begin{array}{c}\frac{D}{L}\ge \frac{37}{18}-\frac{11}{18}\mu +\frac{17}{54}\left[3{(1-\mu )}^2\right]+\frac{o\left(L\right)}{L}\end{array}$$

(34)

$$\begin{array}{c}=\frac{17}{18}{\mu }^2-\frac{5}{2}\mu +3+\frac{o\left(L\right)}{L}.\end{array}$$

(35)

Therefore, we show that the optimal normalized download cost is $\frac{17}{18}{\mu }^2-\frac{5}{2}\mu +3$ when $N=2$ databases in addition to the data center are available in the retrieval phase. To achieve the optimal normalized download cost, each database should randomly and uniformly store the bits in the caching phase.

3.2. Further Examples and Numerical Results

Now, we use different scenarios to illustrate the optimal normalized download cost in (11). We first consider the scenario where the data center contains $K=10$ files, each database with storage size constraint $\mu =\frac{1}{2}$, and in the retrieval phase, the user can access $N=0,\dots ,30$ databases in addition to the data center. We plot the expected normalized download cost versus the different number of available databases in Figure 5. When $N=0$, in order to download the desired file privately, the user should download all the files in the data center, and this results in a download cost of $\frac{D}{L}=K=10$. As the number of accessible databases increases, the normalized download cost decreases. We next consider the scenario where the data center contains $K=10$ files, and the user can access $N=5$ databases in addition to the data center in the retrieval phase. We plot the expected normalized download cost versus different storage size constraint $\mu$ in Figure 6. When $\mu =0$, in order to download the desired file privately, the user should download all the files in the data center resulting in $\frac{D}{L}=K=10$. As $\mu$ increases, the normalized download cost decreases. Finally, we conclude this section with the following general remarks about our main result.

3.3. Remarks

Remark 1.

The achievability scheme consists of two parts, the design of the probability distribution in the caching phase and the PIR scheme in the retrieval phase. We find that the uniform and random caching scheme, originally proposed in [57] for decentralized coded caching, results in the optimal normalized download cost in the retrieval phase. We remark here that the symmetric batch caching scheme, originally proposed in [55] for centralized coded caching, also results in the optimal normalized download cost for PIR from centralized uncoded caching databases [44]. In the retrieval phase, according to the distribution of the subfiles, we apply the PIR scheme proposed in [12] for all subfiles to retrieve the desired file.

Remark 2.

For the converse, we first apply the lower bound derived in [44] which introduces new ingredients in addition to the interference lower bound lemma and induction lemma in Lemmas 5 and 6 in [12]. We note that in [44] the authors replace random variables for queries and answering strings by the contents of the distributed databases in a novel way which is crucial for the converse. With this replacement, we can account for different cached content in the caching phase resulting in different lower bound in the normalized download cost in the retrieval phase. Due to the nature of uncoded caching, this replacement facilitates further lower bound. For the decentralized problem here, to compare different probability distributions in the caching phase, we focus on the marginal distributions on each bit. This transformation allows us to use linearity of expectation, and the nature of decentralization and uncoded caching to further lower bound the expected normalized download cost.

Remark 3.

A more directly related PIR problem from centralized uncoded caching databases for our setting is the one where, in the caching phase, the data center arranges the files in N databases in a centralized manner, and in the retrieval phase, the user has access also to the data center in addition to the N databases. This is different from the problem setting in [38,44], since there the user can only access the N databases in the retrieval phase. As a side note, we can show that the symmetric batch caching scheme is still optimal for this extended problem setting where the data center also participates in the PIR stage. Rigorously, the optimal trade-off between storage and download cost, in this case, is given by the lower convex envelope of the following $(\mu ,D(\mu \left)\right)$ pairs, for $t=0,1,\dots ,N$,

$$\begin{array}{c}\hfill \left(\mu =\frac{t}{N},D\left(\mu \right)=\sum _{k=0}^{K-1}\frac{1}{{(t+1)}^k}\right).\end{array}$$

(36)

To achieve this trade-off, the data center arranges the files into the N databases as in [38,44]. In the retrieval phase, the user accesses also the data center; therefore, the subfiles are stored in one more database. For the converse, we no longer require all the N databases to reconstruct the entire K files as in [38,44]. Thus, while in [38,44] the smallest allowable μ is $\mu =\frac{1}{N}$, since the N databases need to reconstruct the entire K files, here since the user can access the data center, the parameter μ starts from 0. Now, we can compare PIR from centralized caching databases and PIR from decentralized caching databases fairly, since, in the retrieval phase, the user can access the data center in both cases. We consider the case where $K=10$ and $N=5$, and plot the result in Figure 7.

4. Achievability Scheme

The achievability scheme consists of two parts: the design of the probability distribution used in the caching phase and the PIR scheme used in the retrieval phase. In the caching phase, each database uniformly and randomly stores $\mu KL$ bits from the data center. The storage size constraint in (2) is satisfied directly. Each database operates independently through the same probability distribution resulting in decentralized caching.

In the retrieval phase, suppose there are N databases in addition to the data center available to the user. Each file $W_j$ can be expressed as

$$\begin{array}{c}\hfill W_j=\bigcup _{\left\{0\right\}\subseteq S\subseteq \{0,1,\dots ,N\}}{W}_{j,S},\end{array}$$

(37)

where $W_{j,S}$ represents the bits of file $W_j$ which are stored in databases in S. Since each bit must be stored in the data center, i.e., DB${}_0$, we have $\left\{0\right\}\subseteq S$. By the law of large numbers,

$$\begin{array}{c}\hfill |W_{j,S}| = L{\mu }^{|S|-1}{(1-\mu )}^{N+1-|S|}+o\left(L\right),\end{array}$$

(38)

when the file size is large enough.

To retrieve the desired file, say $W_j$, privately, we retrieve each subfile, $W_{j,S}$, privately. Subfile $W_{j,S}$ is replicated in $|S|$ databases, and for each of these $|S|$ databases, there are K subfiles, i.e., $W_{k,S}$, $k=1,\dots ,K$. We apply the PIR scheme in [12] to retrieve $W_{j,S}$ privately by downloading

$$\begin{array}{c}\hfill L{\mu }^{|S|-1}{(1-\mu )}^{N+1-|S|}\left(1+\frac{1}{|S|}+\cdots +\frac{1}{{|S|}^{K-1}}\right)+o\left(L\right)\end{array}$$

(39)

bits. We also note that there are $\left(\genfrac{}{}{0pt}{}{N}{|S|-1}\right)$ types of $W_{j,S}$. Therefore, the following normalized download cost

$$\begin{array}{c}\hfill \frac{D}{L}=\sum _{n=1}^{N+1}\left(\genfrac{}{}{0pt}{}{N}{n-1}\right){\mu }^{n-1}{(1-\mu )}^{N+1-n}\left(1+\frac{1}{n}+\cdots +\frac{1}{n^{K-1}}\right)\end{array}$$

(40)

is achievable.

5. Converse Proof

We first derive a lower bound for $D_{\mathcal{H}}$. Since in the retrieval phase the content of DB${}_0$, …, DB${}_N$, are fixed to be $Z_0$, …, $Z_N$, we can use the lower bound derived in Equation (71) in [44] to serve as the lower bound for $D_{\mathcal{H}}$. A key step to obtain Equation (71) in [44] is to replace the query and answering string random variables with the content of each database, i.e., replacement of $Q_{\mathcal{N}}^{\left[k\right]}$ and $A_{\mathcal{N}}^{\left[k\right]}$ with $Z_{\mathcal{N}}$. With this replacement, one can account for different cached content in the caching phase resulting in different lower bound in the normalized download cost in the retrieval phase. In addition, due to the nature of uncoded caching, this replacement facilitates a further lower bound. Moreover, to obtain Equation (71) in [44], the authors find interesting recursive relationships to compactly deal with the nested harmonic sums. Therefore, from Equation (71) in [44] we have

$$\begin{array}{c}\hfill D_{\mathcal{H}}\ge L+\sum _{l=1}^{N+1}\left(\genfrac{}{}{0pt}{}{N+1}{l}\right)\left(\frac{1}{l}+\frac{1}{l^2}+\cdots +\frac{1}{l^{K-1}}\right)x_l,\end{array}$$

(41)

where

$$\begin{array}{c}\hfill x_l\delta \frac{1}{K\left(\genfrac{}{}{0pt}{}{N+1}{l}\right)}\sum _{\left\{0\right\}\subseteq S\subseteq [0:N],|S|=l}H\left(W_{1:K,S}\right),l\in [1:N+1],\end{array}$$

(42)

and $W_{1:K,S}$ represents the bits of files $W_{1:K}$ which are stored in databases in S.

In the following lemma, we develop a lower bound for $E\left[x_l\right]$.

Lemma 1.

For $l\in [1:N+1]$, and $x_l$ given in (42), we have

$$\begin{array}{c}\hfill E\left[x_l\right]\ge L{\mu }^{l-1}{(1-\mu )}^{N+1-l}\frac{\left(\genfrac{}{}{0pt}{}{N}{l-1}\right)}{\left(\genfrac{}{}{0pt}{}{N+1}{l}\right)}.\end{array}$$

(43)

Proof 1.

By taking expectation on (42) and using the linearity of expectation, we have

$$\begin{array}{c}\hfill E\left[x_l\right]=\frac{1}{K\left(\genfrac{}{}{0pt}{}{N+1}{l}\right)}\sum _{\left\{0\right\}\subseteq S\subseteq [0:N],|S|=l}E\left[H\left(W_{1:K,S}\right)\right].\end{array}$$

(44)

Let random variables $X_{i,j}^{\left(n\right)}$, $i=1,\dots ,L$, $j=1,\dots ,K$, be the indicator functions showing that the i-th bit of file $W_j$ is cached in DB${}_n$, $n=0,\dots ,N$, or not, i.e., $X_{i,j}^{\left(n\right)}=1$ means that the i-th bit of file $W_j$ is stored in DB${}_n$ and $X_{i,j}^{\left(n\right)}=0$ means that it is not stored in DB${}_n$. For DB${}_n$ we have

$$\begin{array}{c}\hfill X_{1,1}^{\left(n\right)}+\cdots +X_{L,1}^{\left(n\right)}+\cdots +X_{1,K}^{\left(n\right)}+\cdots +X_{L,K}^{\left(n\right)}\le \mu KL,\end{array}$$

(45)

due to the storage size constraint in (2). We note that $P_H$ induces probability measures on random variables $X_{i,j}^{\left(n\right)}$, and let $X_{i,j}^{\left(n\right)}=1$ with probability $p_{i,j}$, where we remove the superscript n since each database adopts the same probability distribution $P_H$ to choose the cached bits due to the decentralized caching property. By taking expectation on (45) and applying the linearity of expectation, we have

$$\begin{array}{cc}\hfill E[X_{1,1}^{\left(n\right)}]+\cdots +E[X_{L,K}^{\left(n\right)}]& \le \mu KL,\hfill \end{array}$$

(46)

which yields

$$\begin{array}{cc}\hfill p_{1,1}+\cdots +p_{L,K}& \le \mu KL..\hfill \end{array}$$

(47)

Let random variables $Y_{i,j}^S$, $i=1,\dots ,L$, $j=1,\dots ,K$, be the indicator functions showing that the i-th bit of file $W_j$ is cached in DB${}_n$, $n\in S$, i.e., $Y_{i,j}=1$ means that the i-th bit of the file $W_j$ is stored in DB${}_n$, $n\in S$. Therefore, we have

$$\begin{array}{c}\hfill Y_{i,j}^S=\prod _{n\in S}{X}_{i,j}^{\left(n\right)}\prod _{n\in [0:N]\backslash S}(1-X_{i,j}^{\left(n\right)}).\end{array}$$

(48)

Now, we can evaluate $E\left[H\left(W_{1:K,S}\right)\right]$ in (44) as follows

$$\begin{array}{c}E\left[H\left(W_{1:K,S}\right)\right]=E[Y_{1,1}^S+\cdots +Y_{L,K}^S]\end{array}$$

(49)

$$\begin{array}{c}=E[Y_{1,1}^S]+\cdots +E[Y_{L,K}^S]\end{array}$$

(50)

$$\begin{array}{c}=p_{1,1}^{|S|-1}{(1-p_{1,1})}^{N+1-|S|}+\cdots +p_{L,K}^{|S|-1}{(1-p_{L,K})}^{N+1-|S|},\end{array}$$

(51)

where $p_{1,1}$, …, $p_{L,K}$ are subject to (47). Now, continuing from (44), we have

$$\begin{array}{cc}\hfill E\left[x_l\right]& =\frac{1}{K\left(\genfrac{}{}{0pt}{}{N+1}{l}\right)}\sum _{\left\{0\right\}\subseteq S\subseteq [0:N],|S|=l}{p}_{1,1}^{l-1}{(1-p_{1,1})}^{N+1-l}+\cdots +p_{L,K}^{l-1}{(1-p_{L,K})}^{N+1-l}.\hfill \end{array}$$

(52)

To further lower bound (52), we consider the following Lagrangian

$$\begin{array}{cc}L(p_{1,1},\dots ,p_{L,K},\lambda )\hfill & =p_{1,1}^{l-1}{(1-p_{1,1})}^{N+1-l}+\cdots +p_{L,K}^{l-1}{(1-p_{L,K})}^{N+1-l}\hfill \\ \hfill & +\lambda \left(p_{1,1}+\cdots +p_{L,K}-\mu KL\right).\hfill \end{array}$$

(53)

From the KKT conditions, we have

$$\begin{array}{c}\hfill \lambda =p_{i,j}^{l-1}(N+1-l){(1-p_{i,j})}^{N-l}-(l-1)p_{i,j}^{l-2}{(1-p_{i,j})}^{N+1-l},\end{array}$$

(54)

where $i=1,\dots ,L$, $j=1,\dots ,K$. Therefore, we can further lower bound (52) by letting $p_{1,1}=\cdots =p_{L,K}=\mu$, then we have

$$\begin{array}{c}E[x_l]\ge \frac{1}{K\left(\genfrac{}{}{0pt}{}{N+1}{l}\right)}\sum _{\left\{0\right\}\subseteq S\subseteq [0:N],|S|=l}KL{\mu }^{l-1}{(1-\mu )}^{N+1-l}\end{array}$$

(55)

$$\begin{array}{c}=L{\mu }^{l-1}{(1-\mu )}^{N+1-l}\frac{\left(\genfrac{}{}{0pt}{}{N}{l-1}\right)}{\left(\genfrac{}{}{0pt}{}{N+1}{l}\right)},\end{array}$$

(56)

which completes the proof. □

Finally, by taking expectation and applying Lemma 1 to (41), we obtain

$$\begin{array}{c}\frac{D}{L}\ge 1+\sum _{l=1}^{N+1}\left(\genfrac{}{}{0pt}{}{N}{l-1}\right)\left(\frac{1}{l}+\frac{1}{l^2}+\cdots +\frac{1}{l^{K-1}}\right){\mu }^{l-1}{(1-\mu )}^{N+1-l}\end{array}$$

(57)

$$\begin{array}{c}={\left(\mu +(1-\mu )\right)}^N+\sum _{l=1}^{N+1}\left(\genfrac{}{}{0pt}{}{N}{l-1}\right)\left(\frac{1}{l}+\frac{1}{l^2}+\cdots +\frac{1}{l^{K-1}}\right){\mu }^{l-1}{(1-\mu )}^{N+1-l}\end{array}$$

(58)

$$\begin{array}{c}=\sum _{l=1}^{N+1}\left(\genfrac{}{}{0pt}{}{N}{l-1}\right)\left(1+\frac{1}{l}+\frac{1}{l^2}+\cdots +\frac{1}{l^{K-1}}\right){\mu }^{l-1}{(1-\mu )}^{N+1-l}\end{array}$$

(59)

which matches (40).

6. Conclusions

We considered the PIR problem from decentralized uncoded caching databases. Due to the nature of decentralization and the storage size constraint, we allow the user to access the data center in the retrieval phase to guarantee that the user can reconstruct the entire desired file. We showed that uniform and random decentralized caching scheme, originally proposed in [57] for the problem of decentralized coded caching, results in the lowest expected normalized download cost in the PIR phase. We characterized the expected normalized download cost to be $\frac{D}{L}={\sum }_{n=1}^{N+1}\left(\genfrac{}{}{0pt}{}{N}{n-1}\right){\mu }^{n-1}{(1-\mu )}^{N+1-n}\left(1+\frac{1}{n}+\cdots +\frac{1}{n^{K-1}}\right)$. For the achievability, we applied the PIR scheme in [12] for all subfiles. For the converse, we first applied the lower bound derived in [44], and to compare different probability distributions in the caching phase, we focused on the marginal distributions on individual bits. By using the nature of decentralization and uncoded caching, we further lower bounded the normalized download cost. Finally, we showed the matching converse for the expected normalized download cost, obtaining the exact capacity of the resulting PIR problem.