Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

On the Existence of Optimal Exact-Repair MDS Codes for Distributed Storage

Changho Suh and Kannan Ramchandran

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2010-46
April 26, 2010

http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-46.pdf

The high repair cost of (n,k) Maximum Distance Separable (MDS) erasure codes has recently motivated a new class of codes, called Regenerating Codes, that optimally trade off storage cost for repair bandwidth. In this paper, we address bandwidth-optimal (n,k,d) Exact-Repair MDS codes, which allow for any failed node to be repaired exactly with access to arbitrary d survivor nodes, where d lies between k and n-1. We show the existence of Exact-Repair MDS codes that achieve minimum repair bandwidth (matching the cutset lower bound) for arbitrary admissible (n,k,d). Our approach is based on interference alignment techniques and uses vector linear codes which allow to split symbols into arbitrarily small subsymbols.


BibTeX citation:

@techreport{Suh:EECS-2010-46,
    Author = {Suh, Changho and Ramchandran, Kannan},
    Title = {On the Existence of Optimal Exact-Repair MDS Codes for Distributed Storage},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2010},
    Month = {Apr},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-46.html},
    Number = {UCB/EECS-2010-46},
    Abstract = {The high repair cost of (n,k) Maximum Distance Separable (MDS) erasure codes has recently motivated a new class of codes, called Regenerating Codes, that optimally trade off storage cost for repair bandwidth. In this paper, we address bandwidth-optimal (n,k,d) Exact-Repair MDS codes, which allow for any failed node to be repaired exactly with access to arbitrary d survivor nodes, where d lies between k and n-1. We show the existence of Exact-Repair MDS codes that achieve minimum repair bandwidth (matching the cutset lower bound) for arbitrary admissible (n,k,d). Our approach is based on interference alignment techniques and uses vector linear codes which allow to split symbols into arbitrarily small subsymbols.}
}

EndNote citation:

%0 Report
%A Suh, Changho
%A Ramchandran, Kannan
%T On the Existence of Optimal Exact-Repair MDS Codes for Distributed Storage
%I EECS Department, University of California, Berkeley
%D 2010
%8 April 26
%@ UCB/EECS-2010-46
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-46.html
%F Suh:EECS-2010-46