Bandwidth Adaptive Error Resilient MBR Exact Repair Regenerating Codes

Kaveh Mahdaviani, Ashish Khisti, Soheil Mohajer

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

Regenerating codes are efficient methods for distributed storage in storage networks, where node failures are common. They guarantee low cost data reconstruction and repair through accessing only a predefined number of arbitrarily chosen storage nodes in the network. In this paper, we consider two simultaneous extensions to the original regenerating codes framework introduced by Dimakis et al.; 1) both data reconstruction and repair are resilient to the presence of a certain number of erroneous nodes in the network and 2) the number of helper nodes in every repair is not fixed, but is a flexible parameter that can be selected during the run-time. We study the fundamental limits of required total repair bandwidth and provide an upper bound for the storage capacity of these codes under these assumptions. We then focus on the minimum repair bandwidth (MBR) case and derive the exact storage capacity by presenting explicit coding schemes with exact repair, which achieve the upper bound of the storage capacity in the considered setup. To this end, we first provide a more natural extension of the well-known product matrix (PM) MBR codes, modified to provide flexibility in choosing the number of helpers in each repair, and simultaneously be robust to erroneous nodes in the network. This is achieved by proving the non-singularity for a family of matrices in large enough finite fields. We next provide another extension of the PM codes, based on a novel repair scheme which enables flexibility in the number of helpers and robustness against erroneous nodes without any extra cost in field size compared with the original PM codes.

Original languageEnglish (US)
Article number8510871
Pages (from-to)2736-2759
Number of pages24
JournalIEEE Transactions on Information Theory
Volume65
Issue number5
DOIs
StatePublished - May 2019

Bibliographical note

Funding Information:
Manuscript received November 6, 2017; revised August 28, 2018; accepted August 29, 2018. Date of publication October 26, 2018; date of current version April 19, 2019. S. Mohajer was supported in part by the National Science Foundation under Grant CCF-1617884. This paper was presented at the 2016 IEEE International Symposium on Information Theory [3]. K. Mahdaviani and A. Khisti are with the ECE Department, University of Toronto, Toronto, ON M5S3G4, Canada (e-mail: kaveh.mahdaviani@ mail.utoronto.ca; akhisti@ece.utoronto.ca). S. Mohajer is with the ECE Department, University of Minnesota, Minneapolis, MN 55455 USA (e-mail: soheil@umn.edu). Communicated by M. Schwartz, Associate Editor for Coding Techniques. Digital Object Identifier 10.1109/TIT.2018.2878223

Keywords

  • Distributed storage
  • MBR codes
  • error resiliency
  • exact repair
  • regenerating codes

Fingerprint Dive into the research topics of 'Bandwidth Adaptive Error Resilient MBR Exact Repair Regenerating Codes'. Together they form a unique fingerprint.

Cite this