Bounds and Constructions of Maximally Recoverable Codes for Various Topologies

Abstract

In the present era of Big Data, the demand for storing vast amounts of data is rapidly increasing among companies such as Facebook, Microsoft, Google, Intel, IBM, and others, for newlinevarious applications. To address this need, Distributed Storage Systems (DSSs) have been established, offering improved capabilities in terms of flexibility, scalability, speed, and cost. In newlineDSS, data is distributed and stored on different nodes and are connected through the network. newlineHowever, data loss is inevitable due to physical limitations such as hardware failures and power newlineshutdowns. Maximum Distance Separable (MDS) codes are very efficient in terms of storage newlineoverhead. For practicality, Locally Recoverable codes (LRCs) are discovered to facilitate the newlinelow reconstruction cost for single and multiple failures (Independent and correlated), with a newlineslight increase in storage overhead. Maximally recoverable codes are a class of codes that newlinerecover from all potentially recoverable erasure patterns given the locality constraints of the newlinecode. Our main objectives are to provide MRCs for independent failures, correlated failures newlinewith low computational complexity, and encoding complexity. newlineIn earlier works, codes have been studied in the context of codes with the locality to handle newlineindependent failures. The notion of locality has been extended to the hierarchical locality, newlinewhich allows for the locality to gradually increase in levels with the increase in the number of newlineerasures. In one direction, we consider MRC for the case of codes with 2-level hierarchical newlinelocality for the specific topology (locality constraints) called Hierarchical Local MRC (HLMRC). We derive a field size lower bound on HL-MRC. We also give constructions of HLMRC for some parameters whose field size is smaller than that of earlier known constructions. newlineWe investigate Locally Recoverable Codes (LRCs) with availability, which refers to the newlineability to have multiple repair sets. The presence of multiple repair sets in LRCs is beneficial as it facilitates the distribution of the