Zigzag Codes Revisited: From Optimal Rebuilding to Small Skip Cost and Small Fields
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918149656412160 |
|---|---|
| author | Zhang, Wenqin Kiah, Han Mao Dau, Son Hoang |
| author_facet | Zhang, Wenqin Kiah, Han Mao Dau, Son Hoang |
| contents | We revisit zigzag array codes, a family of MDS codes known for achieving optimal access and optimal rebuilding ratio in single-node repair. In this work, we endow zigzag codes with two new properties: small field size and low skip cost. First, we prove that when the row-indexing group is $\mathcal{G} = \mathbb{Z}_2^m$ and the field has characteristic two, explicit coefficients over any field with $|\mathcal{F}|\ge N$ guarantee the MDS property, thereby decoupling the dependence among $p$, $k$, and $M$. Second, we introduce an ordering-and-subgroup framework that yields repair-by-transfer schemes with bounded skip cost and low repair-fragmentation ratio (RFR), while preserving optimal access and optimal rebuilding ratio. Our explicit constructions include families with zero skip cost whose rates approach $2/3$, and families with bounded skip cost whose rates approach $3/4$ and $4/5$. These rates are comparable to those of MDS array codes widely deployed in practice. Together, these results demonstrate that zigzag codes can be made both more flexible in theory and more practical for modern distributed storage systems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_23090 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Zigzag Codes Revisited: From Optimal Rebuilding to Small Skip Cost and Small Fields Zhang, Wenqin Kiah, Han Mao Dau, Son Hoang Information Theory We revisit zigzag array codes, a family of MDS codes known for achieving optimal access and optimal rebuilding ratio in single-node repair. In this work, we endow zigzag codes with two new properties: small field size and low skip cost. First, we prove that when the row-indexing group is $\mathcal{G} = \mathbb{Z}_2^m$ and the field has characteristic two, explicit coefficients over any field with $|\mathcal{F}|\ge N$ guarantee the MDS property, thereby decoupling the dependence among $p$, $k$, and $M$. Second, we introduce an ordering-and-subgroup framework that yields repair-by-transfer schemes with bounded skip cost and low repair-fragmentation ratio (RFR), while preserving optimal access and optimal rebuilding ratio. Our explicit constructions include families with zero skip cost whose rates approach $2/3$, and families with bounded skip cost whose rates approach $3/4$ and $4/5$. These rates are comparable to those of MDS array codes widely deployed in practice. Together, these results demonstrate that zigzag codes can be made both more flexible in theory and more practical for modern distributed storage systems. |
| title | Zigzag Codes Revisited: From Optimal Rebuilding to Small Skip Cost and Small Fields |
| topic | Information Theory |
| url | https://arxiv.org/abs/2509.23090 |