CaltechAUTHORS
  A Caltech Library Service

Explicit Minimum Storage Regenerating Codes

Wang, Zhiying and Tamo, Itzhak and Bruck, Jehoshua (2016) Explicit Minimum Storage Regenerating Codes. IEEE Transactions on Information Theory, 62 (8). pp. 4466-4480. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:20160930-131654865

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20160930-131654865

Abstract

In distributed storage, a file is stored in a set of nodes and protected by erasure-correcting codes. Regenerating code is a type of code with two properties: first, it can reconstruct the entire file in the presence of any r node erasures for some specified integer r; second, it can efficiently repair an erased node from any subset of remaining nodes with a given size. In the repair process, the amount of information transmitted from each node normalized by the storage size per node is termed repair bandwidth (fraction). When the storage size per node is minimized, the repair bandwidth is lower bounded by 1/r, where r is the number of parity nodes. A code attaining this lower bound is said to have optimal repair. We consider codes with minimum storage size per node and optimal repair, called minimum storage regenerating (MSR) codes. In particular, if an MSR code has r parities and any r erasures occur, then by transmitting all the information from the remaining nodes, the original file can be reconstructed. On the other hand, if only one erasure occurs, only a fraction of 1/r of the information in each remaining node needs to be transmitted. If we view each node as a vector or a column over some field, then the code forms a 2-D array. Given the length of the column l and the number of parities r, we explicitly construct the high-rate MSR codes. The number of systematic nodes of our construction is (r + 1) log_rl, which is longer than previously known results. Besides, we construct the MSR codes with other desirable properties: first, the codes with low complexity when the information is updated, and second, the codes with low access or storage node I/O cost during repair.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/TIT.2016.2553675DOIArticle
http://ieeexplore.ieee.org/document/7457282/PublisherArticle
Additional Information:© 2016 IEEE. Manuscript received October 17, 2014; revised November 15, 2015; accepted February 16, 2016. Date of publication April 20, 2016; date of current version July 12, 2016. Date of Current Version: 20 April 2016. This paper was presented at the 2012 IEEE International Symposium on Information Theory [20].
Record Number:CaltechAUTHORS:20160930-131654865
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20160930-131654865
Official Citation:Z. Wang, I. Tamo and J. Bruck, "Explicit Minimum Storage Regenerating Codes," in IEEE Transactions on Information Theory, vol. 62, no. 8, pp. 4466-4480, Aug. 2016. doi: 10.1109/TIT.2016.2553675
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:70698
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:30 Sep 2016 21:54
Last Modified:30 Sep 2016 21:54

Repository Staff Only: item control page