CaltechAUTHORS
  A Caltech Library Service

Access Versus Bandwidth in Codes for Storage

Tamo, Itzhak and Wang, Zhiying and Bruck, Jehoshua (2014) Access Versus Bandwidth in Codes for Storage. IEEE Transactions on Information Theory, 60 (4). pp. 2028-2037. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:20140425-151109319

[img] PDF - Submitted Version
See Usage Policy.

168Kb

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

Abstract

Maximum distance separable (MDS) codes are widely used in storage systems to protect against disk (node) failures. A node is said to have capacity l over some field F, if it can store that amount of symbols of the field. An (n, k, l) MDS code uses n nodes of capacity l to store k information nodes. The MDS property guarantees the resiliency to any n-k node failures. An optimal bandwidth (respectively, optimal access) MDS code communicates (respectively, accesses) the minimum amount of data during the repair process of a single failed node. It was shown that this amount equals a fraction of 1/(n - k) of data stored in each node. In previous optimal bandwidth constructions, l scaled polynomially with k in codes when the asymptotic rate is less than 1. Moreover, in constructions with a constant number of parities, i.e., when the rate approaches 1, l is scaled exponentially with k. In this paper, we focus on the case of linear codes with linear repair operations and constant number of parities n - k = r, and ask the following question: given the capacity of a node l what is the largest number of information disks k in an optimal bandwidth (respectively, access) (k + r, k, l) MDS code? We give an upper bound for the general case, and two tight bounds in the special cases of two important families of codes. The first is a family of codes with optimal update property, and the second is a family with optimal access property. Moreover, the bounds show that in some cases optimal-bandwidth codes have larger k than optimal-access codes, and therefore these two measures are not equivalent.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/TIT.2014.2305698DOIArticle
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6737213PublisherArticle
http://arxiv.org/abs/1303.3668arXivDiscussion Paper
Additional Information:© 2014 IEEE. Manuscript received March 14, 2013; revised November 5, 2013; accepted January 19, 2014. Date of publication February 11, 2014; date of current version March 13, 2014. This work was supported in part by the NSF under Grant ECCS-0801795 and in part by the BSF under Grant 2010075. This paper was presented at the 2012 IEEE International Symposium on Information Theory.
Funders:
Funding AgencyGrant Number
NSFECCS-0801795
Binational Science Foundation (USA-Israel)2010075
Subject Keywords:Data storage systems, network coding, repair problem, RAID
Record Number:CaltechAUTHORS:20140425-151109319
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20140425-151109319
Official Citation:Tamo, I.; Zhiying Wang; Bruck, J., "Access Versus Bandwidth in Codes for Storage," Information Theory, IEEE Transactions on , vol.60, no.4, pp.2028,2037, April 2014 doi: 10.1109/TIT.2014.2305698
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:45234
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:28 Apr 2014 15:07
Last Modified:19 Jan 2016 23:53

Repository Staff Only: item control page