Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.24573 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910222825553920 |
|---|---|
| author | Martínez-Peñas, Umberto Lalitha, V. |
| author_facet | Martínez-Peñas, Umberto Lalitha, V. |
| contents | In this work, we introduce maximally recoverable codes with locality and availability. We consider locally repairable codes (LRCs) where certain subsets of $ t $ symbols belong each to $ N $ local repair sets, which are pairwise disjoint after removing the $ t $ symbols, and which are of size $ r+δ-1 $ and can correct $ δ-1 $ erasures locally. Classical LRCs with $ N $ disjoint repair sets and LRCs with $ N $-availability are recovered when setting $ t = 1 $ and $ t=δ-1=1 $, respectively. Allowing $ t > 1 $ enables our codes to reduce the storage overhead for the same locality and availability. In this setting, we define maximally recoverable LRCs (MR-LRCs) as those that can correct any globally correctable erasure pattern given the locality and availability constraints. We then identify a large class of global erasure patterns that can be corrected by such MR-LRCs and prove that they are all the correctable patterns when $ t=1 $. We provide three explicit constructions of LRCs that can correct such erasure patterns (thus MR-LRCs for $ t=1 $), based on MSRD codes, each attaining the smallest finite-field sizes for some parameter regime. Finally, we extend the known lower bound on finite-field sizes from classical MR-LRCs to our setting (for any value of $ t $). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_24573 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maximally recoverable codes with locality and availability Martínez-Peñas, Umberto Lalitha, V. Information Theory In this work, we introduce maximally recoverable codes with locality and availability. We consider locally repairable codes (LRCs) where certain subsets of $ t $ symbols belong each to $ N $ local repair sets, which are pairwise disjoint after removing the $ t $ symbols, and which are of size $ r+δ-1 $ and can correct $ δ-1 $ erasures locally. Classical LRCs with $ N $ disjoint repair sets and LRCs with $ N $-availability are recovered when setting $ t = 1 $ and $ t=δ-1=1 $, respectively. Allowing $ t > 1 $ enables our codes to reduce the storage overhead for the same locality and availability. In this setting, we define maximally recoverable LRCs (MR-LRCs) as those that can correct any globally correctable erasure pattern given the locality and availability constraints. We then identify a large class of global erasure patterns that can be corrected by such MR-LRCs and prove that they are all the correctable patterns when $ t=1 $. We provide three explicit constructions of LRCs that can correct such erasure patterns (thus MR-LRCs for $ t=1 $), based on MSRD codes, each attaining the smallest finite-field sizes for some parameter regime. Finally, we extend the known lower bound on finite-field sizes from classical MR-LRCs to our setting (for any value of $ t $). |
| title | Maximally recoverable codes with locality and availability |
| topic | Information Theory |
| url | https://arxiv.org/abs/2505.24573 |