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 various applications. To address this need, Distributed Storage Systems (DSSs) have been established, offering improved capabilities in terms of flexibility, scalability, speed, and cost. In DSS, data is distributed and stored on different nodes and are connected through the network. However, data loss is inevitable due to physical limitations such as hardware failures and power shutdowns. Maximum Distance Separable (MDS) codes are very efficient in terms of storage overhead. For practicality, Locally Recoverable codes (LRCs) are discovered to facilitate the low reconstruction cost for single and multiple failures (Independent and correlated), with a slight increase in storage overhead. Maximally recoverable codes are a class of codes that recover from all potentially recoverable erasure patterns given the locality constraints of the code. Our main objectives are to provide MRCs for independent failures, correlated failures with low computational complexity, and encoding complexity. In earlier works, codes have been studied in the context of codes with the locality to handle independent failures. The notion of locality has been extended to the hierarchical locality, which allows for the locality to gradually increase in levels with the increase in the number of erasures. In one direction, we consider MRC for the case of codes with 2-level hierarchical locality 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. We investigate Locally Recoverable Codes (LRCs) with availability, which refers to the ability to have multiple repair sets. The presence of multiple repair sets in LRCs is beneficial as it facilitates the distribution of the repair load among various nodes. This distribution helps prevent excessive strain on specific nodes and promotes a more balanced workload within the system. In our research, we expand on the concept of availability in Locally Recoverable Codes (LRCs) and apply it to codes with hierarchical locality. The minimum distance plays a vital role in determining the codes’ capability to handle erasures effectively. Our study focuses on investigating the upper bound of the minimum distance for the specific case of LRCs with hierarchical locality. To reduce the encoding complexity, Halbawi et al. introduced sparse and balanced generator matrices for MDS (Reed - Solomon) code and LRCs (Tamo-Barg code) for single erasure. Building upon this work, we contribute by presenting sparse generator matrices for MRC with locality for single erasure. Furthermore, we also provide sparse and balanced generator matrices for MRC with locality, specifically for single erasures where the locality value is set to 2. In order to deal with correlated failures, Gopalan et al. initiated the study of MRCs gridlike and product topologies. In another research direction, we focus on MR codes for product topology Tm,n(a, b). Product codes are a class of codes with generator matrices as the tensor product of the generator matrices of component codes. The codeword can be represented as an m × n array, where the component codes are referred to as the row and column codes. We derive a few properties of maximally recoverable product codes. We give a sufficient condition to characterize a certain subclass of erasure patterns as correctable and another necessary condition to characterize another subclass of erasure patterns as not correctable. We construct a certain bipartite graph based on the erasure pattern satisfying the regularity condition (a necessary condition for recoverability) for product topology and show that there exists a complete matching in this graph. We used this condition to identify a subset of recoverable erasure patterns for a = 2. In earlier work, higher-order MDS codes denoted by MDS(l) have been defined in terms of generic matrices, and these codes have been shown to be constituent row codes for maximally recoverable product codes for the case of a = 1. We derive a certain inclusion-exclusion type principle for characterizing the dimension of intersection spaces of generic matrices. Applying this, we formally derive a relation between MDS(3) codes and points/lines of the associated projective space