arXiv Analytics

Sign in

arXiv:2006.03042 [cs.IT]AbstractReferencesReviewsResources

Access-optimal Linear MDS Convertible Codes for All Parameters

Francisco Maturana, V. S. Chaitanya Mukka, K. V. Rashmi

Published 2020-06-04Version 1

In large-scale distributed storage systems, erasure codes are used to achieve fault tolerance in the face of node failures. Tuning code parameters to observed failure rates has been shown to significantly reduce storage cost. Such tuning of redundancy requires "code conversion", i.e., a change in code dimension and length on already encoded data. Convertible codes are a new class of codes designed to perform such conversions efficiently. The access cost of conversion is the number of nodes accessed during conversion. Existing literature has characterized the access cost of conversion of linear MDS convertible codes only for a specific and small subset of parameters. In this paper, we present lower bounds on the access cost of conversion of linear MDS codes for all valid parameters. Furthermore, we show that these lower bounds are tight by presenting an explicit construction for access-optimal linear MDS convertible codes for all valid parameters. En route, we show that, one of the degrees-of-freedom in the design of convertible codes that was inconsequential in the previously studied parameter regimes, turns out to be crucial when going beyond these regimes and adds to the challenge in the analysis and code construction.

Comments: This is an extended version of an IEEE ISIT 2020 paper with the same title
Categories: cs.IT, cs.DC, cs.NI, math.IT
Related articles: Most relevant | Search more
arXiv:1703.00188 [cs.IT] (Published 2017-03-01)
Lower Bounds on Exponential Moments of the Quadratic Error in Parameter Estimation
arXiv:1005.2880 [cs.IT] (Published 2010-05-17)
General Classes of Lower Bounds on the Probability of Error in Multiple Hypothesis Testing
arXiv:0902.0133 [cs.IT] (Published 2009-02-01)
New Algorithms and Lower Bounds for Sequential-Access Data Compression