The DOI matches its Crossref record; 29 of the 29 references it cites were found in a registry or an index.
Network Coding for Distributed Storage Systems
Abstract
Distributed storage systems provide reliable access to data through redundancy spread over individually unreliable nodes. Application scenarios include data centers, peer-to-peer storage systems, and storage in wireless networks. Storing data using an erasure code, in fragments spread across nodes, requires less redundancy than simple replication for the same level of reliability. However, since fragments must be periodically replaced as nodes fail, a key question is how to generate encoded fragments in a distributed way while transferring as little data as possible across the network. For an erasure coded system, a common practice to repair from a single node failure is for a new node to reconstruct the whole encoded data object to generate just one encoded block. We show that this procedure is sub-optimal. We introduce the notion of regenerating codes, which allow a new node to communicatefunctionsof the stored data from the surviving nodes. We show that regenerating codes can significantly reduce the repair bandwidth. Further, we show that there is a fundamental tradeoff between storage and repair bandwidth which we theoretically characterize using flow arguments on an appropriately constructed graph. By invoking constructive results in network coding, we introduce regenerating codes that can achieve any point in this optimal tradeoff.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Ahlswede, R., Cai, N., Li, S.-Y. R., & Yeung, R. W. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.850663 · Cited by 7,814
Li, S.-Y. R., Yeung, R. W., & Cai, N. (2003) · IEEE Transactions on Information Theory · doi:10.1109/tit.2002.807285 · Cited by 3,378
Luby, M. (2003) · The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. · doi:10.1109/sfcs.2002.1181950 · Cited by 2,757
A Random Linear Network Coding Approach to Multicast
Ho, T., Medard, M., Koetter, R., Karger, D. R., Effros, M., Shi, J., & Leong, B. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.881746 · Cited by 2,553
An algebraic approach to network coding
Koetter, R., & Medard, M. (2003) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2003.818197 · Cited by 2,356
Shokrollahi, A. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874390 · Cited by 2,154
Measurement study of peer-to-peer file sharing systems:
Saroiu, S., Gummadi, P. K., & Gribble, S. D. (2001) · SPIE Proceedings · doi:10.1117/12.449977 · Cited by 1,905
Bang-Jensen, J., & Gutin, G. (2002) · doi:10.1007/978-1-4471-3886-0 · Cited by 1,856
Wide-area cooperative storage with CFS
Dabek, F., Kaashoek, M. F., Karger, D., Morris, R., & Stoica, I. (2001) · Proceedings of the eighteenth ACM symposium on Operating systems principles · doi:10.1145/502034.502054 · Cited by 1,428
Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility
Rowstron, A., & Druschel, P. (2001) · Proceedings of the eighteenth ACM symposium on Operating systems principles · doi:10.1145/502034.502053 · Cited by 1,218
Efficient erasure correcting codes
Luby, M. G., Mitzenmacher, M., Shokrollahi, M. A., & Spielman, D. A. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910575 · Cited by 1,180
Polynomial Time Algorithms for Multicast Network Code Construction
Jaggi, S., Sanders, P., Chou, P. A., Effros, M., Egner, S., Jain, K., & Tolhuizen, L. M. G. M. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.847712 · Cited by 940
EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures
Blaum, M., Brady, J., Bruck, J., & Menon, J. (1995) · IEEE Transactions on Computers · doi:10.1109/12.364531 · Cited by 689
Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs
Bolosky, W. J., Douceur, J. R., Ely, D., & Theimer, M. (2000) · Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems · doi:10.1145/339331.339345 · Cited by 484
Pond: the oceanstore prototype
Rhea, S. C., Eaton, P. R., Geels, D., Weatherspoon, H., Zhao, B. Y., & Kubiatowicz, J. D. (2003) · Cited by 453
An Experimental Study of the Skype Peer-to-Peer VoIP System
Guha, S., & Daswani, N. (2005) · eCommons (Cornell University) · Cited by 435
X-code: MDS array codes with optimal encoding
Xu, L., & Bruck, J. (1999) · IEEE Transactions on Information Theory · doi:10.1109/18.746809 · Cited by 398
Huang, C., Chen, M., & Li, J. (2007) · Sixth IEEE International Symposium on Network Computing and Applications (NCA 2007) · doi:10.1109/nca.2007.37 · Cited by 298
Efficient replica maintenance for distributed storage systems
Chun, B.-G., Dabek, F., Haeberlen, A., Sit, E., Weatherspoon, H., Kaashoek, M. F., Kubiatowicz, J. D., & Morris, R. (2006) · Cited by 289
Polynomial time algorithms for network information flow
Sanders, P., Egner, S., & Tolhuizen, L. (2003) · Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures · doi:10.1145/777412.777464 · Cited by 269
STAR : An Efficient Coding Scheme for Correcting Triple Storage Node Failures
Huang, C., & Xu, L. (2008) · IEEE Transactions on Computers · doi:10.1109/tc.2007.70830 · Cited by 257
Decentralized erasure codes for distributed networked storage
Dimakis, A. G., Prabhakaran, V., & Ramchandran, K. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874535 · Cited by 253
Self-citationMaintenance-free global data storage
Rhea, S., Wells, C., Eaton, P., Geels, D., Zhao, B., Weatherspoon, H., & Kubiatowicz, J. (2001) · IEEE Internet Computing · doi:10.1109/4236.957894 · Cited by 251
Minimizing churn in distributed systems
Godfrey, P. B., Shenker, S., & Stoica, I. (2006) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1151659.1159931 · Cited by 207
Self-citationA measurement study of Napster and Gnutella as examples of peer-to-peer file sharing systems
Gummadi, K. P., Saroiu, S., & Gribble, S. D. (2002) · ACM SIGCOMM Computer Communication Review · doi:10.1145/510726.510756 · Cited by 197
WEAVER codes: highly fault tolerant erasure codes for storage systems
Hafner, J. L. (2005) · File and Storage Technologies · doi:10.5555/1251028.1251044 · Cited by 186
Dimakis, A. G., Prabhakaran, V. M., & Ramchandran, K. (2005) · doi:10.5555/1147685.1147708 · Cited by 164
Self-citationAnatomy of a P2P Content Distribution system with Network Coding.
Gkantsidis, C., Miller, J. L., & Rodríguez, P. (2006) · International Workshop on Peer-to-Peer Systems · Cited by 118
Awarded Best Student Paper! - Pond: The OceanStore Prototype
Rhea, S. C., Eaton, P. R., Geels, D., Weatherspoon, H., Zhao, B. Y., & Kubiatowicz, J. D. (2003) · File and Storage Technologies · Cited by 94
Cited by
Principles of Physical Layer Security in Multiuser Wireless Networks: A Survey
Mukherjee, A., Fakoorian, S. A. A., Huang, J., & Swindlehurst, A. L. (2014) · IEEE Communications Surveys & Tutorials · doi:10.1109/surv.2014.012314.00178 · Cited by 1,483
On the Locality of Codeword Symbols
Gopalan, P., Huang, C., Simitci, H., & Yekhanin, S. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2012.2208937 · Cited by 831
Speeding Up Distributed Machine Learning Using Codes
Lee, K., Lam, M., Pedarsani, R., Papailiopoulos, D., & Ramchandran, K. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2736066 · Cited by 829
Self-citationXORing elephants: novel erasure codes for big data
Sathiamoorthy, M., Asteris, M., Papailiopoulos, D., Dimakis, A. G., Vadali, R., Chen, S., & Borthakur, D. (2013) · Proceedings of the VLDB Endowment · doi:10.14778/2535573.2488339 · Cited by 689
Self-citationFemtocaching and device-to-device collaboration: A new architecture for wireless video distribution
Golrezaei, N., Molisch, A. F., Dimakis, A. G., & Caire, G. (2013) · IEEE Communications Magazine · doi:10.1109/mcom.2013.6495773 · Cited by 686
Self-citation
Metadata
- Authors
- Dimakis, A. G., Godfrey, P. B., Wu, Y., Wainwright, M. J., & Ramchandran, K.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2010-09
- Volume
- 56
- Issue
- 9
- Pages
- 4539-4551
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2105185344
- Cited by
- 1,914
- References
- 29
- FWCI
- 146.35
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.