Loading…
Optimal Rebuilding of Multiple Erasures in MDS Codes
Maximum distance separable (MDS) array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with r redundancy nodes can correct any r node erasures by accessing (reading) all the remaining information in the surviving nodes. Ho...
Saved in:
| Published in: | IEEE transactions on information theory 2017-02, Vol.63 (2), p.1084-1101 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c361t-bc54101a05c5e62e21f369388c6286770774254facc08c9e814cd3d7ae31fbd53 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c361t-bc54101a05c5e62e21f369388c6286770774254facc08c9e814cd3d7ae31fbd53 |
| container_end_page | 1101 |
| container_issue | 2 |
| container_start_page | 1084 |
| container_title | IEEE transactions on information theory |
| container_volume | 63 |
| creator | Zhiying Wang Tamo, Itzhak Bruck, Jehoshua |
| description | Maximum distance separable (MDS) array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with r redundancy nodes can correct any r node erasures by accessing (reading) all the remaining information in the surviving nodes. However, in practice, e erasures are a more likely failure event, for some 1 ≤ e |
| doi_str_mv | 10.1109/TIT.2016.2633411 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_1861301927</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>7762203</ieee_id><sourcerecordid>2174326323</sourcerecordid><originalsourceid>FETCH-LOGICAL-c361t-bc54101a05c5e62e21f369388c6286770774254facc08c9e814cd3d7ae31fbd53</originalsourceid><addsrcrecordid>eNp9kE1Lw0AQhhdRsFbvgpcFz6k7-52jxKqFloLW85JuJpISm7ibHPz3bmnx6GkYeN4Z3oeQW2AzAJY_bBabGWegZ1wLIQHOyASUMlmulTwnE8bAZrmU9pJcxbhLq1TAJ0Su-6H5Klv6htuxaatm_0m7mq7Gdmj6Fuk8lHEMGGmzp6und1p0FcZrclGXbcSb05ySj-f5pnjNluuXRfG4zLzQMGRbryQwKJnyCjVHDrXQubDWa261McwYyZWsS--Z9TlakL4SlSlRQL2tlJiS--PdPnTfI8bB7box7NNLx8FIkapy8R8FVoNgkHOTKHakfOhiDFi7PqTi4ccBcweDLhl0B4PuZDBF7o6RBhH_cGM050yIXyvfaPE</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1861301927</pqid></control><display><type>article</type><title>Optimal Rebuilding of Multiple Erasures in MDS Codes</title><source>IEEE Xplore (Online service)</source><creator>Zhiying Wang ; Tamo, Itzhak ; Bruck, Jehoshua</creator><creatorcontrib>Zhiying Wang ; Tamo, Itzhak ; Bruck, Jehoshua</creatorcontrib><description>Maximum distance separable (MDS) array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with r redundancy nodes can correct any r node erasures by accessing (reading) all the remaining information in the surviving nodes. However, in practice, e erasures are a more likely failure event, for some 1 ≤ e <; r. Hence, a natural question is how much information do we need to access in order to rebuild e storage nodes. We define the rebuilding ratio as the fraction of remaining information accessed during the rebuilding of e erasures. In our previous work, we constructed MDS codes, called zigzag codes, that achieve the optimal rebuilding ratio of 1/r for the rebuilding of any systematic node when e = 1; however, all the information needs to be accessed for the rebuilding of the parity node erasure. The (normalized) repair bandwidth is defined as the fraction of information transmitted from the remaining nodes during the rebuilding process. For codes that are not necessarily MDS, Dimakis et al. proposed the regenerating codes framework where any r erasures can be corrected by accessing some of the remaining information, and any e = 1 erasure can be rebuilt from some subsets of surviving nodes with optimal repair bandwidth. In this paper, we present three results on rebuilding of codes: 1) we show a fundamental outer bound on the storage size of the node and the repair bandwidth similar to the regenerating codes framework, and show that zigzag codes achieve the optimal rebuilding ratio of e/r for systematic nodes of MDS codes, for any 1 ≤ e r; 2) we construct systematic codes that achieve optimal rebuilding ratio of 1/r, for any systematic or parity node erasure; and 3) we present error correction algorithms for zigzag codes, and in particular demonstrate how these codes can be corrected beyond their minimum Hamming distances.</description><identifier>ISSN: 0018-9448</identifier><identifier>EISSN: 1557-9654</identifier><identifier>DOI: 10.1109/TIT.2016.2633411</identifier><identifier>CODEN: IETTAW</identifier><language>eng</language><publisher>New York: IEEE</publisher><subject>Algorithms ; Arrays ; Bandwidth ; Bandwidths ; correcting erasures and errors ; Decoding ; Distributed storage ; Electronic mail ; Encoding ; Error correction ; Error correction & detection ; Information storage ; Information theory ; Maintenance engineering ; multiple erasures ; Nodes ; Parity ; Rebuilding ; Redundancy ; regenerating codes ; Repair ; Storage systems ; Systematics ; Two dimensional displays</subject><ispartof>IEEE transactions on information theory, 2017-02, Vol.63 (2), p.1084-1101</ispartof><rights>Copyright The Institute of Electrical and Electronics Engineers, Inc. (IEEE) Feb 2017</rights><rights>Copyright The Institute of Electrical and Electronics Engineers, Inc. (IEEE) 2017</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c361t-bc54101a05c5e62e21f369388c6286770774254facc08c9e814cd3d7ae31fbd53</citedby><cites>FETCH-LOGICAL-c361t-bc54101a05c5e62e21f369388c6286770774254facc08c9e814cd3d7ae31fbd53</cites><orcidid>0000-0003-3339-3085</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/7762203$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>314,780,784,27924,27925,54796</link.rule.ids></links><search><creatorcontrib>Zhiying Wang</creatorcontrib><creatorcontrib>Tamo, Itzhak</creatorcontrib><creatorcontrib>Bruck, Jehoshua</creatorcontrib><title>Optimal Rebuilding of Multiple Erasures in MDS Codes</title><title>IEEE transactions on information theory</title><addtitle>TIT</addtitle><description>Maximum distance separable (MDS) array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with r redundancy nodes can correct any r node erasures by accessing (reading) all the remaining information in the surviving nodes. However, in practice, e erasures are a more likely failure event, for some 1 ≤ e <; r. Hence, a natural question is how much information do we need to access in order to rebuild e storage nodes. We define the rebuilding ratio as the fraction of remaining information accessed during the rebuilding of e erasures. In our previous work, we constructed MDS codes, called zigzag codes, that achieve the optimal rebuilding ratio of 1/r for the rebuilding of any systematic node when e = 1; however, all the information needs to be accessed for the rebuilding of the parity node erasure. The (normalized) repair bandwidth is defined as the fraction of information transmitted from the remaining nodes during the rebuilding process. For codes that are not necessarily MDS, Dimakis et al. proposed the regenerating codes framework where any r erasures can be corrected by accessing some of the remaining information, and any e = 1 erasure can be rebuilt from some subsets of surviving nodes with optimal repair bandwidth. In this paper, we present three results on rebuilding of codes: 1) we show a fundamental outer bound on the storage size of the node and the repair bandwidth similar to the regenerating codes framework, and show that zigzag codes achieve the optimal rebuilding ratio of e/r for systematic nodes of MDS codes, for any 1 ≤ e r; 2) we construct systematic codes that achieve optimal rebuilding ratio of 1/r, for any systematic or parity node erasure; and 3) we present error correction algorithms for zigzag codes, and in particular demonstrate how these codes can be corrected beyond their minimum Hamming distances.</description><subject>Algorithms</subject><subject>Arrays</subject><subject>Bandwidth</subject><subject>Bandwidths</subject><subject>correcting erasures and errors</subject><subject>Decoding</subject><subject>Distributed storage</subject><subject>Electronic mail</subject><subject>Encoding</subject><subject>Error correction</subject><subject>Error correction & detection</subject><subject>Information storage</subject><subject>Information theory</subject><subject>Maintenance engineering</subject><subject>multiple erasures</subject><subject>Nodes</subject><subject>Parity</subject><subject>Rebuilding</subject><subject>Redundancy</subject><subject>regenerating codes</subject><subject>Repair</subject><subject>Storage systems</subject><subject>Systematics</subject><subject>Two dimensional displays</subject><issn>0018-9448</issn><issn>1557-9654</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2017</creationdate><recordtype>article</recordtype><recordid>eNp9kE1Lw0AQhhdRsFbvgpcFz6k7-52jxKqFloLW85JuJpISm7ibHPz3bmnx6GkYeN4Z3oeQW2AzAJY_bBabGWegZ1wLIQHOyASUMlmulTwnE8bAZrmU9pJcxbhLq1TAJ0Su-6H5Klv6htuxaatm_0m7mq7Gdmj6Fuk8lHEMGGmzp6und1p0FcZrclGXbcSb05ySj-f5pnjNluuXRfG4zLzQMGRbryQwKJnyCjVHDrXQubDWa261McwYyZWsS--Z9TlakL4SlSlRQL2tlJiS--PdPnTfI8bB7box7NNLx8FIkapy8R8FVoNgkHOTKHakfOhiDFi7PqTi4ccBcweDLhl0B4PuZDBF7o6RBhH_cGM050yIXyvfaPE</recordid><startdate>20170201</startdate><enddate>20170201</enddate><creator>Zhiying Wang</creator><creator>Tamo, Itzhak</creator><creator>Bruck, Jehoshua</creator><general>IEEE</general><general>The Institute of Electrical and Electronics Engineers, Inc. (IEEE)</general><scope>97E</scope><scope>RIA</scope><scope>RIE</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7SP</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0003-3339-3085</orcidid></search><sort><creationdate>20170201</creationdate><title>Optimal Rebuilding of Multiple Erasures in MDS Codes</title><author>Zhiying Wang ; Tamo, Itzhak ; Bruck, Jehoshua</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c361t-bc54101a05c5e62e21f369388c6286770774254facc08c9e814cd3d7ae31fbd53</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2017</creationdate><topic>Algorithms</topic><topic>Arrays</topic><topic>Bandwidth</topic><topic>Bandwidths</topic><topic>correcting erasures and errors</topic><topic>Decoding</topic><topic>Distributed storage</topic><topic>Electronic mail</topic><topic>Encoding</topic><topic>Error correction</topic><topic>Error correction & detection</topic><topic>Information storage</topic><topic>Information theory</topic><topic>Maintenance engineering</topic><topic>multiple erasures</topic><topic>Nodes</topic><topic>Parity</topic><topic>Rebuilding</topic><topic>Redundancy</topic><topic>regenerating codes</topic><topic>Repair</topic><topic>Storage systems</topic><topic>Systematics</topic><topic>Two dimensional displays</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Zhiying Wang</creatorcontrib><creatorcontrib>Tamo, Itzhak</creatorcontrib><creatorcontrib>Bruck, Jehoshua</creatorcontrib><collection>IEEE All-Society Periodicals Package (ASPP) 2005-present</collection><collection>IEEE All-Society Periodicals Package (ASPP) 1998-Present</collection><collection>IEEE Xplore</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Electronics & Communications Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>IEEE transactions on information theory</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Zhiying Wang</au><au>Tamo, Itzhak</au><au>Bruck, Jehoshua</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Optimal Rebuilding of Multiple Erasures in MDS Codes</atitle><jtitle>IEEE transactions on information theory</jtitle><stitle>TIT</stitle><date>2017-02-01</date><risdate>2017</risdate><volume>63</volume><issue>2</issue><spage>1084</spage><epage>1101</epage><pages>1084-1101</pages><issn>0018-9448</issn><eissn>1557-9654</eissn><coden>IETTAW</coden><abstract>Maximum distance separable (MDS) array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with r redundancy nodes can correct any r node erasures by accessing (reading) all the remaining information in the surviving nodes. However, in practice, e erasures are a more likely failure event, for some 1 ≤ e <; r. Hence, a natural question is how much information do we need to access in order to rebuild e storage nodes. We define the rebuilding ratio as the fraction of remaining information accessed during the rebuilding of e erasures. In our previous work, we constructed MDS codes, called zigzag codes, that achieve the optimal rebuilding ratio of 1/r for the rebuilding of any systematic node when e = 1; however, all the information needs to be accessed for the rebuilding of the parity node erasure. The (normalized) repair bandwidth is defined as the fraction of information transmitted from the remaining nodes during the rebuilding process. For codes that are not necessarily MDS, Dimakis et al. proposed the regenerating codes framework where any r erasures can be corrected by accessing some of the remaining information, and any e = 1 erasure can be rebuilt from some subsets of surviving nodes with optimal repair bandwidth. In this paper, we present three results on rebuilding of codes: 1) we show a fundamental outer bound on the storage size of the node and the repair bandwidth similar to the regenerating codes framework, and show that zigzag codes achieve the optimal rebuilding ratio of e/r for systematic nodes of MDS codes, for any 1 ≤ e r; 2) we construct systematic codes that achieve optimal rebuilding ratio of 1/r, for any systematic or parity node erasure; and 3) we present error correction algorithms for zigzag codes, and in particular demonstrate how these codes can be corrected beyond their minimum Hamming distances.</abstract><cop>New York</cop><pub>IEEE</pub><doi>10.1109/TIT.2016.2633411</doi><tpages>18</tpages><orcidid>https://orcid.org/0000-0003-3339-3085</orcidid><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0018-9448 |
| ispartof | IEEE transactions on information theory, 2017-02, Vol.63 (2), p.1084-1101 |
| issn | 0018-9448 1557-9654 |
| language | eng |
| recordid | cdi_proquest_journals_1861301927 |
| source | IEEE Xplore (Online service) |
| subjects | Algorithms Arrays Bandwidth Bandwidths correcting erasures and errors Decoding Distributed storage Electronic mail Encoding Error correction Error correction & detection Information storage Information theory Maintenance engineering multiple erasures Nodes Parity Rebuilding Redundancy regenerating codes Repair Storage systems Systematics Two dimensional displays |
| title | Optimal Rebuilding of Multiple Erasures in MDS Codes |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-02T03%3A08%3A51IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Optimal%20Rebuilding%20of%20Multiple%20Erasures%20in%20MDS%20Codes&rft.jtitle=IEEE%20transactions%20on%20information%20theory&rft.au=Zhiying%20Wang&rft.date=2017-02-01&rft.volume=63&rft.issue=2&rft.spage=1084&rft.epage=1101&rft.pages=1084-1101&rft.issn=0018-9448&rft.eissn=1557-9654&rft.coden=IETTAW&rft_id=info:doi/10.1109/TIT.2016.2633411&rft_dat=%3Cproquest_cross%3E2174326323%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c361t-bc54101a05c5e62e21f369388c6286770774254facc08c9e814cd3d7ae31fbd53%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1861301927&rft_id=info:pmid/&rft_ieee_id=7762203&rfr_iscdi=true |