Exact-MSR Codes for Distributed Storage with Low Repair Complexity

In this paper, we propose two new constructions of exact-repair minimum storage regenerating (exact-MSR) codes. For both constructions, the encoded symbols are obtained by treating the message vector over GF(q) as a linearized polynomial and evaluating it over an extension field GF(q^m). For our exact-MSR codes, data repair does not need matrix inversion, and can be implemented by additions and multiplications over GF$(q)$ as well as cyclic shifts when a normal basis is used. The two constructions assume a base field of GF(q) (q>2) and GF(2), respectively. In contrast to existing constructions of exact-MSR codes, the former construction works for arbitrary code parameters, provided that $q$ is large enough. This is the first construction of exact-MSR codes with arbitrary code parameters, to the best of our knowledge. In comparison to existing exact-MSR codes, while data construction of our exact-MSR codes has a higher complexity, the complexity of data repair is lower. Thus, they are attractive for applications that need a small number of data reconstructions along with a large number of data repairs.