Consider a large distributed storage system that needs to store $k$ data items using $n$ servers. We study how to encode information so that a large number $t$ of read requests can be performed in parallel while the rate remains constant (and ideally approaches one). This problem is equivalent to the design of multiset Batch Codes introduced by Ishai, Kushilevitz, Ostrovsky and Sahai.

We give families of multiset batch codes with asymptotically optimal rates of the form $1-1/poly\left(t\right)$ and a number of servers $n$ scaling polynomially in the number of read requests $t$. An advantage of our batch code constructions over most previously known multiset batch codes is explicit and deterministic decoding algorithms and asymptotically optimal fault tolerance. Our constructions rely on dense bipartite graphs with no small cycles. We modify prior graph constructions of dense, high-girth graphs to obtain our batch code results. We achieve close to optimal tradeoffs between the parameters for bipartite graph based batch codes.

* This is joint work with Zhao Song, Alex Dimakis and Anna Gal. *