# Batch code[1]

## Description

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.

## Parents

- Binary code
- Locally recoverable code (LRC) — A systematic batch code with restricted size of reconstruction sets can recover any query of \(t\) information symbols with recovery sets of size \(r\) [2][3].

## References

- [1]
- Y. Ishai et al., “Batch codes and their applications”, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC ’04 (2004) DOI
- [2]
- V. Skachek, “Batch and PIR Codes and Their Connections to Locally Repairable Codes”, Network Coding and Subspace Designs 427 (2018) DOI
- [3]
- 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

- Victor V. Albert (2022-07-07) — most recent
- Yijia Xu (2022-04-25)

## Cite as:

“Batch code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/batch

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/batch.yml.