Asynchronous Batch and PIR Codes from Hypergraphs

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 in Rawat et al., IEEE Trans. on Inform. Theory, Apr. 2016, 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, Erd\H os and S\'os. We then apply the constructions and bounds by Erd\H os, Frankl and R\"odl about this generalization of the (6,3)-problem, known as the (3$r$-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 $\rho(k)$ of graph-based asynchronous batch codes of dimension $k$ with the query size $t=3$ is $2\sqrt{k}$. Moreover, for a general fixed value of $t \ge 4$, $\rho(k) = O\left({k}^{1/(2-\epsilon)}\right)$ for any small $\epsilon>0$. For a general value of $t \ge 4$, $\lim_{k \rightarrow \infty} \rho(k)/\sqrt{k} = \infty$.