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$.

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 = ∞.

We address the question of constructing explicitly quasi-uniform codes from groups. We determine the size of the codebook, the alphabet and the minimum distance as a function of the corresponding group, both for abelian and some nonabelian groups. Potentials applications comprise the design of almost affine codes and non-linear network codes.