2014 · 25 citations · 51 references
ComputingComputer EngineeringComputer ScienceDistributed SystemsFault-tolerant ComputingStorage SystemsCoding TheoryData LocalityData ReplicationDistributed ComputingDistributed StorageHigh AvailabilityAvailability CodesAvailability TradeoffDistributed Storage CodesDistributed Storage ReliabilityHot Data ManagementMinimum DistanceMinimum Distance Bounds
This paper studies the problem of information symbol availability in codes: we refer to a systematic code as code with (r, t)-availability if every information (systematic) symbol can be reconstructed from t disjoint groups of other code symbols, each of the sizes at most r. This paper shows that it is possible to construct codes that can support a scaling number of parallel reads while keeping the rate to be an arbitrarily high constant. It further shows that this is possible with the minimum Hamming distance arbitrarily close to the Singleton bound. This paper also presents a bound demonstrating a tradeoff between rate, minimum Hamming distance, and availability parameters. Our codes match the aforementioned bound, and their constructions rely on certain combinatorial structures. Resolvable designs provide one way to realize these required combinatorial structures. The two constructions presented in this paper require field sizes, which are linear and exponential in the code length, respectively. From a practical standpoint, our codes are relevant for distributed storage applications involving hot data, i.e., the information, which is frequently accessed by multiple processes in parallel.
51
Network Coding for Distributed Storage Systems
Alexandros G. Dimakis, P. Brighten Godfrey, Yunnan Wu et al. · IEEE Transactions on Information Theory · 2010 · 2K citations
On the Locality of Codeword Symbols
Parikshit Gopalan, Cheng Huang, Huseyin Simitci et al. · IEEE Transactions on Information Theory · 2012 · 862 citations
Erasure coding in windows azure storage
Cheng Huang, Huseyin Simitci, Yikang Xu et al. · 2012 · 806 citations
Maheswaran Sathiamoorthy, Megasthenis Asteris, Dimitris Papailiopoulos et al. · Proceedings of the VLDB Endowment · 2013 · 689 citations