Lower Bounds on the Sub-Packetization Level of MSR Codes and Characterizing Optimal-Access MSR Codes Achieving the Bound
S. B. Balaji, Myna Vajha, P. Vijay Kumar · IEEE Transactions on Information Theory · 2022
We present two lower bounds on sub-packetization level$\alpha $of MSR codes with parameters$(n, k, d=n-1, \alpha )$where$n$is the block length,$d$is the number of helper nodes contacted during single-node repair,$\alpha $the sub-packetization level and$k\alpha $the scalar dimension. The first bound we present is for any MSR code and is given by$\alpha \ge e^{\frac {(k-1)(r-1)}{2r^{2}}}$. The second bound we present is for the case of optimal-access MSR codes and the bound is given by$\alpha \ge \min \left\{{ r^{\frac {n-1}{r}}, r^{k-1} }\right\}$. There exist optimal-access MSR constructions that achieve the second sub-packetization level bound with an equality making this bound tight. We also prove that for an optimal-access MSR code to have optimal sub-packetization level under the constraint that the$\beta $scalar symbol indices we access from a given helper node is dependent only on the index of the failed node, it is necessary that the support of the parity-check matrix be the same as the support structure of the existing MSR constructions in literature such as the Clay code.