Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2509.21036 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917357381746688 |
|---|---|
| author | Zhang, Zihao Li, Guodong Hu, Sihuang |
| author_facet | Zhang, Zihao Li, Guodong Hu, Sihuang |
| contents | Maximum distance separable (MDS) codes are widely used in distributed storage systems as they provide optimal fault tolerance for a given amount of storage overhead. The seminal work of Dimakis~\emph{et al.} first established a lower bound on the repair bandwidth for a single failed node of MDS codes, known as the \emph{cut-set bound}. MDS codes that achieve this bound are called minimum storage regenerating (MSR) codes. Numerous constructions and theoretical analyses of MSR codes reveal that they typically require exponentially large sub-packetization levels, leading to significant disk I/O overhead. To mitigate this issue, many studies explore the trade-offs between the sub-packetization level and repair bandwidth, achieving reduced sub-packetization at the cost of suboptimal repair bandwidth. Despite these advances, the fundamental question of determining the minimum repair bandwidth for a single failure of MDS codes with fixed sub-packetization remains open.
In this paper, we address this challenge for the case of two parity nodes ($n-k=2$) and sub-packetization $\ell=2$. Under these parameters, we establish a correspondence between repair schemes and point sets on the projective line $\mathbb{P}^1$, and then derive a lower bound on repair bandwidth utilizing the sharply 3-transitive action of $\text{PGL}_2(\Fq)$. Furthermore, we extend this lower bound to the repair I/O, and construct two classes of explicit MDS array codes that achieve these bounds, offering practical code designs with provable repair efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_21036 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Repair of $(k+2, k, 2)$ MDS Array Codes Zhang, Zihao Li, Guodong Hu, Sihuang Information Theory Maximum distance separable (MDS) codes are widely used in distributed storage systems as they provide optimal fault tolerance for a given amount of storage overhead. The seminal work of Dimakis~\emph{et al.} first established a lower bound on the repair bandwidth for a single failed node of MDS codes, known as the \emph{cut-set bound}. MDS codes that achieve this bound are called minimum storage regenerating (MSR) codes. Numerous constructions and theoretical analyses of MSR codes reveal that they typically require exponentially large sub-packetization levels, leading to significant disk I/O overhead. To mitigate this issue, many studies explore the trade-offs between the sub-packetization level and repair bandwidth, achieving reduced sub-packetization at the cost of suboptimal repair bandwidth. Despite these advances, the fundamental question of determining the minimum repair bandwidth for a single failure of MDS codes with fixed sub-packetization remains open. In this paper, we address this challenge for the case of two parity nodes ($n-k=2$) and sub-packetization $\ell=2$. Under these parameters, we establish a correspondence between repair schemes and point sets on the projective line $\mathbb{P}^1$, and then derive a lower bound on repair bandwidth utilizing the sharply 3-transitive action of $\text{PGL}_2(\Fq)$. Furthermore, we extend this lower bound to the repair I/O, and construct two classes of explicit MDS array codes that achieve these bounds, offering practical code designs with provable repair efficiency. |
| title | Optimal Repair of $(k+2, k, 2)$ MDS Array Codes |
| topic | Information Theory |
| url | https://arxiv.org/abs/2509.21036 |