{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T15:41:16Z","timestamp":1782834076236,"version":"3.54.5"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,10,31]],"date-time":"2014-10-31T00:00:00Z","timestamp":1414713600000},"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":["AoE\/E-02\/08, ECS CUHK419212"],"award-info":[{"award-number":["AoE\/E-02\/08, ECS CUHK419212"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2014,10,31]]},"abstract":"<jats:p>\n            Practical storage systems often adopt erasure codes to tolerate device failures and sector failures, both of which are prevalent in the field. However, traditional erasure codes employ device-level redundancy to protect against sector failures, and hence incur significant space overhead. Recent sector-disk (SD) codes are available only for limited configurations. By making a relaxed but practical assumption, we construct a general family of erasure codes called\n            <jats:italic>STAIR codes<\/jats:italic>\n            , which efficiently and provably tolerate both device and sector failures without any restriction on the size of a storage array and the numbers of tolerable device failures and sector failures. We propose the\n            <jats:italic>upstairs encoding<\/jats:italic>\n            and\n            <jats:italic>downstairs encoding<\/jats:italic>\n            methods, which provide complementary performance advantages for different configurations. We conduct extensive experiments on STAIR codes in terms of space saving, encoding\/decoding speed, and update cost. We demonstrate that STAIR codes not only improve space efficiency over traditional erasure codes, but also provide better computational efficiency than SD codes based on our special code construction. Finally, we present analytical models that characterize the reliability of STAIR codes, and show that the support of a wider range of configurations by STAIR codes is critical for tolerating sector failure bursts discovered in the field.\n          <\/jats:p>","DOI":"10.1145\/2658991","type":"journal-article","created":{"date-parts":[[2014,11,4]],"date-time":"2014-11-04T13:18:31Z","timestamp":1415107111000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":50,"title":["STAIR Codes"],"prefix":"10.1145","volume":"10","author":[{"given":"Mingqiang","family":"Li","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Patrick P. C.","family":"Lee","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,10,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1254882.1254917"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2006.261569"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.364531"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.485722"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2252395"},{"key":"e_1_2_1_6_1","volume-title":"Filed","author":"Blaum M.","year":"2011"},{"key":"e_1_2_1_7_1","unstructured":"Blaum M. and Plank J. S. 2013. Construction of sector-disk (SD) codes with two global parity symbols. IBM Res. Rep. RJ10511 (ALM1308-007) Almaden Research Center IBM Research Division.  Blaum M. and Plank J. S. 2013. Construction of sector-disk (SD) codes with two global parity symbols. IBM Res. Rep. RJ10511 (ALM1308-007) Almaden Research Center IBM Research Division."},{"key":"e_1_2_1_8_1","volume-title":"Tech. Rep. TR-95-048","author":"Blomer J.","year":"1995"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 8th USENIX Conference on File and Storage Technologies (FAST\u201910)","author":"Boboila S."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 3rd USENIX Conference on File and Storage Technologies (FAST\u201904)","author":"Corbett P."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353452.1353453"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970348.1970350"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1954.1057464"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.150"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.200"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 2nd Workshop on Hot Topics in Storage and File Systems (HotStorage\u201910)","author":"Greenan K. M."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1669112.1669118"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 10th USENIX Conference on File and Storage Technologies (FAST\u201912)","author":"Grupp L. M."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 4th USENIX Conference on File and Storage Technologies (FAST\u201905)","author":"Hafner J. L.","year":"2005"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2006.40"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2435204.2435207"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201912)","author":"Huang C."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 4th USENIX Conference on File and Storage Technologies (FAST\u201905)","author":"Huang C."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/NAS.2008.20"},{"key":"e_1_2_1_25_1","unstructured":"Intel. 2005. Intelligent RAID 6 theory --- overview and implementation. White Paper. Intel Corporation.  Intel. 2005. Intelligent RAID 6 theory --- overview and implementation. White Paper. Intel Corporation."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 12th USENIX Conference on File and Storage Technologies (FAST\u201914)","author":"Li M."},{"key":"e_1_2_1_27_1","unstructured":"Li M. and Shu J. 2011. C-Codes: Cyclic lowest-density MDS array codes constructed using starters for RAID 6. IBM Res. Rep. RC25218 (C1110-004) China Research Laboratory IBM Research Division.  Li M. and Shu J. 2011. C-Codes: Cyclic lowest-density MDS array codes constructed using starters for RAID 6. IBM Res. Rep. RC25218 (C1110-004) China Research Laboratory IBM Research Division."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480439.1480444"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 8th USENIX Conference on File and Storage Technologies (FAST\u201910)","author":"Oprea A."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 5th USENIX Conference on File and Storage Technologies (FAST\u201907)","author":"Pinheiro E."},{"key":"e_1_2_1_31_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_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2560013"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 11th USENIX Conference on File and Storage Technologies (FAST\u201913)","author":"Plank J. S."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970338.1970340"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.v35:2"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 11th USENIX Conference on File and Storage Technologies (FAST\u201913)","author":"Plank J. S."},{"key":"e_1_2_1_37_1","volume-title":"Tutorial: Erasure coding for storage applications. Slides presented at the 11th USENIX Conference on File and Storage Technologies.","author":"Plank J. S.","year":"2013"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/NCA.2006.43"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0108018"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535573.2488339"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 8th USENIX Conference on File and Storage Technologies (FAST\u201910)","author":"Schroeder B."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 5th USENIX Conference on File and Storage Technologies (FAST\u201907)","author":"Schroeder B."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 12th Annual Meeting of the IEEE\/ACM International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS\u201904)","author":"Schwarz T. J. E."},{"key":"e_1_2_1_44_1","volume-title":"Tech. Rep. TR-3298, NetApp","author":"White J.","year":"2010"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 17th Annual Meeting of the IEEE\/ACM International Symposium on Modelling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS\u201909)","author":"Wildani A."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.782102"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.746809"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 11th USENIX Conference on File and Storage Technologies (FAST\u201913)","author":"Zheng M."}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2658991","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2658991","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:19Z","timestamp":1750231699000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2658991"}},"subtitle":["A General Family of Erasure Codes for Tolerating Device and Sector Failures"],"short-title":[],"issued":{"date-parts":[[2014,10,31]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,10,31]]}},"alternative-id":["10.1145\/2658991"],"URL":"https:\/\/doi.org\/10.1145\/2658991","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,31]]},"assertion":[{"value":"2014-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}