Asymmetry Hurts: Private Information Retrieval Under Asymmetric Traffic Constraints
We consider the classical setting of private information retrieval (PIR) of a single message (file) out of <inline formula> <tex math notation="LaTeX"$M$ /tex math>/inline formula> messages from <inline formula> <tex math notation="LaTeX"$N$ /tex math>/inline formula> distributed databases under the new constraint of <italic>asymmetric traffic</italic> from databases. In this problem, the <italic>ratios between the traffic</italic> from the databases are constrained, i.e. the ratio of the length of the answer string that the user (retriever) receives from the <inline formula> <tex math notation="LaTeX"$n$ /tex math>/inline formula>th database to the total length of all answer strings from all databases is constrained to be <inline formula> <tex math notation="LaTeX"\tau _{n} /tex math>/inline formula> This may happen if the user's access to the databases is restricted due to database availability, channel quality to the databases, and other factors. For this problem, for fixed <inline formula> <tex math notation="LaTeX"$M$ /tex math>/inline formula> <inline formula> <tex math notation="LaTeX"$N$ /tex math>/inline formula> we develop a general upper bound <inline formula> <tex math notation="LaTeX"\bar {C}\boldsymbol \tau /tex math>/inline formula> which generalizes the converse proof of Sun Jafar, where database symmetry was inherently used. Our converse bound is a piece wise affine function in the traffic ratio vector <inline formula> <tex math notation="LaTeX"\boldsymbol \tau \tau _{1} \cdots \tau _{N} /tex math>/inline formula> For the lower bound, we explicitly show the achievability of <inline formula> <tex math notation="LaTeX"\binom {M+N 1}{M} /tex math>/inline formula> corner points. For the remaining traffic ratio vectors, we perform time sharing between these corner points. The recursive structure of our achievability scheme is captured via a system of difference equations. The upper and lower bounds exactly match for <inline formula> <tex math notation="LaTeX"$M=2$ /tex math>/inline formula> and <inline formula> <tex math notation="LaTeX"$M=3$ /tex math>/inline formula> for any <inline formula> <tex math notation="LaTeX"$N$ /tex math>/inline formula> and any <inline formula> <tex math notation="LaTeX"\boldsymbol \tau /tex math>/inline formula> The results show strict loss of PIR capacity due to the asymmetric traffic constraints compared with the symmetric case of Sun Jafar which implicitly uses <inline formula> <tex math notation="LaTeX"\tau _{n}\frac {1}{N} /tex math>/inline formula> for all <inline formula> <tex math notation="LaTeX"$n$ /tex math>/inline formula>
IEEE Transactions on Information Theory