2019/01/21 by Xiangliang Kong, Kong, Xiangliang, Jingxue Ma +3 · 2 citations
Computer Science · Mathematics · #05C90 #68P30 #Advanced Data Storage Technologies #Caching and Content Delivery #Cryptography and Data Security #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT #msc:05C90 #msc:68P30
paper · pdf · doi:10.48550/arxiv.1901.06915
18 pages. arXiv admin note: text overlap with arXiv:1605.05412 by other authors
openalex publication_date 2019/01/21 · arxiv created 2019/02/19 · arxiv updated 2019/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In recent years, the rapidly increasing amounts of data created and processed through the internet resulted in distributed storage systems employing erasure coding based schemes. Aiming to balance the tradeoff between data recovery for correlated failures and efficient encoding and decoding, distributed storage systems employing maximally recoverable codes came up. Unifying a number of topologies considered both in theory and practice, Gopalan et al. \citeGopalan2017 initiated the study of maximally recoverable codes for grid-like topologies. In this paper, we focus on the maximally recoverable codes that instantiate grid-like topologies Tm× n(1,b,0). To characterize the property of codes for these topologies, we introduce the notion of pseudo-parity check matrix. Then, using the Combinatorial Nullstellensatz, we establish the first polynomial upper bound on the field size needed for achieving the maximal recoverability in topologies Tm× n(1,b,0). And using hypergraph independent set approach, we further improve this general upper bound for topologies T4× n(1,2,0) and T3× n(1,3,0). By relating the problem to generalized Sidon sets in \mathbbFq, we also obtain non-trivial lower bounds on the field size for maximally recoverable codes that instantiate topologies T4× n(1,2,0) and T3× n(1,3,0).