-
Abstract
In this paper, we study batch codes, which were
introduced by Ishai, Kushilevitz, Ostrovsky and Sahai in [4].
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.
We restrict out attention to batch codes
in which 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''.
We only study the special case $t=1$, where,
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.
Mathematics Subject Classification: Primary: 05B30, 05D05; Secondary: 68P20, 68R05.
\begin{equation} \\ \end{equation}
-
Access History
-