ϵ-MSR Codes: Contacting Fewer Code Blocks for Exact Repair
Venkatesan Guruswami, Satyanarayana V. Lokam, Sai Vikneshwar Mani Jayaraman · IEEE Transactions on Information Theory · 2020
ϵ-Minimum Storage Regenerating (E-MSR) codes form a special class of Maximum Distance Separable (MDS) codes, providing mechanisms for exact regeneration of a single code block in their codewords by downloading slightly suboptimal amount of information from the remaining code blocks. The key advantage of these codes is a significantly lower subpacketization that grows only logarithmically with the code length, while providing optimality in storage and error-correcting capacity. However, existing constructions of ϵ-MSR codes require each remaining code block to be available for the repair of any failed code block. In this paper, we construct ϵ-MSR codes that can repair any failed code block by contacting fewer number of available code blocks. When a code block fails, our repair procedure needs to contact a few compulsory code blocks and is free to choose any subset of available code blocks for the remaining choices. Our construction requires a field size linear in code length and ensures load balancing (in terms of information downloaded) among the contacted code blocks for repairing a failed code block.