Asynchronous Batch and PIR Codes from Hypergraphs
Ago-Erik Riet, Vitaly Skachek, Eldho K. Thomas · 2018
We propose a new model of asynchronous batch codes that allow for parallel recovery of information symbols from a coded database in an asynchronous manner, i.e. when different queries take different time to process. Then, we show that the graph-based batch codes studied by Rawat et al. are asynchronous. Further, we demonstrate that hypergraphs of Berge girth at least 4, respectively at least 3, yield graph-based asynchronous batch codes, respectively private information retrieval (PIR) codes. We prove the hypergraph-theoretic proposition that the maximum number of hyperedges in a hypergraph of a fixed Berge girth equals the quantity in a certain generalization of the hypergraph-theoretic (6,3)-problem, first posed by Brown, Erdos and Sós. We then apply the constructions and bounds by Erdos, Frankl and Rödl about this generalization of the (6,3)problem, known as the (3r-3,r)-problem, to obtain batch code constructions and bounds on the redundancy of the graph-based asynchronous batch and PIR codes. Finally, we show that the optimal redundancy ρ(k) of graph-based asynchronous batch codes of dimension k with the query size t = 3 is 2√k. Moreover, for a general fixed value of t ≥ 4, ρ(k) = O (k1/(2-ε)) for any small ε > 0. For a general value of t ≥ 4, limk→∞ρ(k)√k = ∞.