FR4.R8.3

Equal Requests are Asymptotically Hardest for Data Recovery

Jüri Lember, Ago-Erik Riet, University of Tartu, Estonia

Session:
Private Information Retrieval 3

Track:
16: Private Information Retrieval

Location:
Omega

Presentation Time:
Fri, 12 Jul, 17:05 - 17:25

Session Chair:
Ago-Erik Riet, University of Tartu, Estonia
Abstract
In a distributed storage system serving hot data, the data recovery performance becomes important, captured e.g. by the service rate. We give partial evidence for our intuition that it should be hardest to serve a sequence of equal user requests (as in the PIR coding regime) both for concrete and random user requests and server contents. Towards this, in the non-random case we prove a result that, if enough copies of each vector are stored in servers, then if a request sequence with all requests equal can be served then we can still serve it if a few requests are changed. This means that a constant request sequence is “locally hardest”, i.e. hardest in a Hamming ball centered at it. For random iid server contents, where the number of data symbols is constant (for simplicity) and the number of servers grows, we show that the maximum number of user requests we can serve divided by the number of servers we need approaches a limit almost surely. For uniform server contents, we show this limit is 1/2, both for sequences of copies of a fixed request and of any requests, confirming in this case that it is at least as hard to serve equal user requests as any requests. For iid requests independent from the uniform server contents the limit is at least 1/2 and equal to 1/2 if requests are all equal to a fixed request almost surely, again confirming the same. As an important building block of our proofs, we deduce from an old result of Marshall Hall, Jr. on abelian groups, that any collection of half as many requests as coded symbols in the doubled binary simplex code can be served by this code. An easy consequence is the fractional version of the Functional Batch Code Conjecture where half-servers are allowed.
Resources