CaltechAUTHORS
  A Caltech Library Service

On Codes for Optimal Rebuilding Access

Wang, Zhiying and Tamo, Itzhak and Bruck, Jehoshua (2011) On Codes for Optimal Rebuilding Access. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2011.ETR111

[img]
Preview
PDF
See Usage Policy.

159Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2011.ETR111

Abstract

MDS (maximum distance separable) array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with r redundancy nodes can correct any r erasures by accessing (reading) all the remaining information in both the systematic nodes and the parity (redundancy) nodes. However, in practice, a single erasure is the most likely failure event; hence, a natural question is how much information do we need to access in order to rebuild a single storage node? We define the rebuilding ratio as the fraction of remaining information accessed during the rebuilding of a single erasure. In our previous work we showed that the optimal rebuilding ratio of 1/r is achievable (using our newly constructed array codes) for the rebuilding of any systematic node, however, all the information needs to be accessed for the rebuilding of the parity nodes. Namely, constructing array codes with a rebuilding ratio of 1/r was left as an open problem. In this paper, we solve this open problem and present array codes that achieve the lower bound of 1/r for rebuilding any single systematic or parity node.


Item Type:Report or Paper (Technical Report)
Additional Information:We thank Dimitris Papailiopoulos, Alexandros Dimakis and Viveck Cadambe for the inspiring discussions. [Also available at http://www.paradise.caltech.edu/papers/etr111.pdf]
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:2011.ETR111
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:2011.ETR111
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26142
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:14 Jul 2011
Last Modified:26 Dec 2012 13:54

Repository Staff Only: item control page