A code symbol of a linear code is said to have locality r if this symbol could be recovered by at most r other code symbols. An (n,k,r) locally repairable code (LRC) with all symbol locality is a linear code with length n, dimension k, and locality r for all symbols. Recently, there are lots of studies on the bounds and constructions of LRCs, most of which are essentially based on the generator matrix of the linear code. Up to now, the most important bounds of minimum distance for LRCs might be the well-known Singleton-like bound and the Cadambe-Mazumdar bound concerning the field size. In this paper, we study the bounds and constructions of LRCs from views of parity-check matrices. Firstly, we set up a new characterization of the parity-check matrix for an LRC. Then, the proposed parity-check matrix is employed to analyze the minimum distance. We give an alternative simple proof of the well-known Singleton-like bound for LRCs with all symbol locality, and then easily generalize it to a more general bound, which essentially coincides with the Cadambe-Mazumdar bound and includes the Singleton-like bound as a specific case. Based on the proposed characterization of parity-check matrices, necessary conditions of meeting the Singleton-like bound are obtained, which naturally lead to a construction framework of good LRCs. Finally, two classes of optimal LRCs based on linearized polynomial theories and Vandermonde matrices are obtained under the construction framework.
This paper studies the problem of code symbol availability: a code symbol is said to have @math -availability if it can be reconstructed from @math disjoint groups of other symbols, each of size at most @math . For example, @math -replication supports @math -availability as each symbol can be read from its @math other (disjoint) replicas, i.e., @math . However, the rate of replication must vanish like @math as the availability increases. This paper shows that it is possible to construct codes that can support a scaling number of parallel reads while keeping the rate to be an arbitrarily high constant. It further shows that this is possible with the minimum distance arbitrarily close to the Singleton bound. This paper also presents a bound demonstrating a trade-off between minimum distance, availability and locality. Our codes match the aforementioned bound and their construction relies on combinatorial objects called resolvable designs. From a practical standpoint, our codes seem useful for distributed storage applications involving hot data, i.e., the information which is frequently accessed by multiple processes in parallel. A locally recoverable code (LRC code) is a code over a finite alphabet such that every symbol in the encoding is a function of a small number of other symbols that form a recovering set. Bounds on the rate and distance of such codes have been extensively studied in the literature. In this paper we derive upper bounds on the rate and distance of codes in which every symbol has @math disjoint recovering sets. In this work, we present a new upper bound on the minimum distance d of linear locally repairable codes (LRCs) with information locality and availability. The bound takes into account the code length n, dimension k, locality r, availability t, and field size q. We use tensor product codes to construct several families of LRCs with information locality, and then we extend the construction to design LRCs with information locality and availability. Some of these codes are shown to be optimal with respect to their minimum distance, achieving the new bound. Finally, we study the all-symbol locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and 4-cycle free regular low-density parity-check (LDPC) codes. We also investigate their optimality using the new bound. In distributed storage systems, erasure codes with locality (r ) are preferred because a coordinate can be locally repaired by accessing at most (r ) other coordinates which in turn greatly reduces the disk I O complexity for small (r ) . However, the local repair may not be performed when some of the (r ) coordinates are also erased. To overcome this problem, we propose the ((r, )_ c ) -locality providing ( -1 ) nonoverlapping local repair groups of size no more than (r ) for a coordinate. Consequently, the repair locality (r ) can tolerate ( -1 ) erasures in total. We derive an upper bound on the minimum distance for any linear ([n,k] ) code with information ((r, )_ c ) -locality. Then, we prove existence of the codes that attain this bound when (n k(r( -1)+1) ) . Although the locality ((r, ) ) defined by provides the same level of locality and local repair tolerance as our definition, codes with ((r, )_ c ) -locality attaining the bound are proved to have more advantage in the minimum distance. In particular, we construct a class of codes with all symbol ((r, )_ c ) -locality where the gain in minimum distance is ( ( r ) ) and the information rate is close to 1. A code over a finite alphabet is called locally recoverable (LRC) if every symbol in the encoding is a function of a small number (at most r ) other symbols. We present a family of LRC codes that attain the maximum possible value of the distance for a given locality parameter and code cardinality. The codewords are obtained as evaluations of specially constructed polynomials over a finite field, and reduce to a Reed-Solomon code if the locality parameter r is set to be equal to the code dimension. The size of the code alphabet for most parameters is only slightly greater than the code length. The recovery procedure is performed by polynomial interpolation over r points. We also construct codes with several disjoint recovering sets for every symbol. This construction enables the system to conduct several independent and simultaneous recovery processes of a specific symbol by accessing different parts of the codeword. This property enables high availability of frequently accessed data (“hot data”). Repair locality is a desirable property for erasure codes in distributed storage systems. Recently, different structures of local repair groups have been proposed in the definitions of repair locality. In this paper, the concept of regenerating set is introduced to characterize the local repair groups. A definition of locality @math (i.e., locality @math with repair tolerance @math ) under the most general structure of regenerating sets is given. All previously studied locality turns out to be special cases of this definition. Furthermore, three representative concepts of locality proposed before are reinvestigated under the framework of regenerating sets, and their respective upper bounds on the minimum distance are reproved in a uniform and brief form. Additionally, a more precise distance bound is derived for the square code which is a class of linear codes with locality @math and high information rate, and an explicit code construction attaining the optimal distance bound is obtained. Distributed storage systems need to store data redundantly in order to provide some fault-tolerance and guarantee system reliability. Different coding techniques have been proposed to provide the required redundancy more efficiently than traditional replication schemes. However, compared to replication, coding techniques are less efficient for repairing lost redundancy, as they require retrieval of larger amounts of data from larger subsets of storage nodes. To mitigate these problems, several recent works have presented locally repairable codes designed to minimize the repair traffic and the number of nodes involved per repair. Unfortunately, existing methods often lead to codes where there is only one subset of nodes able to repair a piece of lost data, limiting the local repairability to the availability of the nodes in this subset. In this paper, we present a new family of locally repairable codes that allows different trade-offs between the number of contacted nodes per repair, and the number of different subsets of nodes that enable this repair. We show that slightly increasing the number of contacted nodes per repair allows to have repair alternatives, which in turn increases the probability of being able to perform efficient repairs. Finally, we present pg-BLRC, an explicit construction of locally repairable codes with multiple repair alternatives, constructed from partial geometries, in particular from Generalized Quadrangles. We show how these codes can achieve practical lengths and high rates, while requiring a small number of nodes per repair, and providing multiple repair alternatives. The @math th coordinate of an @math code is said to have locality @math and availability @math if there exist @math disjoint groups, each containing at most @math other coordinates that can together recover the value of the @math th coordinate. This property is particularly useful for codes for distributed storage systems because it permits local repair and parallel accesses of hot data. In this paper, for any positive integers @math and @math , we construct a binary linear code of length @math which has locality @math and availability @math for all coordinates. The information rate of this code attains @math , which is always higher than that of the direct product code, the only known construction that can achieve arbitrary locality and availability.