Repairing Reed-Solomon Codes With Multiple Erasures

Hoang Dau; Iwan M. Duursma; Han Mao Kiah; Olgica Milenkovic

doi:10.1109/TIT.2018.2827942

Repairing Reed-Solomon Codes With Multiple Erasures

Hoang Dau, Iwan M. Duursma, Han Mao Kiah, Olgica Milenkovic

Research output: Contribution to journal › Article › peer-review

Abstract

Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth. A naive repair approach would require for the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. Their key idea is to recover the erased symbol by collecting a sufficiently large number of its traces, each of which can be constructed from a number of traces of other symbols. We extend the trace collection technique to cope with two and three erasures.

Original language	English (US)
Article number	8340062
Pages (from-to)	6567-6582
Number of pages	16
Journal	IEEE Transactions on Information Theory
Volume	64
Issue number	10
DOIs	https://doi.org/10.1109/TIT.2018.2827942
State	Published - Oct 2018

Keywords

Reed-Solomon codes
distributed storage systems
erasure
repair bandwidth
trace

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Library and Information Sciences

Online availability

10.1109/TIT.2018.2827942

Library availability

Discover UIUC Full Text

Cite this

@article{e8d95bc2cd614a4394bbff273975cd2a,

title = "Repairing Reed-Solomon Codes With Multiple Erasures",

abstract = "Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth. A naive repair approach would require for the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. Their key idea is to recover the erased symbol by collecting a sufficiently large number of its traces, each of which can be constructed from a number of traces of other symbols. We extend the trace collection technique to cope with two and three erasures.",

keywords = "Reed-Solomon codes, distributed storage systems, erasure, repair bandwidth, trace",

author = "Hoang Dau and Duursma, {Iwan M.} and Kiah, {Han Mao} and Olgica Milenkovic",

note = "Funding Information: Manuscript received June 15, 2017; revised February 17, 2018; accepted April 5, 2018. Date of publication April 17, 2018; date of current version September 13, 2018. This work was supported in part by NSF under Grant CCF 1526875, in part by the Center for Science of Information under Grant NSF 0939370, and in part by NSF grant CCF 1619189. H. M. Kiah was supported by the Singapore Ministry of Education under Grant MOE2016-T1-001-156 and Grant MOE2015-T2-2-086. This paper was presented in part at the 2017 IEEE International Symposium on Information Theory [1]. Publisher Copyright: {\textcopyright} 2018 IEEE.",

year = "2018",

month = oct,

doi = "10.1109/TIT.2018.2827942",

language = "English (US)",

volume = "64",

pages = "6567--6582",

journal = "IRE Professional Group on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "10",

}

TY - JOUR

T1 - Repairing Reed-Solomon Codes With Multiple Erasures

AU - Dau, Hoang

AU - Duursma, Iwan M.

AU - Kiah, Han Mao

AU - Milenkovic, Olgica

N1 - Funding Information: Manuscript received June 15, 2017; revised February 17, 2018; accepted April 5, 2018. Date of publication April 17, 2018; date of current version September 13, 2018. This work was supported in part by NSF under Grant CCF 1526875, in part by the Center for Science of Information under Grant NSF 0939370, and in part by NSF grant CCF 1619189. H. M. Kiah was supported by the Singapore Ministry of Education under Grant MOE2016-T1-001-156 and Grant MOE2015-T2-2-086. This paper was presented in part at the 2017 IEEE International Symposium on Information Theory [1]. Publisher Copyright: © 2018 IEEE.

PY - 2018/10

Y1 - 2018/10

N2 - Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth. A naive repair approach would require for the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. Their key idea is to recover the erased symbol by collecting a sufficiently large number of its traces, each of which can be constructed from a number of traces of other symbols. We extend the trace collection technique to cope with two and three erasures.

AB - Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth. A naive repair approach would require for the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. Their key idea is to recover the erased symbol by collecting a sufficiently large number of its traces, each of which can be constructed from a number of traces of other symbols. We extend the trace collection technique to cope with two and three erasures.

KW - Reed-Solomon codes

KW - distributed storage systems

KW - erasure

KW - repair bandwidth

KW - trace

UR - http://www.scopus.com/inward/record.url?scp=85045743289&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045743289&partnerID=8YFLogxK

U2 - 10.1109/TIT.2018.2827942

DO - 10.1109/TIT.2018.2827942

M3 - Article

AN - SCOPUS:85045743289

SN - 0018-9448

VL - 64

SP - 6567

EP - 6582

JO - IRE Professional Group on Information Theory

JF - IRE Professional Group on Information Theory

IS - 10

M1 - 8340062

ER -

Repairing Reed-Solomon Codes With Multiple Erasures

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this