Network Coding for Distributed Storage Systems

By A. Dimakis, Brighten Godfrey, Martin J. Wainwright, Kannan Ramchandran. IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications, 2007

2,113 citations recorded by the source corpus.

Peer-to-peer distributed storage systems provide reliable access to data through redundancy spread over nodes across the Internet. A key goal is to minimize the amount of bandwidth used to maintain that redundancy. Storing a file using an erasure code, in fragments spread across nodes, promises to require less redundancy and hence less maintenance bandwidth than simple replication to provide the same level of reliability. However, since fragments must be periodically replaced as nodes fail, a key question is how to generate a new fragment in a distributed way while transferring as little data as possible across the network. In this paper, we introduce a general technique to analyze storage architectures that combine any form of coding and replication, as well as presenting two new schemes for maintaining redundancy using erasure codes. First, we show how to optimally generate MDS fragments directly from existing fragments in the system. Second, we introduce a new scheme called regenerating codes which use slightly larger fragments than MDS but have lower overall bandwidth use. We also show through simulation that in realistic environments, regenerating codes can reduce maintenance bandwidth use by 25% or more compared with the best previous design - a hybrid of replication and erasure codes - while simplifying system architecture.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/3d3959f6b491ffb1ff799a7636ec93cc68927e1e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Femtocaching and device-to-device collaboration: A new architecture for wireless video distribution (2012, result): “While many of the results can be derived in closed form, we refer to our recent research papers [3], for details.”
Rethinking erasure codes for cloud file systems: minimizing I/O for recovery and degraded reads (2012, background): “Regenerating codes provide optimal recovery bandwidth [12] among storage nodes.”
XORing Elephants: Novel Erasure Codes for Big Data (2013, background): “Because the new codes repair failures faster, this provides higher reliability, which is orders of magnitude higher compared to replication.”
Speeding Up Distributed Machine Learning Using Codes (2015, background): “Recently, codes have begun to transform the storage layer of distributed systems in modern data centers under the umbrella of regenerating and locally repairable codes for distributed storage [6]–[21] which are also having a major impact on industry [22]–[25].”
A Survey on Network Codes for Distributed Storage (2010, methodology): “Functional [24]: ∀n, k, d”
Analyzing the download time of availability codes (2015, background): “coding theorists to look for novel erasure codes that are recovery efficient [14, 20, 40, 44, 53, 54].”
Locality and Availability in Distributed Storage (2014, background): “It is now well understood that classical codes (such as Reed-Solomon) are highly suboptimal for distributed settings due to the repair problem [1].”
Coding for fast content download (2012, result): “Research in coding for distributed storage was galvanized by the results reported in [1].”
Locally Repairable Codes (2012, neutral): “Let (r+ 1)|n and r ≤ n− d.”
Centralized Repair of Multiple Node Failures With Applications to Communication Efficient Secret Sharing (2016, background): “The model for communication efficient secret sharing [15], [16] is similar to that of [1] in the sense that one contacts to more than enough number of nodes (and download a partial data from each) in order to reduce the total amount of bits downloaded (to reveal the secret in the former, and to repa”
Erasure Coding in Windows Azure Storage (2012, background): “To improve reconstruction performance, instead of reading from fewer fragments as in LRC, a promising alternative is to read instead from more fragments, but less data from each [24, 25, 26, 27].”
Private information retrieval for coded storage (2014, background): “In [1], regenerating codes were proposed to achieve the optimal tradeoff between storage cost and repair cost.”