A Class of Binary Locally Repairable Codes

Abstract

An (n, k) erasure code that can recover any coded symbol by at most r other coded symbols is called a locally repairable code (LRC) with locality r. LRCs have been recently implemented in distributed storage systems. Coding complexity reduction can be significantly decreased by using binary LRCs (BLRCs) as they eliminate costly multiplication calculation. In this paper, motivated by the recently erasure codes with d = 4 used in practice, we propose BLRCs when (r + 1) | n and d = 4. We prove that our proposed binary codes are optimal for r ∈ {1, 3}, meaning that neither their locality nor their minimum distance can be improved by non-binary codes. For r ≥ 4, our proposed binary codes offer near-optimal code rate, with a rate gap of O(log r/n) compared with optimal nonbinary codes. While keeping the bulk of code structure binary, we eliminate this rate gap by using fields with sizes as small as r + 2 for only two redundant symbols. These non-binary codes still eliminate the need for costly multiplications in many operations including a single failure repair (a dominant repair scenario). Using the construction of spanning BLRC with d = 4 as a backbone, we also construct LRCs with minimum distance d ≥ 6. Furthermore, we obtain a closed-form equation for the mean-time to data-loss of arbitrary erasure codes.