Quasi-cyclic regenerating codes for distributed storage: Existence and near-MSR examples

Regenerating codes for distributed storage systems promise significant improvements in the cost and maintenance requirements of large-scale data centers. Research in this area continues to define important new parameters and requirements that have the biggest impact in practice. One of the simplest requirements for a regenerating code is the so-called MSR property, which minimizes the number of bits downloaded during repair. Quasi-cyclic MSR codes are of particular interest, mainly for reducing the encoding and decoding complexity. However, quasi-cyclic MSR codes have not been studied in detail in the existing literature. In this work, we prove the negative result that quasi-cyclic MSR codes with no symbol extension do not exist if the number of systematic nodes is greater than or equal to 4. We provide several examples of quasi-cyclic near-MSR codes, which could be useful for reducing implementation complexity. We point out some interesting connections between zeros of quasi-cyclic codes and the MSR requirement, which are useful in the study of quasi-cyclic regenerating codes with symbol extension. © 2013 IEEE.