The Taub Faculty of Computer Science Events and Talks

An (n, N, k, m, t)-batch code abstracts the following distributed database problem: n items are to be distributed among m servers in such a way that any (multi)set of k items can be retrieved by reading at most t items from each server with the condition that the total storage over m servers be bounded by N. Combinatorial batch codes (CBCs) are replication based variants, i.e., for these codes each of the N stored items is a copy of one of the n input data items. An (n, N, k, m)-CBC is called c-uniform if each of the n input data items is stored in exactly c servers.

Two optimization problems have been discussed in the context of CBCs. 1. Given n, m, k, we denote by N(n, k, m) minimum value of N such that there is an (n, N, k, m, t = 1)-CBC. 2. Given m, c, k, we denote by n(m, c, k) maximum value of n such that there is a c-uniform (n, cn, k, m, t = 1)- CBC. The problems of finding N(n, k, m) and n(m, c, k) seems to be difficult in general. In my talk, I will discuss some bounds and constructions related to these two problems.