New Bounds on the Field Size for Maximally Recoverable Codes Instantiating Grid-like Topologies

DOI10.1007/S10801-021-01013-1arXiv1901.06915WikidataQ114226146 ScholiaQ114226146MaRDI QIDQ6312784FDOQ6312784

Authors: Xiangliang Kong, Jingxue Ma, Gennian Ge 

Publication date: 21 January 2019

Abstract: 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. cite{Gopalan2017} 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 $T_{mimesn}(1,b,0)$. To characterize the property of codes for these topologies, we introduce the notion of emph{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 $T_{mimesn}(1,b,0)$. And using hypergraph independent set approach, we further improve this general upper bound for topologies $T_{4imesn}(1,2,0)$ and $T_{3imesn}(1,3,0)$. By relating the problem to generalized emph{Sidon sets} in $mathbb{F}_q$, we also obtain non-trivial lower bounds on the field size for maximally recoverable codes that instantiate topologies $T_{4imesn}(1,2,0)$ and $T_{3imesn}(1,3,0)$.

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Bounds on codes (94B65) Other types of codes (94B60)

This page was built for publication: New Bounds on the Field Size for Maximally Recoverable Codes Instantiating Grid-like Topologies

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