In this paper, we study the special case t=1, under the assumption that every server stores a subset of the items. This is purely a combinatorial problem, so we call this kind of batch code a "combinatorial batch code''. For various parameter situations, we are able to present batch codes that are optimal with respect to the storage requirement, N. We also study uniform codes, where every item is stored in precisely c of the m servers (such a code is said to have rate 1/c). Interesting new results are presented in the cases c = 2, k-2 and k-1. In addition, we obtain improved existence results for arbitrary fixed c using the probabilistic method.
Category / Keywords: foundations / Publication Info: submitted for publication Date: received 7 Jul 2008 Contact author: dstinson at uwaterloo ca Available formats: PDF | BibTeX Citation Version: 20080708:165634 (All versions of this report) Discussion forum: Show discussion | Start new discussion