Advanced Search
Article Contents
Article Contents
Early Access

Early Access articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Early Access publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Early Access articles via the “Early Access” tab for the selected journal.

Clay and Product-Matrix MSR Codes with Locality

• *Corresponding author: Minhan Gao

L. Holzbaur's work was supported by the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG) under Grant No. WA3907/1-1

• Regenerating codes and codes with locality address the efficiency of the node repair problem. While regeneration reduces the repair bandwidth, locality reduces the number of nodes required for the repair of a small number of nodes. This work considers the combination of minimum storage regenerating codes, an optimal subclass of regenerating codes, and PMDS codes, a particularly strong type of code with locality. Two new constructions are proposed in this paper. The first construction decreases the subpacketization from $r^n$ to $r^{\frac{\mu n}{r}}$ for all considered parameters of PMDS codes, and the second one achieves a significantly lower subpacketization $n-r-1$ when the global redundancy is $s = 1$.

Mathematics Subject Classification: Primary: 94B05.

 Citation:

• Figure 1.  Example of a $[4,2]$ Clay Code

Figure 2.  The construction of a coupled PMDS code with $\mu = 2, n = 4, r = 2$

Figure 3.  Comparison of total symbol size $S$ for different parameters

Table 1.  Parameters of different PMDS code constructions. The values given for coupled PMDS codes hold if $r|n$. The citations in the column Field Size refer to the field size of the underlying PMDS code used in these constructions. As noted in Remark 3.6, coupled PMDS codes for $r\nmid n$ can be obtained by puncturing longer codes. The construction of PM-PMDS codes is restricted to $s = 1$ and $\frac{k}{n} < \frac{1}{2}$

 Construction Field Size Subpacket. $\ell$ [9,Const. C] max$\{(d+1-n+r)n,\mu+1\}^{n-r}$ $r^n$ [9,Const. D] $n(d+1-n+r)(n\mu)^{s(r+1)-1}$ $r^n$ Coupled PMDS $\mu^{n-r}$ [12] $r^{\frac{\mu n}{r}}$ PM-PMDS $n+1$ [13] $n-r-1$
•  [1] M. Blaum, J. L. Hafner and S. Hetzler, Partial-MDS codes and their application to RAID type of architectures, IEEE Trans. Inform. Theory, 59 (2013), 4510-4519.  doi: 10.1109/TIT.2013.2252395. [2] M. Blaum, J. S. Plank, M. Schwartz and E. Yaakobi, Construction of partial MDS and sector-disk codes with two global parity symbols, IEEE Trans. Inform. Theory, 62 (2016), 2673-2681.  doi: 10.1109/TIT.2016.2536720. [3] V. R. Cadambe, S. A. Jafar, H. Maleki, K. Ramchandran and C. Suh, Asymptotic interference alignment for optimal repair of MDS codes in distributed storage, IEEE Trans. Inform. Theory, 59 (2013), 2974-2987.  doi: 10.1109/TIT.2013.2237752. [4] A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright and K. Ramchandran, Network coding for distributed storage systems, IEEE Trans. Inform. Theory, 56 (2010), 4539-4551. [5] R. Gabrys, E. Yaakobi, M. Blaum and P. H. Siegel, Constructions of partial MDS codes over small fields, IEEE Trans. Inform. Theory, 65 (2019), 3692-3701.  doi: 10.1109/TIT.2018.2890201. [6] D. Gligoroski, K. Kralevska, R. E. Jensen and P. Simonsen, Repair duality with locally repairable and locally regenerating codes, 2017 IEEE 15th Intl Conf on Dependable, Autonomic and Secure Computing, 15th Intl Conf on Pervasive Intelligence and Computing, 3rd Intl Conf on Big Data Intelligence and Computing and Cyber Science and Technology Congress (DASC/PiCom/DataCom/CyberSciTech), IEEE, (2017), 979-984. [7] P. Gopalan, C. Huang, H. Simitci and S. Yekhanin, On the locality of codeword symbols, IEEE Trans. Inform. Theory, 58 (2012), 6925-6934.  doi: 10.1109/TIT.2012.2208937. [8] H. D. L. Hollmann, On the minimum storage overhead of distributed storage codes with a given repair locality, IEEE Inter. Symposium on Information Theory, IEEE, (2014), 1041-1045. [9] L. Holzbaur, S. Puchinger, E. Yaakobi and A. Wachter-Zeh, Partial MDS codes with local regeneration, IEEE Trans. Inform. Theory, IEEE, 67 (2021), 6425-6441. doi: 10.1109/tit.2021.3091455. [10] G. M. Kamath, N. Prakash, V. Lalitha and P. V. Kumar, Codes with local regeneration and erasure correction, IEEE Trans. Inform. Theory, 60 (2014), 4637-4660.  doi: 10.1109/TIT.2014.2329872. [11] M. N. Krishnan and P. V. Kumar, Codes with combined locality and regeneration having optimal rate, $d_{\rm{min}}$ and linear field size, IEEE Inter. Symposium on Information Theory, IEEE, (2018), 1196-1200. [12] U. Martínez-Peñas and F. R. Kschischang, Universal and dynamic locally repairable codes with maximal recoverability via sum-rank codes, IEEE Trans. Inform. Theory, 65 (2019), 7790-7805.  doi: 10.1109/TIT.2019.2924888. [13] K. V. Rashmi, N. B. Shah and P. V. Kumar, Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction, IEEE Trans. Inform. Theory, 57 (2011), 5227-5239.  doi: 10.1109/TIT.2011.2159049. [14] A. S. Rawat, O. O. Koyluoglu, N. Silberstein and S. Vishwanath, Optimal locally repairable and secure codes for distributed storage systems, IEEE Trans. Inform. Theory, 60 (2014), 5228-5244.  doi: 10.1109/TIT.2014.2319271. [15] M. Vajha, V. Ramkumar, B. Puranik, G. Kini, E. Lobo, B. Sasidharan, P. V. Kumar, A. Barg, M. Ye, S. Narayanamurthy, S. Hussain and S. Nandi, Clay codes: Moulding MDS codes to yield and MSR code, 16th USENIX Conference on File and Storage Technologies (FAST 18), Oakland, CA, (2018), 139-154. [16] M. Ye and A. Barg, Explicit consctrution of high-rate MDS array codes with optimal repair bandwidth, IEEE Trans. Inform. Theory, 63 (2017), 2001-2014.  doi: 10.1109/TIT.2017.2661313.

Figures(3)

Tables(1)

Article Metrics

HTML views(214) PDF downloads(81) Cited by(0)

Other Articles By Authors

• on this site
• on Google Scholar

Catalog

/

DownLoad:  Full-Size Img  PowerPoint