The MISER Code: An MDS Distributed Storage Code that Minimizes Repair Bandwidth for Systematic Nodes through Interference Alignment

Authors:
  • NSNihar B. Shah
    Nihar B. Shah
  • KRK. V. Rashmi
    K. V. Rashmi
  • PKP. Vijay Kumar
    P. Vijay Kumar
  • KRKannan Ramchandran
    Kannan Ramchandran

Abstract
Regenerating codes are a class of recently developed codes for distributed storage, that like Reed-Solomon codes, permit data recovery from any k of n nodes, but which also have the capability of repairing a failed node by connecting to any d nodes and downloading an amount of data, termed the repair bandwidth, that is on average, significantly less than the size of the data file. The main result of the paper is the explicit construction of a systematic MDS code for d = n-1 >= 2k-1 termed the MISER code, that makes use of interference alignment to achieve the cut-set bound on the repair bandwidth for systematic nodes. It is also proven that it is impossible to construct a code with these properties for d < 2k-3. A second major result of the paper is the construction, also explicit, of a minimum-storage regenerating code for d=k+1. To our knowledge, the constructions presented in this paper are the first explicit constructions of regenerating codes that achieve the cut set bound.