On MDS Convertible Codes in the Merge Regime This work was presented in part at the 2025 IEEE International Symposium on Information Theory (ISIT) [ 1 ] . Vinayak Ramkumar is with the Institute for Communications Engineering, Technical University of Munich, Germany. Xiangliang Kong is with the Depar
Vinayak Ramkumar, Xiangliang Kong, G. Yeswanth Sai, Myna Vajha, M. Nikhil Krishnan · 2025
Read On MDS Convertible Codes in the Merge Regime This work was presented in part at the 2025 IEEE International Symposium on Information Theory (ISIT) [ 1 ] . Vinayak Ramkumar is with the Institute for Communications Engineering, Technical University of Munich, Germany. Xiangliang Kong is with the Depar by Vinayak Ramkumar, Xiangliang Kong, G. Yeswanth Sai, Myna Vajha, M. Nikhil Krishnan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-06219.txt.
Introduction
Vinayak Ramkumar, Xiangliang Kong, and their co-authors study codes that change shape inside large storage systems. Their 2025 paper explains that data centers guard files with erasure codes, which rebuild lost data from spare pieces. When disk failure rates shift, resizing the code can save much storage at the same safety level.
Such resizing is called code conversion. The authors study the merge case, where several codewords of a top grade code fuse into one codeword of a new code. They give three constructions that reach the lowest possible access cost, meaning the fewest disks touched during conversion. The first two need set conditions on the spare count and field size. The third builds on an earlier scheme to widen the range.
Catalog record
| CREATOR | Vinayak Ramkumar, Xiangliang Kong, G. Yeswanth Sai, Myna Vajha, M. Nikhil Krishnan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 89 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-06219
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On MDS Convertible Codes in the Merge Regime This work was presented in part at the 2025 IEEE International Symposium on Information Theory (ISIT) [ 1 ] . Vinayak Ramkumar is with the Institute for Communications Engineering, Technical University of Munich, Germany. Xiangliang Kong is with the Department of Electrical Engineering–Systems, Tel Aviv University, Israel. G. Yeswanth Sai is with the Mehta Family School of Data Science & Artificial Intelligence, Indian Institute of Technology Palakkad, India. Myna Vajha is with the Department of Electrical Engineering, Indian Institute of Technology Hyderabad, India. M. Nikhil Krishnan is jointly with the Mehta Family School of Data Science & Artificial Intelligence and the Department of Electrical Engineering, Indian Institute of Technology Palakkad, India. Emails: {vinram93, rongxlkong, ysai0158, mynaramana, nikhilkrishnan.m}@gmail.com Vinayak Ramkumar, Xiangliang Kong, G. Yeswanth Sai, Myna Vajha, M. Nikhil Krishnan Abstract In large-scale distributed storage systems, erasure coding is employed to ensure reliability against disk failures. Recent work by Kadekodi et al. demonstrates that adapting code parameters to varying disk failure rates can lead to significant storage savings without compromising reliability. Such adaptations, known as code conversions , motivate the design of convertible codes , which enable efficient transformations between codes of different parameters. In this work, we study the setting in which λ \lambda codewords of an initial [ n I = k I + r I , k I ] [n^{I}=k^{I}+r^{I},\,k^{I}] MDS code are merged into a single codeword of a final [ n F = λ k I + r F , k F = λ k I ] [n^{F}=\lambda k^{I}+r^{F},\,k^{F}=\lambda k^{I}] MDS code. We begin by presenting three constructions that achieve optimal access cost , defined as the total number of disks accessed during the conversion process. The first two constructions apply when λ ≤ r I \lambda\leq r^{I} and impose specific divisibility conditions on r I r^{I} and the field size q q . These schemes minimize both the per-symbol and the overall access cost. The third construction, which builds on a prior scheme by Kong, achieves minimal access cost while supporting arbitrary parameter regimes. All three constructions require field sizes that are linear in the final code length, and notably, the third construction achieves a field size that matches the lower bound implied by the MDS conjecture in almost all cases. In addition, we propose a construction that optimizes the bandwidth cost , defined as the total number of symbols transmitted during conversion. This scheme is a refinement of Maturana and Rashmi’s bandwidth-optimal construction based on the piggybacking framework, and achieves reduced sub-packetization. I Introduction Erasure codes are widely used in distributed storage systems to efficiently provide fault tolerance. An [n,k] erasure code over a finite field \mathbb{F}_{q} encodes a file by first dividing it into k data symbols and then encoding them into n coded symbols. Each coded symbol is stored on a separate disk to ensure resilience against disk failures. Nowadays, most storage systems employ a static erasure code, where the code parameters n,k (typically chosen based on the expected disk failure rate) remain fixed throughout the system’s lifetime. However, this design may render the storage system either storage-inefficient or increasingly vulnerable to failures as the disks age, since the failure rates of storage devices in large-scale systems can vary significantly over time [ 2 , 3 , 4 , 5 ] . In [ 6 ] , it was shown that adapting code parameters to varying disk failure rates can improve storage efficiency. However, subsequent work [ 7 ] demonstrated that such adaptations may incur significant I/O overhead and adversely affect overall cluster performance. Motivated by the need to adapt code parameters to varying disk failure rates while maintaining low I/O overhead, Maturana and Rashmi introduced the convertible codes framework and initiated the theoretical study of code conversions in distributed storage systems [ 8 ] . An (n^{I},k^{I};n^{F},k^{F}) convertible code consists of an initial [n^{I}=k^{I}+r^{I},\,k^{I}] code \mathcal{C}^{I} and a final [n^{F}=k^{F}+r^{F},\,k^{F}] code \mathcal{C}^{F} . Given M\triangleq\mathrm{lcm}(k^{I},k^{F}) , a set of \lambda^{I}\triangleq M/k^{I} codewords from \mathcal{C}^{I} are transformed into \lambda^{F}\triangleq M/k^{F} codewords in \mathcal{C}^{F} to represent the same batch of data through a conversion procedure. The efficiency of such conversions can be measured in terms of the following two metrics: (a) Access cost [ 8 ] — the total number of disks accessed during the conversion. (b) Bandwidth cost [ 9 ] — the total number of symbols transferred across the network during the conversion. Due to the widespread applications of maximum distance separable (MDS) codes in modern storage systems, most existing works in the literature focus on the scenario where both the initial and final codes are linear MDS codes. The study of code conversions among MDS codes typically considers two regimes: the merge regime and the split regime . In the merge regime, where \lambda=\lambda^{I} initial codewords are merged into a single final codeword, [ 8 ] derives the following tight lower bound on the access cost: C_{\text{access}}=\begin{cases}(\lambda+1)r^{F},&\text{if }r^{F}\leq\min\{r^{I},k^{I}\},\\ \lambda k^{I}+r^{F},&\text{otherwise}.\end{cases} Note that the default conversion scheme, which accesses k^{I} disks to read the information symbols of each initial codeword and writes new parity symbols of the final code to r^{F} disks, incurs an access cost of \lambda k^{I}+r^{F} . Therefore, according to the bound above, the most interesting case arises when r^{F}\leq\min\{r^{I},k^{I}\} . In [ 8 ] , Maturana and Rashmi present an access-optimal construction in which both the initial and final codes are MDS codes with systematic generator matrices. The parity portions of these generator matrices are carefully designed Vandermonde matrices to ensure access cost optimality. However, this construction requires a field size of q\geq\max\{2^{O(n^{F^{3}})},\,n^{I}-1\} , which becomes impractical when n^{F} is large. Furthermore, Maturana and Rashmi also provide three families of access-optimal MDS convertible code constructions based on superregular Hankel arrays (see Table I ). Although these constructions reduce the field size requirement compared to the aforementioned Vandermonde-based construction, they do not cover all parameter regimes where r^{F}\leq r^{I} . Recently, [ 10 ] reduced the field size requirement for the construction using Vandermonde-matrix-based generator matrices to O((k^{F})^{r^{F}}) in the general case. In [ 11 ] , Kong proposed a construction of access-optimal MDS convertible codes using a polynomial-based framework, in which both the initial and final codes are Generalized Reed–Solomon (GRS) codes. The conversion procedure in [ 11 ] is described as a transformation from \lambda polynomials of degree less than k^{I} into a single polynomial of degree less than \lambda k^{I} . The field size required for this construction is q\geq(\lambda+1)\max\{k^{I},r^{I}\}+1 , under the additional constraint that \max\{k^{I},r^{I}\}\mid(q-1) . Besides the aforementioned works on code conversions among MDS codes in the merge regime, there are also studies that focus on conversions in other regimes and for different classes of codes. For example, in [ 12 ] , the authors provide a construction of MDS convertible codes along with a matching lower bound on the access cost for the split regime, where k^{I}=\lambda k^{F} and each initial codeword is split into \lambda=\lambda^{F} final codewords. Moreover, they derive lower bounds on the access cost for general parameters \{n^{I},k^{I},n^{F},k^{F}\} and present corresponding MDS convertible code constructions that achieve them. Code conversions among locally recoverable codes are explored in [