{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T15:41:17Z","timestamp":1782834077100,"version":"3.54.5"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2004CB3182052007CB311100"],"award-info":[{"award-number":["2004CB3182052007CB311100"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004602","name":"Program for New Century Excellent Talents in University","doi-asserted-by":"publisher","award":["NCET-05-0067"],"award-info":[{"award-number":["NCET-05-0067"]}],"id":[{"id":"10.13039\/501100004602","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["6.09E+15"],"award-info":[{"award-number":["6.09E+15"]}],"id":[{"id":"10.13039\/501100001809","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":[[2009,1]]},"abstract":"<jats:p>\n            As storage systems grow in size and complexity, they are increasingly confronted with concurrent disk failures together with multiple unrecoverable sector errors. To ensure high data reliability and availability, erasure codes with high fault tolerance are required. In this article, we present a new family of erasure codes with high fault tolerance, named GRID codes. They are called such because they are a family of\n            <jats:italic>strip-based codes<\/jats:italic>\n            whose strips are arranged into multi-dimensional grids. In the construction of GRID codes, we first introduce a concept of\n            <jats:italic>matched codes<\/jats:italic>\n            and then discuss how to use matched codes to construct GRID codes. In addition, we propose an iterative reconstruction algorithm for GRID codes. We also discuss some important features of GRID codes. Finally, we compare GRID codes with several categories of existing codes. Our comparisons show that for large-scale storage systems, our GRID codes have attractive advantages over many existing erasure codes: (a) They are completely XOR-based and have very regular structures, ensuring easy implementation; (b) they can provide up to 15 and even higher fault tolerance; and (c) their storage efficiency can reach up to 80% and even higher. All the advantages make GRID codes more suitable for large-scale storage systems.\n          <\/jats:p>","DOI":"10.1145\/1480439.1480444","type":"journal-article","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T16:42:19Z","timestamp":1234284139000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["GRID codes"],"prefix":"10.1145","volume":"4","author":[{"given":"Mingqiang","family":"Li","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiwu","family":"Shu","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Weimin","family":"Zheng","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,2,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2005.96"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC)","volume":"2","author":"Anne N. B.","unstructured":"Anne , N. B. , Thirunavukkarasu , U. , and Latifi , S . 2004. Three and four-dimensional parity-check codes for correction and detection of multiple errors . In Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC) , vol. 2 . IEEE Computer Society, 840--845. Anne, N. B., Thirunavukkarasu, U., and Latifi, S. 2004. Three and four-dimensional parity-check codes for correction and detection of multiple errors. In Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC), vol. 2. IEEE Computer Society, 840--845."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1254882.1254917"},{"key":"e_1_2_1_4_1","unstructured":"Blaum M. Brady J. Bruck J. Menon J. and Vardy A. 2001. The EVENODD code and its generalization: An efficient scheme for tolerating multiple disk failures in RAID architectures. InHigh Performance Mass Storage and Parallel I\/O: Technologies and Applications 187--208.  Blaum M. Brady J. Bruck J. Menon J. and Vardy A. 2001. The EVENODD code and its generalization: An efficient scheme for tolerating multiple disk failures in RAID architectures. InHigh Performance Mass Storage and Parallel I\/O: Technologies and Applications 187--208."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.485722"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.364531"},{"key":"e_1_2_1_7_1","unstructured":"Bloemer 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 International Computer Science Institute Berkeley California.  Bloemer 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 International Computer Science Institute Berkeley California."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/176979.176981"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2005.21"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 3rd USENIX Conference on File and Storage Technologies (FAST'04)","author":"Corbett P.","unstructured":"Corbett , P. , English , B. , Goel , A. , Grcanac , T. , Kleiman , S. , Leong , J. , and Sankar , S . 2004. Row-Diagonal parity for double disk failure correction . In Proceedings of the 3rd USENIX Conference on File and Storage Technologies (FAST'04) . USENIX Association, 1--14. Corbett, P., English, B., Goel, A., Grcanac, T., Kleiman, S., Leong, J., and Sankar, S. 2004. Row-Diagonal parity for double disk failure correction. In Proceedings of the 3rd USENIX Conference on File and Storage Technologies (FAST'04). USENIX Association, 1--14."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.150"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.200"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN'04)","author":"Fr\u00f8lund S.","unstructured":"Fr\u00f8lund , S. Merchant , A. , Saito , Y. , Spence , S. , and Veitch , A . 2004. A decentralized algorithm for erasure-coded virtual disks . In Proceedings of the Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN'04) , 125--134. Fr\u00f8lund, S. Merchant, A., Saito, Y., Spence, S., and Veitch, A. 2004. A decentralized algorithm for erasure-coded virtual disks. In Proceedings of the Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN'04), 125--134."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1962.1057683"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN'04)","author":"Goodson G. R.","unstructured":"Goodson , G. R. , Wylie , J. J. , Granger , G. R. , and Reiter , M. K . 2004. Efficient Byzantine-tolerant erasure-coded storage . In Proceedings of the Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN'04) , 135--144. Goodson, G. R., Wylie, J. J., Granger, G. R., and Reiter, M. K. 2004. Efficient Byzantine-tolerant erasure-coded storage. In Proceedings of the Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN'04), 135--144."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 38th Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN'08)","author":"Greenan K. M.","unstructured":"Greenan , K. M. , Miller , E. L. , and Wylie , J. J . 2008. Reliability of flat XOR-based erasure codes on heterogeneous devices . In Proceedings of the 38th Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN'08) . IEEE Computer Society, 147--156. Greenan, K. M., Miller, E. L., and Wylie, J. J. 2008. Reliability of flat XOR-based erasure codes on heterogeneous devices. In Proceedings of the 38th Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN'08). IEEE Computer Society, 147--156."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2006.40"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 4th USENIX Conference on File and Storage Technologies (FAST'05)","author":"Hafner J. L.","year":"2005","unstructured":"Hafner , J. L. 2005 . Weaver codes: Highly fault tolerant erasure codes for storage systems . In Proceedings of the 4th USENIX Conference on File and Storage Technologies (FAST'05) . USENIX Association, 211--224. Hafner, J. L. 2005. Weaver codes: Highly fault tolerant erasure codes for storage systems. In Proceedings of the 4th USENIX Conference on File and Storage Technologies (FAST'05). USENIX Association, 211--224."},{"key":"e_1_2_1_19_1","unstructured":"Hafner J. L. Deenadhayalan V. Kanungo T. and Rao K. K. 2004. Performance metrics for erasure codes in storage systems. Tech. rep. RJ 10321 (A0408-003). IBM Research Division Almaden Research Center. August.  Hafner J. L. Deenadhayalan V. Kanungo T. and Rao K. K. 2004. Performance metrics for erasure codes in storage systems. Tech. rep. RJ 10321 (A0408-003). IBM Research Division Almaden Research Center. August."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 4th USENIX Conference on File and Storage Technologies (FAST'05)","author":"Huang C.","unstructured":"Huang , C. and Xu , L . 2005. Star: An efficient coding scheme for correcting triple storage node failures . In Proceedings of the 4th USENIX Conference on File and Storage Technologies (FAST'05) . USENIX Association. Huang, C. and Xu, L. 2005. Star: An efficient coding scheme for correcting triple storage node failures. In Proceedings of the 4th USENIX Conference on File and Storage Technologies (FAST'05). USENIX Association."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.910575"},{"key":"e_1_2_1_22_1","unstructured":"MacWilliams F. J. and Sloane N. J. A. 1977. The Theory of Error-Correcting Codes. North-Holland New York.  MacWilliams F. J. and Sloane N. J. A. 1977. The Theory of Error-Correcting Codes. North-Holland New York."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 5th USENIX Conference on File and Storage Technologies (FAST'07)","author":"Pinheiro E.","unstructured":"Pinheiro , E. , Weber , W. D. , and Barroso , L. A . 2007. Failure trends in a large disk drive population . In Proceedings of the 5th USENIX Conference on File and Storage Technologies (FAST'07) . USENIX Association, 17--29. Pinheiro, E., Weber, W. D., and Barroso, L. A. 2007. Failure trends in a large disk drive population. In Proceedings of the 5th USENIX Conference on File and Storage Technologies (FAST'07). USENIX Association, 17--29."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1364813.1364820"},{"key":"e_1_2_1_25_1","volume-title":"Erasure codes for storage applications. Tutorial slides presented at the 4th USENIX Conference on File and Storage Technologies (FAST'05)","author":"Plank J. S.","unstructured":"Plank , J. S. 2005. Erasure codes for storage applications. Tutorial slides presented at the 4th USENIX Conference on File and Storage Technologies (FAST'05) . http:\/\/www.cs.utk.edu\/~plank\/plank\/papers\/FAST-2005.html. Plank, J. S. 2005. Erasure codes for storage applications. Tutorial slides presented at the 4th USENIX Conference on File and Storage Technologies (FAST'05). http:\/\/www.cs.utk.edu\/~plank\/plank\/papers\/FAST-2005.html."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN'04)","author":"Plank J. S.","unstructured":"Plank , J. S. and Thomason , M. G . 2004. A practical analysis of low-density parity-check erasure codes for wide-area storage applications . In Proceedings of the Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN'04) . IEEE Computer Society. Plank, J. S. and Thomason, M. G. 2004. A practical analysis of low-density parity-check erasure codes for wide-area storage applications. In Proceedings of the Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN'04). IEEE Computer Society."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/NCA.2006.43"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2005.86"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0108018"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.45291"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/366853.366878"},{"key":"e_1_2_1_32_1","unstructured":"Schroeder B. and Gibson G. A. 2007. Disk failures in the real world: What does an MTTF of 1 000 000 hours mean to you&quest; In Proceedings of the 5th USENIX Conference on File and Storage Technologies (FAST'07). USENIX Association 1--16.   Schroeder B. and Gibson G. A. 2007. Disk failures in the real world: What does an MTTF of 1 000 000 hours mean to you&quest; In Proceedings of the 5 th USENIX Conference on File and Storage Technologies (FAST'07). USENIX Association 1--16."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1981.1056404"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.502.0181"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the IEEE International Symposium on Information Theory (ISIT'01)","author":"Wong T. E.","unstructured":"Wong , T. E. and Shea , J. M . 2001. Multi-Dimensional parity check codes for bursty channels . In Proceedings of the IEEE International Symposium on Information Theory (ISIT'01) , 123. Wong, T. E. and Shea, J. M. 2001. Multi-Dimensional parity check codes for bursty channels. In Proceedings of the IEEE International Symposium on Information Theory (ISIT'01), 123."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2007.32"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1362622.1362682"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.746809"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1480439.1480444","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1480439.1480444","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:59Z","timestamp":1750253399000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1480439.1480444"}},"subtitle":["Strip-based erasure codes with high fault tolerance for storage systems"],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1145\/1480439.1480444"],"URL":"https:\/\/doi.org\/10.1145\/1480439.1480444","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]},"assertion":[{"value":"2007-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}