On the Single-Parity Locally Repairable Codes with Multiple Repairable Groups

Abstract

Locally repairable codes (LRCs) are a new family of erasure codes used in distributed storage systems which have attracted a great deal of interest in recent years. For an [ n , k , d ] linear code, if a code symbol can be repaired by t disjoint groups of other code symbols, where each group contains at most r code symbols, it is said to have availability- ( r , t ) . Single-parity LRCs are LRCs with a constraint that each repairable group contains exactly one parity symbol. For an [ n , k , d ] single-parity LRC with availability- ( r , t ) for the information symbols (single-parity LRCs), the minimum distance satisfies d ≤ n − k − ⌈ k t / r ⌉ + t + 1 . In this paper, we focus on the study of single-parity LRCs with availability- ( r , t ) for information symbols. Based on the standard form of generator matrices, we present a novel characterization of single-parity LRCs with availability t ≥ 1 . Then, a simple and straightforward proof for the Singleton-type bound is given based on the new characterization. Some necessary conditions for optimal single-parity LRCs with availability t ≥ 1 are obtained, which might provide some guidelines for optimal coding constructions.

Keywords

• Erasure codes
• locally repairable codes
• locality
• availability
• data reliability