The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
XORing elephants: novel erasure codes for big data
Abstract
Distributed storage systems for large clusters typically use replication to provide reliability. Recently, erasure codes have been used to reduce the large storage overhead of three-replicated systems. Reed-Solomon codes are the standard design choice and their high repair cost is often considered an unavoidable price to pay for high storage efficiency and high reliability. This paper shows how to overcome this limitation. We present a novel family of erasure codes that are efficiently repairable and offer higher reliability compared to Reed-Solomon codes. We show analytically that our codes are optimal on a recently identified tradeoff between locality and minimum distance. We implement our new codes in Hadoop HDFS and compare to a currently deployed HDFS module that uses Reed-Solomon codes. Our modified HDFS implementation shows a reduction of approximately 2× on the repair disk I/O and repair network traffic. The disadvantage of the new coding scheme is that it requires 14% more storage compared to Reed-Solomon codes, an overhead shown to be information theoretically optimal to obtain locality. Because the new codes repair failures faster, this provides higher reliability, which is orders of magnitude higher compared to replication.
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
Polynomial Codes Over Certain Finite Fields
Reed, I. S., & Solomon, G. (1960) · Journal of the Society for Industrial and Applied Mathematics · doi:10.1137/0108018 · Cited by 3,662
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
VL2: a scalable and flexible data center network
Greenberg, A., Hamilton, J. R., Jain, N., Kandula, S., Kim, C., Lahiri, P., Maltz, D. A., Patel, P., & Sengupta, S. (2009) · Proceedings of the ACM SIGCOMM 2009 conference on Data communication · doi:10.1145/1592568.1592576 · Cited by 2,111
Network Coding for Distributed Storage Systems
Dimakis, A. G., Godfrey, P. B., Wu, Y., Wainwright, M. J., & Ramchandran, K. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2054295 · Cited by 1,914
Self-citationThe cost of a cloud: research problems in data center networks
Greenberg, A., Hamilton, J., Maltz, D. A., & Patel, P. (2008) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1496091.1496103 · Cited by 1,621
Dcell: a scalable and fault-tolerant network structure for data centers
Guo, C., Wu, H., Tan, K., Shi, L., Zhang, Y., & Lu, S. (2008) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1402946.1402968 · Cited by 994
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
Windows Azure Storage: a highly available cloud storage service with strong consistency
Calder, B., Wang, J., Ogus, A., Nilakantan, N., Skjolsvold, A., McKelvie, S., Xu, Y., Srivastav, S., Wu, J., Simitci, H., et al. (2011) · Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles · doi:10.1145/2043556.2043571 · Cited by 796
Write off-loading: Practical power management for enterprise storage
Narayanan, D., Donnelly, A., & Rowstron, A. (2008) · ACM Transactions on Storage · doi:10.1145/1416944.1416949 · Cited by 762
VL2: a scalable and flexible data center network
Greenberg, A., Hamilton, J. R., Jain, N., Kandula, S., Kim, C., Lahiri, P., Maltz, D. A., Patel, P., & Sengupta, S. (2009) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1594977.1592576 · Cited by 711
Rashmi, K. V., Shah, N. B., & Kumar, P. V. (2011) · NOT FOUND REPOSITORY (Indian Institute of Science Bangalore) · Cited by 701
A Survey on Network Codes for Distributed Storage
Dimakis, A. G., Ramchandran, K., Wu, Y., et al. (2011) · Proceedings of the IEEE · doi:10.1109/jproc.2010.2096170 · Cited by 639
Self-citationManaging data transfers in computer clusters with orchestra
Chowdhury, M., Zaharia, M., Ma, J., Jordan, M. I., & Stoica, I. (2011) · Proceedings of the ACM SIGCOMM 2011 conference · doi:10.1145/2018436.2018448 · Cited by 543
Availability in globally distributed storage systems
Ford, D. A., Labelle, F., Popovici, F. I., Stokely, M., Truong, V., Barroso, L. A., Grimes, C., & Quinlan, S. (2010) · doi:10.5555/1924943.1924948 · Cited by 539
UNIVERSITY OF CALIFORNIA: SCHOOL OF OPTOMETRY
STODDARD, K. B. (1948) · Optometry and Vision Science · doi:10.1097/00006324-194805000-00008 · Cited by 534
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
Self-repairing homomorphic codes for distributed storage systems
Oggier, F., & Datta, A. (2011) · 2011 Proceedings IEEE INFOCOM · doi:10.1109/infcom.2011.5934901 · Cited by 247
Proceedings of the 9th USENIX conference on Operating systems design and implementation
Arpaci-Dusseau, R. H., & Chen, B. (2010) · Cited by 242
Papailiopoulos, D. S., & Dimakis, A. G. (2012) · 2012 IEEE International Symposium on Information Theory Proceedings · doi:10.1109/isit.2012.6284027 · Cited by 207
Self-citationSimple regenerating codes: Network coding for cloud storage
Papailiopoulos, D. S., Luo, J., Dimakis, A. G., Huang, C., & Li, J. (2012) · 2012 Proceedings IEEE INFOCOM · doi:10.1109/infcom.2012.6195703 · Cited by 195
Self-citationReliability mechanisms for very large storage systems
Xin, Q., Miller, E. L., Schwarz, T., Long, D. D. E., Brandt, S. A., & Litwin, W. (2003) · 20th IEEE/11th NASA Goddard Conference on Mass Storage Systems and Technologies, 2003. (MSST 2003). Proceedings. · doi:10.1109/mass.2003.1194851 · Cited by 190
XORing Elephants: Novel Erasure Codes for Big DataPreprint
Sathiamoorthy, M., Asteris, M., Papailiopoulos, D., Dimakis, A. G., Vadali, R., Chen, S., & Borthakur, D. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.3791 · Cited by 102
Self-citationMDS array codes with optimal rebuilding
Tamo, I., Wang, Z., & Bruck, J. (2011) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2011.6033733 · Cited by 65
Reliability and power-efficiency in erasure-coded storage systems
Greenan, K. M. (2009) · Cited by 29
Cited by
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-citation
Metadata
- Authors
- Sathiamoorthy, M., Asteris, M., Papailiopoulos, D., Dimakis, A. G., Vadali, R., Chen, S., & Borthakur, D.
- Venue
- Proceedings of the VLDB Endowment
- Published
- 2013-03
- Volume
- 6
- Issue
- 5
- Pages
- 325-336
- ISSN
- 2150-8097 (ISSN-L)
- OpenAlex
- W2138744797
- Cited by
- 689
- References
- 24
- FWCI
- 95.60
- 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.