We consider a communication problem in which an update of the source message needs to be conveyed to one or more distant receivers that are interested in maintaining specific linear functions of the source message. The setting is one in which the updates are sparse in nature, and where neither the source nor the receiver(s) is aware of the exact difference vector, but only know the amount of sparsity that is present in the difference-vector. Under this setting, we are interested in devising linear encoding and decoding schemes that minimize the communication cost involved. We show that the optimal solution to this problem is closely related to the notion of maximally recoverable codes (MRCs), which were originally introduced in the context of coding for storage systems. In the context of storage, MRCs guarantee optimal erasure protection when the system is partially constrained to have local parity relations among the storage nodes. In our problem, we show that optimal solutions exist if and only if MRCs of certain kind (identified by the desired linear functions) exist. We consider point-to-point and broadcast versions of the problem, and identify connections to MRCs under both these settings.
@cite_18: Practical storage systems often adopt erasure codes to tolerate device failures and sector failures, both of which are prevalent in the field. However, traditional erasure codes employ device-level redundancy to protect against sector failures, and hence incur significant space overhead. Recent sector-disk (SD) codes are available only for limited configurations due to the relatively strict assumption on the coverage of sector failures. By making a relaxed but practical assumption, we construct a general family of erasure codes called STAIR codes, which efficiently and provably tolerate both device and sector failures without any restriction on the size of a storage array and the numbers of tolerable device failures and sector failures. We propose the upstairs encoding and downstairs encoding methods, which provide complementary performance advantages for different configurations. We conduct extensive experiments to justify the practicality of STAIR codes in terms of space saving, encoding decoding speed, and update cost. We demonstrate that STAIR codes not only improve space efficiency over traditional erasure codes, but also provide better computational efficiency than SD codes based on our special code construction.
@cite_22: Mario Blaum∗, James S. Plank†, Moshe Schwartz‡, and Eitan Yaakobi§ ∗IBM Research Division, Almaden Research Center, San Jose, CA 95120, USA †Dept. of Electrical Engineering and Computer Science, Univ. of Tennessee, Knoxville, TN 37996, USA ‡Department of Electrical and Computer Engineering, Ben-Gurion University, Beer Sheva 8410501, Israel § Computer Science Department, Technion – Israel Institute of Technology, Haifa 32000, Israel mblaum@us.ibm.com, plank@cs.utk.edu, schwartz@ee.bgu.ac.il, yaakobi@cs.technion.ac.il
@cite_28: A new construction for sector-disk codes and partial MDS codes up to three sector erasures are proposed. In contrast to existing codes, which are based on the design of parity check matrix, our new code is based on the design of generator matrix. This new approach allows us to construct a code that requires a small field size. In particular, for the case when there is only one sector erasure, our field size requirement is independent of the number of sectors and is close to optimal. For the case when there are three sector erasures, we provide a condition which allows the code be constructed by computer search.
@cite_29: In this paper, we study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. By a local parity-check computation, we mean recovery via a single parity-check equation associated with small Hamming weight. Earlier approaches considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. These codes, which we refer to as locally 2-reconstructible codes, are a natural generalization along one direction, of codes with all-symbol locality introduced by , in which recovery from a single erasure is considered. By studying the generalized Hamming weights of the dual code, we derive upper bounds on the minimum distance of locally 2-reconstructible codes and provide constructions for a family of codes based on Turan graphs, that are optimal with respect to this bound. The minimum distance bound derived here is universal in the sense that no code which permits all-symbol local recovery from 2 erasures can have larger minimum distance regardless of approach adopted. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case.
@cite_1: Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, whereas other (heavy) parity symbols may depend on all data symbols. Such codes have been studied recently in the context of erasure coding for data storage, where the local parities facilitate fast recovery of any single symbol when it is erased, whereas the heavy parities provide tolerance to a large number of simultaneous erasures. A code as above is maximally recoverable, if it corrects all erasure patterns, which are information theoretically correctable given the prescribed dependence relations between data symbols and parity symbols. In this paper, we present explicit families of maximally recoverable codes with locality. We also initiate the general study of the tradeoff between maximal recoverability and alphabet size.
@cite_2: A family of codes with a natural 2-D structure is presented, inspired by an application of redundant arrays of independent disks (RAID) type of architectures whose units are solid-state drives (SSDs). Arrays of SSDs behave differently from arrays of hard disk drives, since hard errors in sectors are common and traditional RAID approaches (like RAID 5 or RAID 6) may be either insufficient or excessive. An efficient solution to this problem is given by the new codes presented, called partial maximum distance separable (PMDS) codes.
@cite_31: An [n, k] linear code C that is subject to locality constraints imposed by a parity check matrix H 0 is said to be a maximally recoverable (MR) code if it can recover from any erasure pattern that some k-dimensional subcode of the null space of H 0 can recover from. The focus in this paper is on MR codes constrained to have all-symbol locality r. Given that it is challenging to construct MR codes having small field size, we present results in two directions. In the first, we relax the MR constraint and require only that apart from the requirement of being an optimum all-symbol locality code, the code must yield an MDS code when punctured in a single, specific pattern which ensures that each local code is punctured in precisely one coordinate and that no two local codes share the same punctured coordinate. We term these codes as partially maximally recoverable (PMR) codes. We provide a simple construction for high-rate PMR codes and then provide a general, promising approach that needs further investigation. In the second direction, we present three constructions of MR codes with improved parameters, primarily the size of the finite field employed in the construction.
@cite_13: A code is said to be data-local maximally recoverable if (i) all the information symbols have locality and (ii) any erasure pattern which can be potentially recovered (i.e., the number of equations is equal to the number of unknowns) is recovered by the code. A code is said to be local maximally recoverable if (i) all the symbols of the code have locality and (ii) from the above holds. In this paper, we establish the matroid structures corresponding to data-local and local maximally recoverable codes (MRC). The matroid structures of these codes can be used to determine the associated Tutte polynomial. Greene proved that the weight enumerators of any code can be determined from its associated Tutte polynomial. We will use this result to derive explicit expressions for the weight enumerators of data-local MRC. Also, Britz proved that the higher support weights of any code can be determined from its associated Tutte polynomial. We will use this result to derive expressions for the higher support weights of data-local and local MRC with two local codes.
@cite_12: In this paper, we study the maximally recoverable (MR) property for multi-protection group (MPG) codes. MPG codes with MR property achieve the best erasure recoverability given configurations, where a configuration represents the structural relationship between data and parity symbols. We present construction and decoding algorithms for MPG codes with MR property. We show that both recoverability and minimum decoding overhead of any MPG code with MR property depend only on the configuration, where decoding overhead is defined as the additional number of symbols to access, in order to decode the lost data symbols.
Maximally Recoverable Codes: The notion of maximal recoverability in linear codes was originally introduced in @cite_12 . Low field size constructions of partial MDS codes (another name for MRCs with locality) for specific parameter sets codes appear in @cite_2 , @cite_22 , @cite_28 . In the terminology of partial MDS codes, these three works respectively provide low field size constructions for the settings up to one, two and three global parities, and any number of local parities. Explicit constructions based on linearized polynomials for the case of one local parity and any number of global parities appear in @cite_1 . Identifying low-field-size constructions of partial MDS codes for general parameter sets remain an open problem. Various approximations of partial MDS codes like Sector Disk codes @cite_2 , @cite_22 , @cite_28 , STAIR codes @cite_18 , and partial-maximally-recoverable-codes @cite_31 have been considered in literature, and these permit low field size constructions for larger parameter sets. Other known results on maximally recoverable codes include expressions for the weight enumerators of MRCs with locality @cite_13 , and the generalized Hamming weights (GHWs) of the MRSC @math in terms of the GHWs of the code @math @cite_29 .