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 - STOC ’04 (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)

edit on this site

Zoo Code ID: batch

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

Cite as:

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