2021 IEEE International Symposium on Information Theory (ISIT 2021) 12-20 July 2021 • Melbourne, Victoria, Australia.
Francisco Maturana and K. V. Rashmi
Carnegie Mellon University
In distributed storage systems, an [n; k] code encodes k message symbols into n codeword symbols which are then stored on n nodes in the system. Recent work has shown that significant savings in storage space can be obtained by tuning n and k to variations in device failure rates. Such tuning necessitates code conversion: the process of converting data encoded under an [nI ; kI ] code to its equivalent under an [nF ; kF ] code. The default approach for code conversion places significant burden on system resources. Convertible codes are a recently proposed class of codes for enabling resource-efficient conversions. Existing work on convertible codes has focused on minimizing access cost, i.e., the number of nodes accessed during conversion. Bandwidth, which corresponds to the amount of data read and transferred, is another important resource to optimize during conversions. In this paper, we initiate the study on the fundamental limits on conversion bandwidth and present constructions for conversionbandwidth optimal convertible codes. First, we model the code conversion problem using information flow graphs with variable capacity edges. Second, focusing on MDS codes and an important subclass of convertible codes, we derive a lower bound on conversion bandwidth. The derived bound shows that conversion bandwidth can be significantly reduced even in regimes where access cost of conversion cannot be reduced. Third, we present an explicit construction for MDS convertible codes which match this lower bound and are thus conversion-bandwidth optimal.
FULL PAPER: pdf