Defect tolerance: fundamental limits and examples
This paper addresses the problem of adding redundancy to a collection of physical objects so that the overall system is more robust to failures. In contrast to its information counterpart, which can exploit parity to protect multiple information symbols from a single erasure, physical redundancy can...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2020
|
| Online Access: | https://hdl.handle.net/1721.1/124983 |
| _version_ | 1826191313398136832 |
|---|---|
| author | Tang, Jennifer Susan Wang, Da Polyanskiy, Yury Wornell, Gregory |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Tang, Jennifer Susan Wang, Da Polyanskiy, Yury Wornell, Gregory |
| author_sort | Tang, Jennifer Susan |
| collection | MIT |
| description | This paper addresses the problem of adding redundancy to a collection of physical objects so that the overall system is more robust to failures. In contrast to its information counterpart, which can exploit parity to protect multiple information symbols from a single erasure, physical redundancy can only be realized through duplication and substitution of objects. We propose a bipartite graph model for designing defect-tolerant systems, in which the defective objects are replaced by the judiciously connected redundant objects. The fundamental limits of this model are characterized under various asymptotic settings and both asymptotic and finite-size systems that approach these limits are constructed. Among other results, we show that the simple modular redundancy is in general suboptimal. As we develop, this combinatorial problem of defect tolerant system design has a natural interpretation as one of graph coloring, and the analysis is significantly different from that traditionally used in information redundancy for error-control codes.©2018 |
| first_indexed | 2024-09-23T08:53:58Z |
| format | Article |
| id | mit-1721.1/124983 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:53:58Z |
| publishDate | 2020 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1249832022-09-26T09:04:00Z Defect tolerance: fundamental limits and examples Tang, Jennifer Susan Wang, Da Polyanskiy, Yury Wornell, Gregory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science This paper addresses the problem of adding redundancy to a collection of physical objects so that the overall system is more robust to failures. In contrast to its information counterpart, which can exploit parity to protect multiple information symbols from a single erasure, physical redundancy can only be realized through duplication and substitution of objects. We propose a bipartite graph model for designing defect-tolerant systems, in which the defective objects are replaced by the judiciously connected redundant objects. The fundamental limits of this model are characterized under various asymptotic settings and both asymptotic and finite-size systems that approach these limits are constructed. Among other results, we show that the simple modular redundancy is in general suboptimal. As we develop, this combinatorial problem of defect tolerant system design has a natural interpretation as one of graph coloring, and the analysis is significantly different from that traditionally used in information redundancy for error-control codes.©2018 2020-05-01T19:26:05Z 2020-05-01T19:26:05Z 2018-07 2019-07-01T17:51:37Z Article http://purl.org/eprint/type/JournalArticle 1557-9654 0018-9448 https://hdl.handle.net/1721.1/124983 Tang, Jennifer Susan, Da Wang, Yury Polyanskiy, and Gregory Wornell, "Defect tolerance: fundamental limits and examples." IEEE Transactions on Information Theory 64, 7 (July 2018): p. 5240-60 doi 10.1109/TIT.2017.2771417 ©2018 Author(s) en 10.1109/TIT.2017.2771417 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Tang, Jennifer Susan Wang, Da Polyanskiy, Yury Wornell, Gregory Defect tolerance: fundamental limits and examples |
| title | Defect tolerance: fundamental limits and examples |
| title_full | Defect tolerance: fundamental limits and examples |
| title_fullStr | Defect tolerance: fundamental limits and examples |
| title_full_unstemmed | Defect tolerance: fundamental limits and examples |
| title_short | Defect tolerance: fundamental limits and examples |
| title_sort | defect tolerance fundamental limits and examples |
| url | https://hdl.handle.net/1721.1/124983 |
| work_keys_str_mv | AT tangjennifersusan defecttolerancefundamentallimitsandexamples AT wangda defecttolerancefundamentallimitsandexamples AT polyanskiyyury defecttolerancefundamentallimitsandexamples AT wornellgregory defecttolerancefundamentallimitsandexamples |