Explicit Codes Minimizing Repair Bandwidth for Distributed Storage

Details Explicit Codes Minimizing Repair Bandwidth for Distributed Storage Explicit Codes Minimizing Repair Bandwidth for Distributed Storage

2009-08-20

arxiv.org/abs/0908.2984v2

Computer Science

Information Theory

11 pages, 4 figures v2: corrected typos

Scientific paper

We consider the setting of data storage across n nodes in a distributed manner. A data collector (DC) should be able to reconstruct the entire data by connecting to any k out of the n nodes and downloading all the data stored in them. When a node fails, it has to be regenerated back using the existing nodes. In a recent paper, Wu et al. have obtained an information theoretic lower bound for the repair bandwidth. Also, there has been additional interest in storing data in systematic form as no post processing is required when DC connects to k systematic nodes. Because of their preferred status there is a need to regenerate back any systematic node quickly and exactly. Replacement of a failed node by an exact replica is termed Exact Regeneration.In this paper, we consider the problem of minimizing the repair bandwidth for exact regeneration of the systematic nodes. The file to be stored is of size B and each node can store alpha = B/k units of data. A failed systematic node is regenerated by downloading beta units of data each from d existing nodes. We give a lower bound for the repair bandwidth for exact regeneration of the systematic nodes which matches with the bound given by Wu et al. For d >= 2k-1 we give an explicit code construction which minimizes the repair bandwidth when the existing k-1 systematic nodes participate in the regeneration. We show the existence and construction of codes that achieve the bound for d >= 2k-3. Here we also establish the necessity of interference alignment. We prove that the bound is not achievable for d <= 2k-4 when beta=1. We also give a coding scheme which can be used for any d and k, which is optimal for d >= 2k-1.

Affiliated with

Also associated with

No associations

Rating

Explicit Codes Minimizing Repair Bandwidth for Distributed Storage does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Explicit Codes Minimizing Repair Bandwidth for Distributed Storage, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Explicit Codes Minimizing Repair Bandwidth for Distributed Storage will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-527116