1 Access vs. Bandwidth in Codes for Storage
Itzhak Tamo, Zhiying Wang, Jehoshua Bruck · 2012
Abstract—Maximum distance separable (MDS) codes are widely used in storage systems to protect against disk (node) failures. 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 (resp. optimal access) MDS code communicates (resp. accesses) the minimum amount of data during the recovery 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 with asymptotic rate < 1. Moreover, in constructions with a constant number of parities, i.e. rate approaches 1, l is scaled exponentially w.r.t. k. In this paper, we focus on the practical case of n − k = 2, and ask the following question: Given the capacity of a node l what is the largest (w.r.t. k) optimal bandwidth (resp. access) (k + 2, 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. I.