Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Coding Theory: Multiset Combinatorial Batch Codes
event speaker icon
Hui Zhang (CS, Technion)
event date icon
Sunday, 22.01.2017, 14:30
event location icon
Taub 601
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.