Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction

By K. V. Rashmi, Nihar B. Shah, F. I. P. Vijay Kumar. IEEE Transactions on Information Theory, 2010

720 citations recorded by the source corpus.

Regenerating codes are a class of distributed storage codes that allow for efficient repair of failed nodes, as compared to traditional erasure codes. An [n, k, d] regenerating code permits the data to be recovered by connecting to any k of the n nodes in the network, while requiring that a failed node be repaired by connecting to any d nodes. The amount of data downloaded for repair is typically much smaller than the size of the source data. Previous constructions of exact-regenerating codes have been confined to the case n=d+1 . In this paper, we present optimal, explicit constructions of (a) Minimum Bandwidth Regenerating (MBR) codes for all values of [n, k, d] and (b) Minimum Storage Regenerating (MSR) codes for all [n, k, d ≥ 2k-2], using a new product-matrix framework. The product-matrix framework is also shown to significantly simplify system operation. To the best of our knowledge, these are the first constructions of exact-regenerating codes that allow the number n of nodes in the network, to be chosen independent of the other parameters. The paper also contains a simpler description, in the product-matrix framework, of a previously constructed MSR code with [n=d+1, k, d ≥ 2k-1].

Subfields: Computer Networks and Communications, Information Systems

View Paper: https://www.semanticscholar.org/paper/d0895dccd61c567034d197eecfa5d7d59332061f

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

In Information Systems

Citations in the corpus

Communication Efficient Secret Sharing (2015, background): “We also remark on an interesting analog between communication efficient secret sharing and the well-studied subject of regenerating codes [8], [22], [16].”
Fractional Repetition and Erasure Batch Codes (2014, background): “optimize the storage overhead and repair bandwidth, respectively (for constructions see [4, 5, 12, 13] and references therein).”
Centralized Repair of Multiple Node Failures With Applications to Communication Efficient Secret Sharing (2016, background): “Over the past few years, the problem of designing regenerating codes has fueled numerous research efforts which have resulted into the constructions presented in [1], [2], [3], [4], [5] and the references therein.”
Staircase codes for secret sharing with optimal communication and read overheads (2015, background): “t and the keys in a d × α matrix M deﬁned in Table 2. The inspiration behind this construction is the class of Product Matrix codes that minimizes the repair bandwidth in distributed storage systems6 [22]. M = S D R2 R1 0 d×α k α−k α z k z α−k Table 2: The structure of the matrix M that cont”
A Family of Optimal Locally Recoverable Codes (2013, neutral): “, the repair-bandwidth [6], [22], [25], [27], [5], [18] , ii), the number of bits read, the disk-I/O [13], [27], and iii), repai r locality, i.”
A Survey on Network Codes for Distributed Storage (2010, background): “Also, under functional repair, significant system overhead is incurred in order to continually update repairing-and-decoding rules whenever a failure occurs.”