Linear erasure codes with local repairability are desirable for distributed data storage systems. An [n, k, d] code having all-symbol (r, )-locality, denoted as (r, )a, is considered optimal if it also meets the minimum Hamming distance bound. The existing results on the existence and the construction of optimal (r, )a codes are limited to only the special case of = 2, and to only two small regions within this special case, namely, m = 0 or m >= (v+ -1) > ( -1), where m = n mod (r+ -1) and v = k mod r. This paper investigates the existence conditions and presents deterministic constructive algorithms for optimal (r, )a codes with general r and . First, a structure theorem is derived for general optimal (r, )a codes which helps illuminate some of their structure properties. Next, the entire problem space with arbitrary n, k, r and is divided into eight different cases (regions) with regard to the specific relations of these parameters. For two cases, it is rigorously proved that no optimal (r, )a could exist. For four other cases the optimal (r, )a codes are shown to exist, deterministic constructions are proposed and the lower bound on the required field size for these algorithms to work is provided. Our new constructive algorithms not only cover more cases, but for the same cases where previous algorithms exist, the new constructions require a considerably smaller field, which translates to potentially lower computational complexity. Our findings substantially enriches the knowledge on (r, )a codes, leaving only two cases in which the existence of optimal codes are yet to be determined.
@cite_14: One main challenge in the design of distributed storage codes is the Exact Repair Problem: if a node storing encoded information fails, to maintain the same level of reliability, we need to exactly regenerate what was lost in a new node. A major open problem in this area has been the design of codes that i) admit exact and low cost repair of nodes and ii) have arbitrarily high data rates. In this paper, we are interested in the metric of repair locality, which corresponds to the the number of disk accesses required during a node repair. Under this metric we characterize an information theoretic trade-off that binds together locality, code distance, and storage cost per node. We introduce Locally repairable codes (LRCs) which are shown to achieve this tradeoff. The achievability proof uses a “locality aware” flow graph gadget which leads to a randomized code construction. We then present the first explicit construction of LRCs that can achieve arbitrarily high data-rates.
@cite_7: This paper aims to go beyond resilience into the study of security and local-repairability for distributed storage systems (DSSs). Security and local-repairability are both important as features of an efficient storage system, and this paper aims to understand the trade-offs between resilience, security, and local-repairability in these systems. In particular, this paper first investigates security in the presence of colluding eavesdroppers, where eavesdroppers are assumed to work together in decoding the stored information. Second, this paper focuses on coding schemes that enable optimal local repairs. It further brings these two concepts together to develop locally repairable coding schemes for DSS that are secure against eavesdroppers. The main results of this paper include: 1) an improved bound on the secrecy capacity for minimum storage regenerating codes; 2) secure coding schemes that achieve the bound for some special cases; 3) a new bound on minimum distance for locally repairable codes; 4) code construction for locally repairable codes that attain the minimum distance bound; and 5) repair-bandwidth-efficient locally repairable codes with and without security constraints.
Locality of general codes (linear or nonlinear) and bounds on the minimum distance for a given locality were presented in parallel and subsequent works @cite_14 @cite_7 . An @math code (systematic or not) is also termed a , and @math codes that achieve the minimum distance bound are called .