nach oben

Applicable Algebra in Engineering, Communication and Computing

Erschienen in:

01.10.2021 | Original Paper

Multilinear algebra for minimum storage regenerating codes: a generalization of the product-matrix construction

verfasst von: Iwan Duursma, Hsin-Po Wang

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 4/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

An \((n, k, d, \alpha )\)-MSR (minimum storage regeneration) code is a set of n nodes used to store a file. For a file of total size \(k\alpha\), each node stores \(\alpha\) symbols, any k nodes determine the file, and any d nodes can repair any other node by each sending out \(\alpha /(d-k+1)\) symbols. In this work, we express the product-matrix construction of \(\bigl (n, k, 2(k-1), k-1\bigr )\)-MSR codes in terms of symmetric algebras. We then generalize the product-matrix construction to \(\bigl (n, k, \frac{(k-1)t}{t-1}, \left( {\begin{array}{c}k-1\\ t-1\end{array}}\right) \bigr )\)-MSR codes for general \(t\geqslant 2\), while the \(t=2\) case recovers the product-matrix construction. Our codes’ sub-packetization level—\(\alpha\)—is small and independent of n. It is less than \(L^{2.8(d-k+1)}\), where L is Alrabiah–Guruswami’s lower bound on \(\alpha\). Furthermore, it is less than other MSR codes’ \(\alpha\) for a set of practical parameters. Finally, we discuss how our code repairs multiple failures at once.

Vorheriger Artikel Several classes of p-ary linear codes with few weights

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Alon, N.: Combinatorial Nullstellensatz. Combin. Probab. Comput. 8(1–2), 7–29 (1999)MathSciNetCrossRefMATH

Alrabiah, O., Guruswami, V.: An exponential lower bound on the sub-packetization of msr codes. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pp. 979–985. Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/3313276.3316387

Balaji, S.B., Kumar, P.V.: A tight lower bound on the sub- packetization level of optimal-access msr and mds codes. In: 2018 IEEE International Symposium on Information Theory (ISIT), pp. 2381–2385 (2018). https://doi.org/10.1109/ISIT.2018.8437486

Cadambe, V.R., Jafar, S.A., Maleki, H., Ramchandran, K., Suh, C.: Asymptotic interference alignment for optimal repair of MDS codes in distributed storage. IEEE Trans. Inf. Theory 59(5), 2974–2987 (2013). https://doi.org/10.1109/TIT.2013.2237752MathSciNetCrossRefMATH

Chen, Z., Ye, M., Barg, A.: Enabling optimal access and error correction for the repair of reed-solomon codes. IEEE Trans. Inf. Theory 66(12), 7439–7456 (2020). https://doi.org/10.1109/TIT.2020.3017666MathSciNetCrossRefMATH

Dau, H., Duursma, I.M., Kiah, H.M., Milenkovic, O.: Repairing reed-solomon codes with multiple erasures. IEEE Trans. Inf. Theory 64(10), 6567–6582 (2018). https://doi.org/10.1109/TIT.2018.2827942MathSciNetCrossRefMATH

Dimakis, A.G., Godfrey, P.B., Wu, Y., Wainwright, M.J., Ramchandran, K.: Network coding for distributed storage systems. IEEE Trans. Inf. Theory 56(9), 4539–4551 (2010). https://doi.org/10.1109/TIT.2010.2054295CrossRefMATH

Duursma, I., Dau, H.: Low bandwidth repair of the rs(10,4) reed-solomon code. In: 2017 Information Theory and Applications Workshop (ITA), pp. 1–10 (2017). https://doi.org/10.1109/ITA.2017.8023449

Duursma, I., Li, X.: Layered codes through multilinear algebra (2017). https://meetings.siam.org/sess/dsp_talk.cfm?p=88132. Presented at SIAM Conference on Applied Algebraic Geometry

10.

Duursma, I., Li, X.: Johnson graph codes. CoRR abs/1912.10388 (2019). arXiv:1912.10388

11.

Duursma, I.M.: Outer bounds for exact repair codes. CoRR abs/1406.4852 (2014). arXiv:1406.4852

12.

Duursma, I.M.: Shortened regenerating codes. IEEE Trans. Inf. Theory 65(2), 1000–1007 (2019). https://doi.org/10.1109/TIT.2018.2840995MathSciNetCrossRefMATH

13.

Duursma, I.M., Li, X., Wang, H.: Multilinear algebra for distributed storage. CoRR abs/2006.08911 (2020). arXiv:2006.08911

14.

Elyasi, M., Mohajer, S.: Determinant codes with helper-independent repair for single and multiple failures. IEEE Trans. Inf. Theory 65(9), 5469–5483 (2019). https://doi.org/10.1109/TIT.2019.2904294MathSciNetCrossRefMATH

15.

Elyasi, M., Mohajer, S.: Cascade codes for distributed storage systems. IEEE Trans. Inf. Theory 66(12), 7490–7527 (2020). https://doi.org/10.1109/TIT.2020.3033338MathSciNetCrossRefMATH

16.

Elyasi, M., Mohajer, S., Tandon, R.: Linear exact repair rate region of (k + 1, k, k) distributed storage systems: A new approach. In: 2015 IEEE International Symposium on Information Theory (ISIT), pp. 2061–2065 (2015). https://doi.org/10.1109/ISIT.2015.7282818

17.

Goparaju, S., Fazeli, A., Vardy, A.: Minimum storage regenerating codes for all parameters. IEEE Trans. Inf. Theory 63(10), 6318–6328 (2017). https://doi.org/10.1109/TIT.2017.2690662MathSciNetCrossRefMATH

18.

Goparaju, S., Tamo, I., Calderbank, R.: An improved sub-packetization bound for minimum storage regenerating codes. IEEE Trans. Inf. Theory 60(5), 2770–2779 (2014). https://doi.org/10.1109/TIT.2014.2309000MathSciNetCrossRefMATH

19.

Guruswami, V., Lokam, S.V., Mani Jayaraman, S.V.: \(\epsilon\)-msr codes: Contacting fewer code blocks for exact repair. In: 2018 IEEE International Symposium on Information Theory (ISIT), pp. 2371–2375 (2018). https://doi.org/10.1109/ISIT.2018.8437576

20.

Guruswami, V., Wootters, M.: Repairing reed-solomon codes. IEEE Trans. Inf. Theory 63(9), 5684–5698 (2017). https://doi.org/10.1109/TIT.2017.2702660MathSciNetCrossRefMATH

21.

Lee, H., Lee, J.: An outer bound on the storage-bandwidth tradeoff of exact-repair regenerating codes and its asymptotic optimality in high rates. In: 2016 IEEE Information Theory Workshop (ITW), pp. 255–259 (2016). https://doi.org/10.1109/ITW.2016.7606835

22.

Mohajer, S., Tandon, R.: New bounds on the (n, k, d) storage systems with exact repair. In: 2015 IEEE International Symposium on Information Theory (ISIT), pp. 2056–2060 (2015). https://doi.org/10.1109/ISIT.2015.7282817

23.

Prakash, N., Krishnan, M.N.: The storage-repair-bandwidth trade-off of exact repair linear regenerating codes for the case d = k = n - 1. In: 2015 IEEE International Symposium on Information Theory (ISIT), pp. 859–863 (2015). https://doi.org/10.1109/ISIT.2015.7282577

24.

Ramkumar, V., Vajha, M., Balaji, S.B., Krishnan, M.N., Sasidharan, B., Kumar, P.V.: Codes for distributed storage (2020)

25.

Rashmi, K.V., Shah, N.B., Kumar, P.V.: Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction. IEEE Trans. Inf. Theory 57(8), 5227–5239 (2011). https://doi.org/10.1109/TIT.2011.2159049MathSciNetCrossRefMATH

26.

Rashmi, K.V., Shah, N.B., Kumar, P.V., Ramchandran, K.: Explicit construction of optimal exact regenerating codes for distributed storage. In: 2009 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1243–1249 (2009). https://doi.org/10.1109/ALLERTON.2009.5394538

27.

Rawat, A.S., Koyluoglu, O.O., Vishwanath, S.: Progress on high-rate msr codes: Enabling arbitrary number of helper nodes. In: 2016 Information Theory and Applications Workshop (ITA), pp. 1–6 (2016). https://doi.org/10.1109/ITA.2016.7888191

28.

Rawat, A.S., Tamo, I., Guruswami, V., Efremenko, K.: \(\epsilon\)-msr codes with small sub-packetization. In: 2017 IEEE International Symposium on Information Theory (ISIT), pp. 2043–2047 (2017). https://doi.org/10.1109/ISIT.2017.8006888

29.

Sasidharan, B., Agarwal, G.K., Kumar, P.V.: A high-rate msr code with polynomial sub-packetization level. In: 2015 IEEE International Symposium on Information Theory (ISIT), pp. 2051–2055 (2015). https://doi.org/10.1109/ISIT.2015.7282816

30.

Sasidharan, B., Prakash, N., Krishnan, M.N., Vajha, M., Senthoor, K., Kumar, P.V.: Outer bounds on the storage-repair bandwidth trade-off of exact-repair regenerating codes. Int. J. Inf. Coding Theory 3(4), 255–298 (2016)MathSciNetMATH

31.

Sasidharan, B., Senthoor, K., Kumar, P.V.: An improved outer bound on the storage-repair-bandwidth tradeoff of exact-repair regenerating codes. In: 2014 IEEE International Symposium on Information Theory, pp. 2430–2434 (2014). https://doi.org/10.1109/ISIT.2014.6875270

32.

Senthoor, K., Sasidharan, B., Kumar, P.V.: Improved layered regenerating codes characterizing the exact-repair storage-repair bandwidth tradeoff for certain parameter sets. In: 2015 IEEE Information Theory Workshop (ITW), pp. 1–5 (2015). https://doi.org/10.1109/ITW.2015.7133121

33.

Shum, K.W., Hu, Y.: Cooperative regenerating codes. IEEE Trans. Inf. Theory 59(11), 7229–7258 (2013). https://doi.org/10.1109/TIT.2013.2274265MathSciNetCrossRefMATH

34.

Tamo, I., Ye, M., Barg, A.: The repair problem for reed-solomon codes: Optimal repair of single and multiple erasures with almost optimal node size. IEEE Trans. Inf. Theory 65(5), 2673–2695 (2019). https://doi.org/10.1109/TIT.2018.2884075MathSciNetCrossRefMATH

35.

Tian, C.: Characterizing the rate region of the (4,3,3) exact-repair regenerating codes. IEEE J. Select. Areas Commun. 32(5), 967–975 (2014). https://doi.org/10.1109/JSAC.2014.140516CrossRef

36.

Tian, C.: A note on the rate region of exact-repair regenerating codes. CoRR abs/1503.00011 (2015). arXiv:1503.00011

37.

Tian, C.: Solutions of computed information-theoretic limits (2016). http://web.eecs.utk.edu/~ctian1/SCITL.html

38.

Tian, C., Sasidharan, B., Aggarwal, V., Vaishampayan, V.A., Kumar, P.V.: Layered exact-repair regenerating codes via embedded error correction and block designs. IEEE Trans. Inf. Theory 61(4), 1933–1947 (2015). https://doi.org/10.1109/TIT.2015.2408595MathSciNetCrossRefMATH

39.

Vajha, M., Ramkumar, V., Puranik, B., Kini, G., Lobo, E., Sasidharan, B., Kumar, P.V., Barg, A., Ye, M., Narayanamurthy, S., Hussain, S., Nandi, S.: Clay codes: Moulding MDS codes to yield an MSR code. In: 16th USENIX Conference on File and Storage Technologies (FAST 18), pp. 139–154. USENIX Association, Oakland, CA (2018). https://www.usenix.org/conference/fast18/presentation/vajha

40.

Wang, Z., Tamo, I., Bruck, J.: Explicit minimum storage regenerating codes. IEEE Trans. Inf. Theory 62(8), 4466–4480 (2016). https://doi.org/10.1109/TIT.2016.2553675MathSciNetCrossRefMATH

41.

Wu, Y., Dimakis, A.G.: Reducing repair traffic for erasure coding-based storage via interference alignment. In: 2009 IEEE International Symposium on Information Theory, pp. 2276–2280 (2009). https://doi.org/10.1109/ISIT.2009.5205898

42.

Ye, M., Barg, A.: Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization. IEEE Trans. Inf. Theory 63(10), 6307–6317 (2017). https://doi.org/10.1109/TIT.2017.2730863MathSciNetCrossRefMATH

43.

Ye, M., Barg, A.: Cooperative repair: constructions of optimal MDS codes for all admissible parameters. IEEE Trans. Inf. Theory 65(3), 1639–1656 (2019). https://doi.org/10.1109/TIT.2018.2856206MathSciNetCrossRefMATH

Titel: Multilinear algebra for minimum storage regenerating codes: a generalization of the product-matrix construction
verfasst von: Iwan Duursma
Hsin-Po Wang
Publikationsdatum: 01.10.2021
Verlag: Springer Berlin Heidelberg
Erschienen in: Applicable Algebra in Engineering, Communication and Computing / Ausgabe 4/2023
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-021-00526-3

A new algorithm for equivalence of cyclic codes and its applications

Original Paper

Several classes of p-ary linear codes with few weights

Original Paper

Integration in finite terms: dilogarithmic integrals

Original Paper

Special LCD codes from products of graphs

Original Paper

AG codes from -rational points of the GK maximal curve

Open Access
Original Paper

Rational homotopy theory methods in graph theory

Original Paper

Springer Professional

Multilinear algebra for minimum storage regenerating codes: a generalization of the product-matrix construction

Abstract

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2023

A new algorithm for equivalence of cyclic codes and its applications

Several classes of p-ary linear codes with few weights

Integration in finite terms: dilogarithmic integrals

Special LCD codes from products of graphs

AG codes from -rational points of the GK maximal curve

Rational homotopy theory methods in graph theory

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

A new algorithm for equivalence of cyclic codes and its applications

Several classes of p-ary linear codes with few weights

Integration in finite terms: dilogarithmic integrals

Special LCD codes from products of graphs

AG codes from -rational points of the GK maximal curve

Rational homotopy theory methods in graph theory