Cascade Codes for Distributed Storage Systems

Mehran Elyasi, Soheil Mohajer

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

A novel coding scheme for exact repair-regenerating codes is presented in this paper. The codes proposed in this work can trade between the repair bandwidth of nodes (number of downloaded symbols from each surviving node in a repair process) and the required storage overhead of the system. These codes work for general system parameters $(n,k,d)$ , which are the total number of nodes, the number of nodes suffice for data recovery, and the number of helper nodes in a repair process, respectively. The proposed construction offers a unified scheme to develop exact-repair regenerating codes for the entire trade-off, including the MBR and MSR points. We conjecture that the new storage-vs.-bandwidth trade-off achieved by the proposed codes is optimum. Some other key features of this code include: the construction is linear; the required field size is only $\Theta (n)$ ; and the code parameters and in particular sub-packetization level is at most $(d-k+1)^{k}$ ; which is independent of the number of the parity nodes. Moreover, the proposed repair mechanism is helper-independent, that is the data sent from each helper only depends on the identity of the helper and failed nodes, but independent of the identity of other helper nodes participating in the repair process.

Original languageEnglish (US)
Article number9238032
Pages (from-to)7490-7527
Number of pages38
JournalIEEE Transactions on Information Theory
Volume66
Issue number12
DOIs
StatePublished - Dec 2020
Externally publishedYes

Bibliographical note

Funding Information:
Manuscript received January 3, 2019; revised September 16, 2019; accepted November 24, 2019. Date of publication October 23, 2020; date of current version November 20, 2020. This work was supported in part by the National Science Foundation under Grant CCF-1617884. This article was presented in part at the 2018 IEEE International Symposium on Information Theory (ISIT). (Corresponding author: Mehran Elyasi.) The authors are with the Department of Electrical and Computer Engineering, University of Minnesota, Twin Cities, MN 55455 USA (e-mail: melyasi@umn.edu; soheil@umn.edu). Communicated by B. Dey, Associate Editor for Coding Techniques.

Publisher Copyright:
© 1963-2012 IEEE.

Keywords

  • Distributed storage codes
  • cascade codes
  • determinant codes
  • erasure codes
  • regenerating codes

Fingerprint

Dive into the research topics of 'Cascade Codes for Distributed Storage Systems'. Together they form a unique fingerprint.

Cite this