Batch Codes for Asynchronous Recovery of Data
Ago-Erik Riet, Vitaly Skachek, Eldho K. Thomas · IEEE Transactions on Information Theory · 2021
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 requests arrive at random times and they take varying time to process. We show that the graph-based batch codes studied by Rawatet al.are asynchronous. Further, we demonstrate that hypergraphs of Berge girth larger or equal to 4, respectively larger or equal to 3, yield graph-based asynchronous batch codes, respectively private information retrieval (PIR) codes. We prove a 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ős and Sós. We then apply the constructions and bounds by Erdős, Frankl and Rödl about this generalization of the (6,3)-problem, known as the ($3\varrho $-3,$\varrho $)-problem, to obtain batch code constructions and bounds on the redundancy of the graph-based asynchronous batch and PIR codes. We derive bounds on the optimal redundancy of several families of asynchronous batch codes with the query size$t=2$. In particular, we show that the optimal redundancy$\rho (k)$of graph-based asynchronous batch codes of dimension$k$for$t=2$is$2\sqrt {k}$. Moreover, for graph-based asynchronous batch codes with$t \ge 3$,$\rho (k) = O\left ({{k}^{1/(2-\epsilon)}}\right)$for any small$\epsilon >0$.