2014 · 129 citations · 23 references
ComputingComputer EngineeringComputer ScienceFault ToleranceFault-tolerant SystemsStorage SystemsCoding TheoryData RedundancyError Control CodingError-correcting CodesFault-tolerant Storage SystemsReliable Storage SystemsBinary CodesCode OptimalityCodes Over Finite FieldsCyclic CodesLinear CodesLocally Repairable CodesMinimum DistanceUpper Bounds
Codes for storage systems aim to minimize the repair locality, which is the number of disks (or nodes) that participate in the repair of a single failed disk. Simultaneously, the code must sustain a high rate, operate on a small finite field to be practically significant and be tolerant to a large number of erasures. To this end, we construct new families of binary linear codes that have an optimal dimension (rate) for a given minimum distance and locality. Specifically, we construct cyclic codes that are locally repairable for locality 2 and distances 2, 6 and 10. In doing so, we discover new upper bounds on the code dimension, and prove the optimality of enabling local repair by provisioning disjoint groups of disks. Finally, we extend our construction to build codes that have multiple repair sets for each disk.
23
The Hadoop Distributed File System
Konstantin V. Shvachko, Hairong Kuang, Sanjay Radia et al. · 2010 · 4.8K citations
Network Coding for Distributed Storage Systems
Alexandros G. Dimakis, P. Brighten Godfrey, Yunnan Wu et al. · IEEE Transactions on Information Theory · 2010 · 2K citations
Sanjay Ghemawat, Howard Gobioff, Shun-Tak A. Leung · 2003 · 1.3K citations
On the Locality of Codeword Symbols
Parikshit Gopalan, Cheng Huang, Huseyin Simitci et al. · IEEE Transactions on Information Theory · 2012 · 862 citations