Codes With Locality for Two Erasures

• Published in: IEEE transactions on information theory 2019-12, Vol.65 (12), p.7771-7789
• Main Authors: Prakash, N., Lalitha, V., Balaji, S. B., Vijay Kumar, P.
• Format: Article
• Language: English
• Subjects: availability codes; Codes; Codes with locality; Data centers; generalized Hamming weights; Graphs; Linear codes; locally repairable codes; Maintenance engineering; multiple erasures; Recovery; Reliability; Repair; sequential recovery; Symbols; Systematics; Turan graph based constructions; two erasures; Upper bound; Upper bounds
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2019.2934124

Codes with locality are a class of codes introduced by Gopalan et al. to efficiently repair a failed node, by minimizing the number of nodes contacted during repair. An [n,k] systematic code is said to have information locality r , if each message symbol can be recovered by accessing \leq r other symbols. An [n,k] code is said to have all-symbol locality r , if each code symbol can be recovered by accessing \leq r other symbols. In this paper, we consider a generalization of codes with all-symbol locality to the case of handling two erasures. We study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. We refer to these codes as sequential-recovery locally repairable codes (denoted by 2-seq LR codes). Earlier approaches to handling multiple erasures considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. We derive an upper bound on the rate of 2-seq LR codes. We provide constructions based on regular graphs which are rate-optimal with respect to the derived bound. We also characterize the structure of any rate-optimal code. By studying the Generalized Hamming Weights of the dual code, we derive a recursive upper bound on the minimum distance of 2-seq LR codes. We also provide constructions of a family of codes based on Turán graphs, that are optimal with respect to this bound. We also present explicit distance-optimal Turán graph based constructions of 2-seq LR codes for certain parameters. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case.