\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Clay and Product-Matrix MSR Codes with Locality

  • *Corresponding author: Minhan Gao

    *Corresponding author: Minhan Gao 

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

Abstract / Introduction Full Text(HTML) Figure(3) / Table(1) Related Papers Cited by
  • 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:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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 $
     | Show Table
    DownLoad: CSV
  • [1] M. BlaumJ. 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. BlaumJ. S. PlankM. 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. CadambeS. A. JafarH. MalekiK. 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. DimakisP. B. GodfreyY. WuM. J. Wainwright and K. Ramchandran, Network coding for distributed storage systems, IEEE Trans. Inform. Theory, 56 (2010), 4539-4551. 
    [5] R. GabrysE. YaakobiM. 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. GopalanC. HuangH. 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. KamathN. PrakashV. 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. RashmiN. 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. RawatO. O. KoyluogluN. 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)

SHARE

Article Metrics

HTML views(3007) PDF downloads(770) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return