2019/07/21 by Hou, Hanxu, Lee, Patrick P. C., Han, Yunghsiang S.
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1907.08938
An (n,k) maximum distance separable (MDS) code has optimal repair access if the minimum number of symbols accessed from d surviving nodes is achieved, where k+1≤ d≤ n-1. Existing results show that the sub-packetization α of an (n,k,d) high code rate (i.e., k/n>0.5) MDS code with optimal repair access is at least (d-k+1)\lceil(n)/(d-k+1)\rceil. In this paper, we propose a class of multi-layer transformed MDS codes such that the sub-packetization is (d-k+1)\lceil(n)/((d-k+1)η)\rceil, where η=\lfloor(n-k-1)/(d-k)\rfloor, and the repair access is optimal for any single node. We show that the sub-packetization of the proposed multi-layer transformed MDS codes is strictly less than the existing known lower bound when η=\lfloor(n-k-1)/(d-k)\rfloor>1, achieving by restricting the choice of d specific helper nodes in repairing a failed node. We further propose multi-layer transformed EVENODD codes that have optimal repair access for any single node and lower sub-packetization than the existing binary MDS array codes with optimal repair access for any single node. With our multi-layer transformation, we can design new MDS codes that have the properties of low computational complexity, optimal repair access for any single node, and relatively small sub-packetization, all of which are critical for maintaining the reliability of distributed storage systems.