On MDS Convertible Codes in the Merge Regime
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918119252951040 |
|---|---|
| author | Ramkumar, Vinayak Kong, Xiangliang Sai, G. Yeswanth Vajha, Myna Krishnan, M. Nikhil |
| author_facet | Ramkumar, Vinayak Kong, Xiangliang Sai, G. Yeswanth Vajha, Myna Krishnan, M. Nikhil |
| contents | 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 \emph{code conversions}, motivate the design of \emph{convertible codes}, which enable efficient transformations between codes of different parameters.
In this work, we study the setting in which $λ$ codewords of an initial $[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]$ MDS code. We begin by presenting three constructions that achieve optimal \emph{access cost}, defined as the total number of disks accessed during the conversion process. The first two constructions apply when $λ\leq r^I$ and impose specific divisibility conditions on $r^I$ and the field size $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 \emph{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_06219 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On MDS Convertible Codes in the Merge Regime Ramkumar, Vinayak Kong, Xiangliang Sai, G. Yeswanth Vajha, Myna Krishnan, M. Nikhil Information Theory 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 \emph{code conversions}, motivate the design of \emph{convertible codes}, which enable efficient transformations between codes of different parameters. In this work, we study the setting in which $λ$ codewords of an initial $[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]$ MDS code. We begin by presenting three constructions that achieve optimal \emph{access cost}, defined as the total number of disks accessed during the conversion process. The first two constructions apply when $λ\leq r^I$ and impose specific divisibility conditions on $r^I$ and the field size $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 \emph{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. |
| title | On MDS Convertible Codes in the Merge Regime |
| topic | Information Theory |
| url | https://arxiv.org/abs/2508.06219 |