Polynomial length MDS codes with optimal repair in distributed storage

Viveck R. Cadambe; Cheng Huang; Jin Li; Sanjeev Mehrotra

doi:10.1109/ACSSC.2011.6190343

Polynomial length MDS codes with optimal repair in distributed storage

Viveck R. Cadambe, Cheng Huang, Jin Li, Sanjeev Mehrotra

Electrical Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

50 Scopus citations

Abstract

An (n, k) maximum distance separable (MDS) code can be used to store data in n storage nodes, such that the system can tolerate the failure of any (n-k) storage nodes. Recently, MDS codes have been constructed which satisfy an additional optimal repair property as follows: the failure of a single storage node can be repaired by downloading a fraction of 1/(n - k) of the data stored in every surviving storage node. In previous constructions satisfying this optimal repair property, the size of the code is polynomial in k for the high-redundancy regime of k/n ≤ 1/2, but the codes have an exponential size (w.r.t. k) for the practically important low-redundancy regime of k/n > 1/2. In this paper, we construct a class of polynomial size codes in this low redundancy regime.

Original language	English (US)
Title of host publication	Conference Record of the 45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011
Pages	1850-1854
Number of pages	5
DOIs	https://doi.org/10.1109/ACSSC.2011.6190343
State	Published - 2011
Event	45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011 - Pacific Grove, CA, United States Duration: Nov 6 2011 → Nov 9 2011

Publication series

Name	Conference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)	1058-6393

Other

Other	45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011
Country/Territory	United States
City	Pacific Grove, CA
Period	11/6/11 → 11/9/11

All Science Journal Classification (ASJC) codes

Signal Processing
Computer Networks and Communications

Access to Document

10.1109/ACSSC.2011.6190343

Cite this

Cadambe, V. R., Huang, C., Li, J., & Mehrotra, S. (2011). Polynomial length MDS codes with optimal repair in distributed storage. In Conference Record of the 45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011 (pp. 1850-1854). Article 6190343 (Conference Record - Asilomar Conference on Signals, Systems and Computers). https://doi.org/10.1109/ACSSC.2011.6190343

@inproceedings{8ad68bfa7ffb4f2484cbe88a273f9e7c,

title = "Polynomial length MDS codes with optimal repair in distributed storage",

abstract = "An (n, k) maximum distance separable (MDS) code can be used to store data in n storage nodes, such that the system can tolerate the failure of any (n-k) storage nodes. Recently, MDS codes have been constructed which satisfy an additional optimal repair property as follows: the failure of a single storage node can be repaired by downloading a fraction of 1/(n - k) of the data stored in every surviving storage node. In previous constructions satisfying this optimal repair property, the size of the code is polynomial in k for the high-redundancy regime of k/n ≤ 1/2, but the codes have an exponential size (w.r.t. k) for the practically important low-redundancy regime of k/n > 1/2. In this paper, we construct a class of polynomial size codes in this low redundancy regime.",

author = "Cadambe, {Viveck R.} and Cheng Huang and Jin Li and Sanjeev Mehrotra",

year = "2011",

doi = "10.1109/ACSSC.2011.6190343",

language = "English (US)",

isbn = "9781467303231",

series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",

pages = "1850--1854",

booktitle = "Conference Record of the 45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011",

note = "45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011 ; Conference date: 06-11-2011 Through 09-11-2011",

}

Cadambe, VR, Huang, C, Li, J & Mehrotra, S 2011, Polynomial length MDS codes with optimal repair in distributed storage. in Conference Record of the 45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011., 6190343, Conference Record - Asilomar Conference on Signals, Systems and Computers, pp. 1850-1854, 45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011, Pacific Grove, CA, United States, 11/6/11. https://doi.org/10.1109/ACSSC.2011.6190343

Polynomial length MDS codes with optimal repair in distributed storage. / Cadambe, Viveck R.; Huang, Cheng; Li, Jin et al.
Conference Record of the 45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011. 2011. p. 1850-1854 6190343 (Conference Record - Asilomar Conference on Signals, Systems and Computers).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Polynomial length MDS codes with optimal repair in distributed storage

AU - Cadambe, Viveck R.

AU - Huang, Cheng

AU - Li, Jin

AU - Mehrotra, Sanjeev

PY - 2011

Y1 - 2011

N2 - An (n, k) maximum distance separable (MDS) code can be used to store data in n storage nodes, such that the system can tolerate the failure of any (n-k) storage nodes. Recently, MDS codes have been constructed which satisfy an additional optimal repair property as follows: the failure of a single storage node can be repaired by downloading a fraction of 1/(n - k) of the data stored in every surviving storage node. In previous constructions satisfying this optimal repair property, the size of the code is polynomial in k for the high-redundancy regime of k/n ≤ 1/2, but the codes have an exponential size (w.r.t. k) for the practically important low-redundancy regime of k/n > 1/2. In this paper, we construct a class of polynomial size codes in this low redundancy regime.

AB - An (n, k) maximum distance separable (MDS) code can be used to store data in n storage nodes, such that the system can tolerate the failure of any (n-k) storage nodes. Recently, MDS codes have been constructed which satisfy an additional optimal repair property as follows: the failure of a single storage node can be repaired by downloading a fraction of 1/(n - k) of the data stored in every surviving storage node. In previous constructions satisfying this optimal repair property, the size of the code is polynomial in k for the high-redundancy regime of k/n ≤ 1/2, but the codes have an exponential size (w.r.t. k) for the practically important low-redundancy regime of k/n > 1/2. In this paper, we construct a class of polynomial size codes in this low redundancy regime.

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

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

U2 - 10.1109/ACSSC.2011.6190343

DO - 10.1109/ACSSC.2011.6190343

M3 - Conference contribution

AN - SCOPUS:84861323713

SN - 9781467303231

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 1850

EP - 1854

BT - Conference Record of the 45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011

T2 - 45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011

Y2 - 6 November 2011 through 9 November 2011

ER -

Polynomial length MDS codes with optimal repair in distributed storage

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this