Top

Applicable Algebra in Engineering, Communication and Computing

Published in:

01-10-2021 | Original Paper

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

Authors: Iwan Duursma, Hsin-Po Wang

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 4/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The article addresses the challenge of efficient cloud storage by introducing the Atrahasis code, a generalization of the product-matrix construction for minimum storage regenerating (MSR) codes. Utilizing multilinear algebra, the Atrahasis code achieves a lower sub-packetization level, enhancing the efficiency and reliability of distributed storage systems. The paper also provides a detailed construction of the Atrahasis code and compares its performance with existing codes, highlighting its advantages in terms of reduced storage requirements and improved data recovery capabilities.

AI Generated

This summary of the content was generated with the help of AI.

previous article Several classes of p-ary linear codes with few weights

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Available only for authorised users

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

Title: Multilinear algebra for minimum storage regenerating codes: a generalization of the product-matrix construction
Authors: Iwan Duursma
Hsin-Po Wang
Publication date: 01-10-2021
Publisher: Springer Berlin Heidelberg
Published in: Applicable Algebra in Engineering, Communication and Computing / Issue 4/2023
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-021-00526-3

Using double Weil sums in finding the c-boomerang connectivity table for monomial functions on finite fields

Original Paper

AG codes from -rational points of the GK maximal curve

Open Access
Original Paper

Special LCD codes from products of graphs

Original Paper

Rational homotopy theory methods in graph theory

Original Paper

A new algorithm for equivalence of cyclic codes and its applications

Original Paper

Deterministic factoring with oracles

Original Paper

Springer Professional

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

Abstract

Abstract

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 4/2023

Using double Weil sums in finding the c-boomerang connectivity table for monomial functions on finite fields

AG codes from -rational points of the GK maximal curve

Special LCD codes from products of graphs

Rational homotopy theory methods in graph theory

A new algorithm for equivalence of cyclic codes and its applications

Deterministic factoring with oracles

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Using double Weil sums in finding the c-boomerang connectivity table for monomial functions on finite fields

AG codes from -rational points of the GK maximal curve

Special LCD codes from products of graphs

Rational homotopy theory methods in graph theory

A new algorithm for equivalence of cyclic codes and its applications

Deterministic factoring with oracles