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_5: Petabyte-scale distributed storage systems are currently transitioning to erasure codes to achieve higher storage efficiency. Classical codes like Reed-Solomon are highly sub-optimal for distributed environments due to their high overhead in single-failure events. Locally Repairable Codes (LRCs) form a new family of codes that are repair efficient. In particular, LRCs minimize the number of nodes participating in single node repairs during which they generate small network traffic. Two large-scale distributed storage systems have already implemented different types of LRCs: Windows Azure Storage and the Hadoop Distributed File System RAID used by Facebook. The fundamental bounds for LRCs, namely the best possible distance for a given code locality, were recently discovered, but few explicit constructions exist. In this work, we present an explicit and optimal LRCs that are simple to construct. Our construction is based on grouping Reed-Solomon (RS) coded symbols to obtain RS coded symbols over a larger finite field. We then partition these RS symbols in small groups, and re-encode them using a simple local code that offers low repair locality. For the analysis of the optimality of the code, we derive a new result on the matroid represented by the code generator matrix.
@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.
@cite_2: Regenerating codes and codes with locality are two schemes that have recently been proposed to ensure data collection and reliability in a distributed storage network. In a situation where one is attempting to repair a failed node, regenerating codes seek to minimize the amount of data downloaded for node repair, while codes with locality attempt to minimize the number of helper nodes accessed. In this paper, we provide several constructions for a class of vector codes with locality in which the local codes are regenerating codes, that enjoy both advantages. We derive an upper bound on the minimum distance of this class of codes and show that the proposed constructions achieve this bound. The constructions include both the cases where the local regenerating codes correspond to the MSR as well as the MBR point on the storage-repair-bandwidth tradeoff curve of regenerating codes. Also included is a performance comparison of various code constructions for fixed block length and minimum distance.
It was proved in @cite_2 that there exists optimal locally repairable linear codes when @math and @math . Under the condition that @math , a construction method of optimal locally repairable vector codes was proposed in @cite_7 , where maximal rank distance (MRD) codes were used along with MDS array codes. For the special case of @math , Tamo @cite_5 proposed an explicit construction of optimal LRCs when @math or @math Except for the special case that @math , no results are known about whether there exists optimal @math code when @math .