Batch Codes for Asynchronous Recovery of Data
| Autor: | Vitaly Skachek, Ago-Erik Riet, Eldho K. Thomas |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Hypergraph Discrete Mathematics (cs.DM) Generalization Computer Science - Information Theory E.4 G.2 Dimension (graph theory) Library and Information Sciences Redundancy (information theory) FOS: Mathematics Mathematics - Combinatorics Mathematics Discrete mathematics Information Theory (cs.IT) 68P30 (primary) 05D99 05B40 (secondary) Process (computing) Girth (graph theory) Computer Science Applications Asynchronous communication Graph (abstract data type) Combinatorics (math.CO) Computer Science - Discrete Mathematics MathematicsofComputing_DISCRETEMATHEMATICS Information Systems |
| Zdroj: | IEEE Transactions on Information Theory. 68:1545-1559 |
| ISSN: | 1557-9654 0018-9448 |
| DOI: | 10.1109/tit.2021.3131620 |
| Popis: | We propose a new model of asynchronous batch codes that allow for parallel recovery of information symbols from a coded database in an asynchronous manner, i.e. when queries arrive at random times and they take varying time to process. We show that the graph-based batch codes studied by et al. are asynchronous. Further, we demonstrate that hypergraphs of Berge girth larger or equal to 4, respectively larger or equal to 3, yield graph-based asynchronous batch codes, respectively private information retrieval (PIR) codes. We prove the hypergraph-theoretic proposition that the maximum number of hyperedges in a hypergraph of a fixed Berge girth equals the quantity in a certain generalization of the hypergraph-theoretic (6,3)-problem, first posed by Brown, Erd\H{o}s and S\'{o}s. We then apply the constructions and bounds by Erd\H{o}s, Frankl and R\"{o}dl about this generalization of the (6,3)-problem, known as the (3$\varrho$-3,$\varrho$)-problem, to obtain batch code constructions and bounds on the redundancy of the graph-based asynchronous batch and PIR codes. We derive bounds on the optimal redundancy of several families of asynchronous batch codes with the query size $t=2$. In particular, we show that the optimal redundancy $\rho(k)$ of graph-based asynchronous batch codes of dimension $k$ for $t=2$ is $2\sqrt{k}$. Moreover, for graph-based asynchronous batch codes with $t \ge 3$, $\rho(k) = O\left({k}^{1/(2-\epsilon)}\right)$ for any small $\epsilon>0$. Comment: 18 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|