New bounds on the (n, k, d) storage systems with exact repair

Soheil Mohajer; Ravi Tandon

doi:10.1109/ISIT.2015.7282817

New bounds on the (n, k, d) storage systems with exact repair

Soheil Mohajer, Ravi Tandon

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

20 Scopus citations

Abstract

The exact-repair problem for distributed storage systems is considered. Characterizing the optimal storage-vs-repair bandwidth tradeoff for such systems remains an open problem for more than four storage nodes. A new family of information theoretic bounds is provided for the storage-vs-repair bandwidth tradeoff for all (n, k, d) systems. The proposed bound readily recovers Tian's result for the (4, 3, 3) system, and hence suffices for exact characterization for this system. In addition, the bound improves upon the existing bounds for the (5, 4, 4) system. More generally, it is shown that this bound characterizes the optimal boundary of the exact repair tradeoff for all distributed storage systems, with (n, k, d) = (n, n-1; n-1) when β ≤ 2α/k.

Original language	English (US)
Title of host publication	Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2056-2060
Number of pages	5
ISBN (Electronic)	9781467377041
DOIs	https://doi.org/10.1109/ISIT.2015.7282817
State	Published - Sep 28 2015
Externally published	Yes
Event	IEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong Duration: Jun 14 2015 → Jun 19 2015

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2015-June
ISSN (Print)	2157-8095

Other

Other	IEEE International Symposium on Information Theory, ISIT 2015
Country/Territory	Hong Kong
City	Hong Kong
Period	6/14/15 → 6/19/15

Keywords

Distributed storage system
Exact repair
New outer bounds

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2015.7282817

Cite this

Mohajer, S., & Tandon, R. (2015). New bounds on the (n, k, d) storage systems with exact repair. In Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015 (pp. 2056-2060). Article 7282817 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2015-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2015.7282817

New bounds on the (n, k, d) storage systems with exact repair. / Mohajer, Soheil; Tandon, Ravi.
Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 2056-2060 7282817 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2015-June).

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

Mohajer, S & Tandon, R 2015, New bounds on the (n, k, d) storage systems with exact repair. in Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015., 7282817, IEEE International Symposium on Information Theory - Proceedings, vol. 2015-June, Institute of Electrical and Electronics Engineers Inc., pp. 2056-2060, IEEE International Symposium on Information Theory, ISIT 2015, Hong Kong, Hong Kong, 6/14/15. https://doi.org/10.1109/ISIT.2015.7282817

@inproceedings{5c69fba3796f48649a4716d051d18fee,

title = "New bounds on the (n, k, d) storage systems with exact repair",

abstract = "The exact-repair problem for distributed storage systems is considered. Characterizing the optimal storage-vs-repair bandwidth tradeoff for such systems remains an open problem for more than four storage nodes. A new family of information theoretic bounds is provided for the storage-vs-repair bandwidth tradeoff for all (n, k, d) systems. The proposed bound readily recovers Tian's result for the (4, 3, 3) system, and hence suffices for exact characterization for this system. In addition, the bound improves upon the existing bounds for the (5, 4, 4) system. More generally, it is shown that this bound characterizes the optimal boundary of the exact repair tradeoff for all distributed storage systems, with (n, k, d) = (n, n-1; n-1) when β ≤ 2α/k.",

keywords = "Distributed storage system, Exact repair, New outer bounds",

author = "Soheil Mohajer and Ravi Tandon",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; IEEE International Symposium on Information Theory, ISIT 2015 ; Conference date: 14-06-2015 Through 19-06-2015",

year = "2015",

month = sep,

day = "28",

doi = "10.1109/ISIT.2015.7282817",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

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

pages = "2056--2060",

booktitle = "Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015",

}

TY - GEN

T1 - New bounds on the (n, k, d) storage systems with exact repair

AU - Mohajer, Soheil

AU - Tandon, Ravi

PY - 2015/9/28

Y1 - 2015/9/28

N2 - The exact-repair problem for distributed storage systems is considered. Characterizing the optimal storage-vs-repair bandwidth tradeoff for such systems remains an open problem for more than four storage nodes. A new family of information theoretic bounds is provided for the storage-vs-repair bandwidth tradeoff for all (n, k, d) systems. The proposed bound readily recovers Tian's result for the (4, 3, 3) system, and hence suffices for exact characterization for this system. In addition, the bound improves upon the existing bounds for the (5, 4, 4) system. More generally, it is shown that this bound characterizes the optimal boundary of the exact repair tradeoff for all distributed storage systems, with (n, k, d) = (n, n-1; n-1) when β ≤ 2α/k.

AB - The exact-repair problem for distributed storage systems is considered. Characterizing the optimal storage-vs-repair bandwidth tradeoff for such systems remains an open problem for more than four storage nodes. A new family of information theoretic bounds is provided for the storage-vs-repair bandwidth tradeoff for all (n, k, d) systems. The proposed bound readily recovers Tian's result for the (4, 3, 3) system, and hence suffices for exact characterization for this system. In addition, the bound improves upon the existing bounds for the (5, 4, 4) system. More generally, it is shown that this bound characterizes the optimal boundary of the exact repair tradeoff for all distributed storage systems, with (n, k, d) = (n, n-1; n-1) when β ≤ 2α/k.

KW - Distributed storage system

KW - Exact repair

KW - New outer bounds

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

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

U2 - 10.1109/ISIT.2015.7282817

DO - 10.1109/ISIT.2015.7282817

M3 - Conference contribution

AN - SCOPUS:84969800025

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2056

EP - 2060

BT - Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - IEEE International Symposium on Information Theory, ISIT 2015

Y2 - 14 June 2015 through 19 June 2015

ER -

New bounds on the (n, k, d) storage systems with exact repair

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this