The Taub Faculty of Computer Science Events and Talks

Batch codes, first introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai, mimic a distributed storage of a set of n data items on m servers, in such a way that any batch of k data items can be retrieved by reading at most some t symbols from each server. Combinatorial batch codes,

are replication-based batch codes in which each server stores a subset of the data items.

In this talk, we propose a generalization of combinatorial batch codes, called multiset combinatorial batch codes (MCBC). The setup of this new family of codes is motivated by recent work on codes which enable high availability and parallel reads in distributed storage systems. The main problem under this paradigm is to minimize the number of items stored in the servers. We first give a necessary and sufficient condition for the existence of MCBCs. Then, we present several bounds and constructions.