Optimal Locally Repairable Codes and Connections to Matroid Theory
Itzhak Tamo, Dimitris Papailiopoulos, Alexandros G. Dimakis · IEEE Transactions on Information Theory · 2016
Petabyte-scale distributed storage systems are currently transitioning to erasure codes to achieve higher storage efficiency. Classical codes, such as Reed-Solomon (RS), are highly sub-optimal for distributed environments due to their high overhead during single-failure events. Locally repairable codes (LRCs) form a new family of codes that are repair efficient. In particular, LRCs minimize the number of nodes participating in single node repairs. Fundamental bounds and methods for explicitly constructing LRCs suitable for deployment in distributed storage clusters are not fully understood and currently form an active area of research. In this paper, we present an explicit LRC that is simple to construct and is optimal for a specific set of coding parameters. Our construction is based on grouping RS symbols and then adding extra simple parities that allow for small repair locality. For the analysis of the optimality of the code, we derive a new result on the matroid represented by the code's generator matrix.