Locally repairable codes with the optimum average information locality
Mostafa Shahabinejad, Majid Khabbazian, Masoud Ardakani · 2017
Locally repairable codes (LRCs) have been proposed and used in practice as effective coding methods for distributed storage systems (DSSs). In a DSS, information block recovery is a critical task performed in the case of data node permanent failure or temporal unavailability. Temporal node unavailability accounts for 90% of all block recoveries triggered in DSS. Since parity blocks are not needed to be recovered during a temporal node unavailability, special attention should be given to reconstruction of information blocks when trying to minimize the average bandwidth needed for block recovery. Motivated by this, in this work, we study the average locality ofinformation blocks. We obtain a lower bound on the average locality of information blocks of LRCs and design LRCs that achieve the bound. In addition to obtaining the optimal average locality for the information blocks, our codes achieve the optimal maximum locality for all the information blocks as well as some parity blocks (in some cases all the parity blocks).