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

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

Zoo code information

Internal code ID: batch

Your contribution is welcome!

on github.com (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. https://errorcorrectionzoo.org/c/batch
BibTeX:
@incollection{eczoo_batch, title={Batch code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/batch} }
Share via:
Twitter |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/batch

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.