Computer Science – Information Theory
Scientific paper
2010-05-10
Computer Science
Information Theory
38 pages, 12 figures, submitted to the IEEE Transactions on Information Theory;v3 - The title has been modified to better refl
Scientific paper
Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any arbitrary k of n nodes. However regenerating codes possess in addition, the ability to repair a failed node by connecting to any arbitrary d nodes and downloading an amount of data that is typically far less than the size of the data file. This amount of download is termed the repair bandwidth. Minimum storage regenerating (MSR) codes are a subclass of regenerating codes that require the least amount of network storage; every such code is a maximum distance separable (MDS) code. Further, when a replacement node stores data identical to that in the failed node, the repair is termed as exact. The four principal results of the paper are (a) the explicit construction of a class of MDS codes for d = n-1 >= 2k-1 termed the MISER code, that achieves the cut-set bound on the repair bandwidth for the exact-repair of systematic nodes, (b) proof of the necessity of interference alignment in exact-repair MSR codes, (c) a proof showing the impossibility of constructing linear, exact-repair MSR codes for d < 2k-3 in the absence of symbol extension, and (d) the construction, also explicit, of MSR codes for d = k+1. Interference alignment (IA) is a theme that runs throughout the paper: the MISER code is built on the principles of IA and IA is also a crucial component to the non-existence proof for d < 2k-3. To the best of our knowledge, the constructions presented in this paper are the first, explicit constructions of regenerating codes that achieve the cut-set bound.
Kumar Vijay P.
Ramchandran Kannan
Rashmi K. V.
Shah Nihar B.
No associations
LandOfFree
Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions 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 Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-629652