On erasure combinatorial batch codes

DOI10.3934/AMC.2018003MaRDI QIDQ1783704zbMATH OpenOpenAlexFDO

Authors G. Richomme

Publication date 21 September 2018

Published in Advances in Mathematics of Communications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.04580

zbMATH Keywords

dual codesblock designsbatch codesdual designserasure batch codes

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Other designs, configurations (05B30) Combinatorial codes (94B25)

Abstract: Combinatorial batch codes were defined by Paterson, Stinson, and Wei as purely combinatorial versions of the batch codes introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai. There are $n$ items and $m$ servers, each of which stores a subset of the items. A batch code is an arrangement for storing items on servers so that, for prescribed integers $k$ and $t$, any $k$ items can be retrieved by reading at most $t$ items from each server. Silberstein defined an erasure batch code (with redundancy $r$) as a batch code in which any $k$ items can be retrieved by reading at most $t$ items from each server, while any $r$ servers are unavailable (failed). In this paper, we investigate erasure batch codes with $t=1$ (each server can read at most one item) in a combinatorial manner. We determine the optimal (minimum) total storage of an erasure batch code for several ranges of parameters. Additionally, we relate optimal erasure batch codes to maximum packings. We also identify a necessary lower bound for the total storage of an erasure batch code, and we relate parameters for which this trivial lower bound is achieved to the existence of graphs with appropriate girth.

Recommendations

• Combinatorial batch codes
• Optimal batch codes: many items or low retrieval requirement
• Erasure combinatorial batch codes based on nonadaptive group testing
• Combinatorial batch codes and transversal matroids
• Combinatorial batch codes: a lower bound and optimal constructions

Cites work

• scientific article; zbMATH DE number 124521 (Why is no real title available?)
• Batch codes and their applications
• Combinatorial batch codes
• Combinatorial batch codes and transversal matroids
• Fractional repetition and erasure batch codes
• Graphs with maximum size and lower bounded girth
• Multiset combinatorial batch codes
• Optimal batch codes: many items or low retrieval requirement
• Optimal combinatorial batch codes derived from dual systems
• Relaxations of Hall's condition: optimal batch codes with multiple queries
• The CRC handbook of combinatorial designs

Cited in

(5)

• Turán numbers and batch codes
• Fractional repetition and erasure batch codes
• Constructions and bounds for batch codes with small parameters
• Erasure combinatorial batch codes based on nonadaptive group testing
• On Generic Erasure Correcting Sets and Related Problems

This page was built for publication: On erasure combinatorial batch codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1783704)