Skip to main content
Top
Published in: Applicable Algebra in Engineering, Communication and Computing 4/2023

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

Log in

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

search-config
loading …

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.

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!

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!

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!

Appendix
Available only for authorised users
Literature
2.
go back to reference 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 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
24.
go back to reference Ramkumar, V., Vajha, M., Balaji, S.B., Krishnan, M.N., Sasidharan, B., Kumar, P.V.: Codes for distributed storage (2020) Ramkumar, V., Vajha, M., Balaji, S.B., Krishnan, M.N., Sasidharan, B., Kumar, P.V.: Codes for distributed storage (2020)
26.
30.
go back to reference 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 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
32.
39.
go back to reference 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 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
Metadata
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

Other articles of this Issue 4/2023

Applicable Algebra in Engineering, Communication and Computing 4/2023 Go to the issue

Premium Partner