Optimal Locally Repairable Linear Codes

摘要

Linear erasure codes with local repairability are desirable for distributed data storage systems. An [n,k,d] linear code having all-symbol (r,δ)-locality, denoted as (r,δ)_a, is considered optimal if it has the actual highest minimum distance of any code of the given parameters n,k,r and δ. A minimum distance bound is given in . The existing results on the existence and the construction of optimal (r, δ)_a linear codes are limited to only two small regions within this special case, namely, i) m=0 and ii) mȦ5; (v+δ-1)>(δ-1) and δ=2, where m=n mod(r+δ-1) and v=k mod r. This paper investigates the properties and existence conditions for optimal (r,δ)_a linear 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 (r,δ)_a linear code can achieve the minimum distance bound in . For four other cases the optimal (r,δ)_a codes are shown to exist over a field of size qȦ5;({n} {k-1}), deterministic constructions are proposed. Our new constructive algorithms not only cover more cases, but for the same cases where previous algorithms exist, the new constructions require a smaller field, which translates to potentially lower computational complexity. Our findings substantially enriches the knowledge on optimal (r,δ)_a linear codes, leaving only two cases in which the construction of optimal codes are not yet known.