Private Information Retrieval from Decentralized Uncoded Caching Databases

• Main Authors: Wei, Yi-Peng, Arasli, Batuhan, Banawan, Karim, Ulukus, Sennur
• Format: Conference Proceeding
• Language: English
• Subjects: Data centers; Distributed databases; Information retrieval; Probability distribution; Random variables; Servers
• ISSN: 2157-8117
• DOI: 10.1109/ISIT.2019.8849784

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 μKL bits exist in the system. Each database independently chooses μ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 \frac{D}{L} = \sum\nolimits_{n = 1}^{N + 1} {\binom{N } {{n - 1} }{\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 result in the lowest normalized download cost. This is the decentralized counterpart of the recent result of Attia, Kumar and Tandon for the centralized case.