Combinatorial batch codes

In this paper, we study batch codes, which wereintroduced by Ishai, Kushilevitz, Ostrovsky and Sahai in [4].A batch code specifies a method to distribute adatabase of n items among m devices (servers)in such a way that any k itemscan be retrieved by reading at most t items from each of the servers. It is of interest to devise batch codes thatminimize the total storage, denoted by N, over all m servers.We restrict out attention to batch codesin which every server stores a subset ofthe items. This is purely a combinatorial problem, sowe call this kind of batch code a ''combinatorial batch code''.We only study the special case $t=1$, where,for various parameter situations, we are able to presentbatch codes that are optimal with respect to the storagerequirement, N. We also study uniform codes, where every item isstored in precisely c of the m servers (such a codeis said to have rate $1/c$). Interesting new resultsare presented in the cases $c = 2, k-2$ and $k-1$. In addition,we obtain improved existence results for arbitraryfixed c using the probabilistic method.