Maximally Recoverable Codes With Locality and Availability
Umberto Martínez-Peñas, V. Lalitha · IEEE Transactions on Information Theory · 2026
In this work, we introduce maximally recoverable codes with locality and availability. We consider locally repairable codes (LRCs) where certain subsets oftsymbols belong each toNlocal repair sets, which are pairwise disjoint after removing thetsymbols, and which are of sizer+ δ − 1 and can correct δ −1 erasures locally. Classical LRCs withNdisjoint repair sets and LRCs withN-availability are recovered when settingt= 1 andt= δ − 1 = 1, respectively. Allowingt> 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 whent= 1. We provide three explicit constructions of LRCs that can correct such erasure patterns (thus MR-LRCs fort= 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 oft).