Access Versus Bandwidth in Codes for Storage
Itzhak Tamo, Zhiying Wang, Jehoshua Bruck · IEEE Transactions on Information Theory · 2014
Maximum distance separable (MDS) codes are widely used in storage systems to protect against disk (node) failures. A node is said to have capacitylover 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 anyn-knode 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,lscaled 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,lis scaled exponentially withk. In this paper, we focus on the case of linear codes with linear repair operations and constant number of paritiesn-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 largerkthan optimal-access codes, and therefore these two measures are not equivalent.