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. https://resolver.caltech.edu/CaltechAUTHORS:20140425-151109319
![]() |
PDF
- Submitted Version
See Usage Policy. 168Kb |
Use this Persistent URL to link to this item: https://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: |
| ||||||||||||
ORCID: |
| ||||||||||||
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: |
| ||||||||||||
Subject Keywords: | Data storage systems, network coding, repair problem, RAID | ||||||||||||
Issue or Number: | 4 | ||||||||||||
Record Number: | CaltechAUTHORS:20140425-151109319 | ||||||||||||
Persistent URL: | https://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: | 22 Nov 2019 09:58 |
Repository Staff Only: item control page