Batch code[1] 


Binary code designed for minimizing the total amount of storage and the worst-case maximal load on any devices in a distributed system.

An \((n,N,k,m,t)\) batch code encodes a length-\(n\) string \(x_1,\cdots,x_n\) into an \(m\)-tuple of strings of total length \(N\) (are also called buckets), such that for each \(k\)-tuple of distinct indices \(i_1,i_2,...,i_k\), the entries \(x_{i_1},...,x_{i_k}\) can be decoded by reading at most \(t\)-symbols from each bucket. If each bucket of a batch code contains a single symbol, then the \((n,N,k,m)\) batch code is primitive.

A multi-user generalization of batch code is named multiset batch code. If, for any multiset \(i_1, i_2, ..., i_k \in [n]\), there is a partition of buckets into subsets \(S_1, ..., S_k \subset [m]\) such that each \(x_{i_j}\) can be recovered by reading at most one symbol from each bucket in \(S_j\), then the \((n, N, k, m)\) code is a multiset batch code.

Combining two batch codes \(C_1\) and \(C_2\), which are \((n_1,N_1,k_1,m_1)\) and \((n_2,N_2,k_2,m_2)\) batch codes respectively, yields a composite batch code \(C_1\otimes C_2\), which is an \((n_1, m_1N_2, k_1 k_2, m_1 m_2)\) batch code.



Y. Ishai et al., “Batch codes and their applications”, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (2004) DOI
V. Skachek, “Batch and PIR Codes and Their Connections to Locally Repairable Codes”, Network Coding and Subspace Designs 427 (2018) DOI
A.-E. Riet, V. Skachek, and E. K. Thomas, “Batch Codes for Asynchronous Recovery of Data”, IEEE Transactions on Information Theory 68, 1545 (2022) DOI
Page edit log

Your contribution is welcome!

on (edit & pull request)— see instructions

edit on this site

Zoo Code ID: batch

Cite as:
“Batch code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022.
@incollection{eczoo_batch, title={Batch code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:

Cite as:

“Batch code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022.