2010 · 26 citations · 22 references
ComputingComputer EngineeringComputer ScienceFault-tolerant ComputingFault-tolerant SystemsStorage SystemsCoding TheoryDistributed StorageError Control CodingError CorrectionError-correcting CodesFault-tolerant Storage SystemsCode ConstructionsErasure CorrectionError Correction CodesLinear Block CodesLinear CodesMds CodesReed-solomon CodesStorage System Reliability
The problem of designing codes to protect against server failures in a distributed storage system for frequently changing data is considered. When the original data changes, the coded packets stored on the servers must be updated accordingly. Since performing updates consumes costly bandwidth and energy, it is of interest to construct codes that have small update complexity, which we define as the maximum number of coded symbols that must be updated when any single information symbol is changed. Linear codes which are conventionally used or recently proposed for use in storage systems for correcting a linear number of erasures (such as Reed-Solomon and other MDS codes) have the update complexity which scales linearly with the code length. In this paper, we take advantage of randomization to construct update-efficient codes that have update complexity scaling sub-linearly with the code length. Two erasure models are examined: random erasures (i.e., the erasure channel) and adversarial erasures.
22
Network Coding for Distributed Storage Systems
Alexandros G. Dimakis, P. Brighten Godfrey, Martin J. Wainwright et al. · 2007 · 394 citations · Full text