{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T16:05:49Z","timestamp":1787760349435,"version":"build-2784847793"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,3,1]],"date-time":"2013-03-01T00:00:00Z","timestamp":1362096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["411209, 411010, 411011"],"award-info":[{"award-number":["411209, 411010, 411011"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Area of Excellence Grant","award":["AoE\/E-02\/08"],"award-info":[{"award-number":["AoE\/E-02\/08"]}]},{"DOI":"10.13039\/100004351","name":"Cisco Systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004351","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2012CB315904"],"award-info":[{"award-number":["2012CB315904"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004318","name":"Microsoft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004318","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Open Project of Shenzhen Key Lab of Cloud Computing Technology and Application"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2013,3]]},"abstract":"<jats:p>We design flexible schemes to explore the tradeoffs between storage space and access efficiency in reliable data storage systems. Aiming at this goal, two new classes of erasure-resilient codes are introduced -- Basic Pyramid Codes (BPC) and Generalized Pyramid Codes (GPC). Both schemes require slightly more storage space than conventional schemes, but significantly improve the critical performance of read during failures and unavailability.<\/jats:p>\n                  <jats:p>\n                    As a by-product, we establish a necessary matching condition to characterize the limit of failure recovery, that is, unless the matching condition is satisfied, a failure case is impossible to recover. In addition, we define a maximally recoverable (MR) property. For all ERC schemes holding the MR property, the matching condition becomes sufficient, that is, all failure cases satisfying the matching condition are indeed recoverable. We show that GPC is the\n                    <jats:italic>first<\/jats:italic>\n                    class of non-MDS schemes holding the MR property.\n                  <\/jats:p>","DOI":"10.1145\/2435204.2435207","type":"journal-article","created":{"date-parts":[[2013,3,25]],"date-time":"2013-03-25T09:31:59Z","timestamp":1364203919000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":134,"title":["Pyramid Codes"],"prefix":"10.1145","volume":"9","author":[{"given":"Cheng","family":"Huang","sequence":"first","affiliation":[{"name":"Microsoft Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minghua","family":"Chen","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jin","family":"Li","sequence":"additional","affiliation":[{"name":"Microsoft Research"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,3]]},"reference":[{"key":"e_1_2_1_1_1","volume":"200","author":"Abd-El-Malek M., W. V. C.","journal-title":"J."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2005.96"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Blahut R. E. 2003. Algebraic Codes for Data Transmission. Cambridge University Press.  Blahut R. E. 2003. Algebraic Codes for Data Transmission . Cambridge University Press.","DOI":"10.1017\/CBO9780511800467"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.746771"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.364531"},{"key":"e_1_2_1_6_1","unstructured":"Blomer J. Kalfane M. Karp R. Karpinski M. Luby M. and Zuckerman D. 1995. An XOR-based erasure-resilient coding scheme. Tech. rep. TR-95-048 ICSI Berkeley CA.  Blomer J. Kalfane M. Karp R. Karpinski M. Luby M. and Zuckerman D. 1995. An XOR-based erasure-resilient coding scheme. Tech. rep. TR-95-048 ICSI Berkeley CA."},{"key":"e_1_2_1_7_1","volume-title":"HDFS RAID. Hadoop User Group Meeting.","author":"Borthakur D."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of IEEE International Symposium on Information Theory. IEEE","author":"Cadambe V. R."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the Asilomar Conference on Signals, Systems and Computers.","author":"Cadambe V. R."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043571"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies.","author":"Chang F."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the IEEE International Symposium on Information Theory.","author":"Chen M."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/176979.176981"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/313238.313249"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies.","author":"Corbett P."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2054295"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Workshop on Design Issues in Anonymity and Unobservability.","author":"Dingledine R."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies.","author":"Dubnicki C."},{"key":"e_1_2_1_19_1","unstructured":"Fikes A. 2010. Storage architecture and challenges. Google Faculty Summit.  Fikes A. 2010. Storage architecture and challenges. Google Faculty Summit."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation.","author":"Ford D."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Gallager R. G. 1963. Low-density parity-check codes. MIT Press Cambridge MA.  Gallager R. G. 1963. Low-density parity-check codes. MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/4347.001.0001"},{"key":"e_1_2_1_22_1","unstructured":"Gantenbein D. 2012. A better way to store data. Microsoft Res. Featured Stories. http:\/\/research.microsoft.com\/en-us\/news\/features\/erasurecoding-090512.aspx.  Gantenbein D. 2012. A better way to store data. Microsoft Res. Featured Stories. http:\/\/research.microsoft.com\/en-us\/news\/features\/erasurecoding-090512.aspx."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/945445.945450"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the Allerton Conference on Communication, Control, and Computing.","author":"Gopalan P."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2010.5496983"},{"key":"e_1_2_1_26_1","volume":"200","author":"Greenan K. M.","journal-title":"J."},{"key":"e_1_2_1_27_1","volume":"200","author":"Greenan K. M.","journal-title":"J."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Web 2.0 Expo.","author":"Grolimund D.","year":"2007"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the USENIX Symposium on Networked Systems Design and Implementation.","author":"Haeberlen A."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies.","author":"Hafner J. L.","year":"2005"},{"key":"e_1_2_1_31_1","unstructured":"Hafner J. L. and Rao K. 2006. Notes on reliability models for non-MDS erasure codes. IBM Tech. rep. RJ10391.  Hafner J. L. and Rao K. 2006. Notes on reliability models for non-MDS erasure codes. IBM Tech. rep. RJ10391."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies.","author":"Hafner J. L."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research.","author":"Hamilton J.","year":"2007"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies.","author":"Hosekote D. K."},{"key":"e_1_2_1_35_1","unstructured":"Huang C. and Xu L. 2003. Fast software implementation of finite field operations. Tech. rep. Washington University St. Louis MO.  Huang C. and Xu L. 2003. Fast software implementation of finite field operations. Tech. rep. Washington University St. Louis MO."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2007.70830"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the IEEE International Symposium on Network Computing and Applications. IEEE","author":"Huang C."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the IEEE Information Theory Workshop. IEEE","author":"Huang C."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the USENIX Annual Technical Conference.","author":"Huang C."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the USENIX Workshop on Hot Topics in Storage and File Systems.","author":"Khan O."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies.","author":"Khan O."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/378993.379239"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.910575"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the IEEE International Conference on Dependable Systems and Networks.","author":"Luo J."},{"key":"e_1_2_1_45_1","unstructured":"MacWilliams F. J. and Sloane N. J. A. 1977. The Theory of Error Correcting Codes. North-Holland Amsterdam.  MacWilliams F. J. and Sloane N. J. A. 1977. The Theory of Error Correcting Codes . North-Holland Amsterdam."},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the International Workshop on Peer-To-Peer Systems.","author":"Maymounkov P."},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the IEEE INFOCOM Mini-Conference. IEEE","author":"Papailiopoulos D. S."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199709)27:9%3C995::AID-SPE111%3E3.3.CO;2-Y"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies.","author":"Plank J. S.","year":"2008"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/NCA.2006.43"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Reed I. S. and Solomon G. 1960. Polynomial codes over certain finite fields. J. Soc. Industrial Appl. Math.  Reed I. S. and Solomon G. 1960. Polynomial codes over certain finite fields. J. Soc. Industrial Appl. Math .","DOI":"10.1137\/0108018"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies.","author":"Rhea S."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/502034.502053"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024393.1024400"},{"key":"e_1_2_1_55_1","unstructured":"Schrijver A. 2003. Combinatorial optimization polyhedra and efficiency. Alg. Combinatorics.  Schrijver A. 2003. Combinatorial optimization polyhedra and efficiency. Alg. Combinatorics ."},{"key":"e_1_2_1_56_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies.","author":"Schroeder B."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2010.5496972"},{"key":"e_1_2_1_58_1","doi-asserted-by":"crossref","unstructured":"Suh C. and Ramchandran K. 2011. Exact regeneration codes for distributed storage repair using interference alignment. IEEE Trans. Inf. Theory.  Suh C. and Ramchandran K. 2011. Exact regeneration codes for distributed storage repair using interference alignment. IEEE Trans. Inf. Theory .","DOI":"10.1109\/ISIT.2010.5513263"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1981.1056404"},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies.","author":"Ungureanu C."},{"key":"e_1_2_1_61_1","doi-asserted-by":"crossref","unstructured":"Wang Z. Tamo I. and Bruck J. 2011. On codes for optimal rebuilding access. Tech. rep. ETR111 Caltech.  Wang Z. Tamo I. and Bruck J. 2011. On codes for optimal rebuilding access. Tech. rep. ETR111 Caltech.","DOI":"10.1109\/Allerton.2011.6120327"},{"key":"e_1_2_1_62_1","volume-title":"Proceedings of the International Workshop on Peer-To-Peer Systems.","author":"Weatherspoon H."},{"key":"e_1_2_1_63_1","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies.","author":"Welch B."},{"key":"e_1_2_1_64_1","volume-title":"Proceedings of the IEEE International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems.","author":"Wildani A."}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2435204.2435207","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2435204.2435207","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:35:40Z","timestamp":1750221340000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2435204.2435207"}},"subtitle":["Flexible Schemes to Trade Space for Access Efficiency in Reliable Data Storage Systems"],"short-title":[],"issued":{"date-parts":[[2013,3]]},"references-count":64,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["10.1145\/2435204.2435207"],"URL":"https:\/\/doi.org\/10.1145\/2435204.2435207","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3]]},"assertion":[{"value":"2011-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}