Combinatorial batch codes

M.  B.  Paterson; D.  R.  Stinson; R.  Wei

Paper 2008/306

Combinatorial batch codes

M. B. Paterson, D. R. Stinson, and R. Wei

Abstract

In this paper, we study batch codes, which were introduced by Ishai, Kushilevitz, Ostrovsky and Sahai. A batch code specifies a method to distribute a database of n items among m devices (servers) in such a way that any k items can be retrieved by reading at most t items from each of the servers. It is of interest to devise batch codes that minimize the total storage, denoted by N, over all m servers. 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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. submitted for publication
Contact author(s): dstinson @ uwaterloo ca
History: 2008-07-08: received
Short URL: https://ia.cr/2008/306
License: CC BY

BibTeX

@misc{cryptoeprint:2008/306,
      author = {M.  B.  Paterson and D.  R.  Stinson and R.  Wei},
      title = {Combinatorial batch codes},
      howpublished = {Cryptology ePrint Archive, Paper 2008/306},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/306}},
      url = {https://eprint.iacr.org/2008/306}
}