2025/05/30 by Martínez-Peñas, Umberto, Lalitha, V. · 1 citation
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2505.24573
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 provide three explicit constructions, 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.