{"id":15038,"date":"2022-06-16T20:06:32","date_gmt":"2022-06-17T00:06:32","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=15038"},"modified":"2026-06-09T09:57:38","modified_gmt":"2026-06-09T13:57:38","slug":"tr-204-recognition-of-catastrophic-faults-in-reconfigurable-arrays-with-arbitrary-link-redundancy","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1992\/tr-204-recognition-of-catastrophic-faults-in-reconfigurable-arrays-with-arbitrary-link-redundancy\/","title":{"rendered":"TR-204: Recognition of Catastrophic Faults in Reconfigurable Arrays with Arbitrary Link Redundancy"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-204: Recognition of Catastrophic Faults in Reconfigurable Arrays with Arbitrary Link Redundancy\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n\n\n<p class=\"wp-block-paragraph\">ÐÓ°ÉÔ­´´ University<br><a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1992\/\">Technical Report<\/a>&nbsp;<strong>TR-204<\/strong><br>March 1992<\/p>\n\n\n\n<h2 id=\"recognition-of-catastrophic-faults-in-reconfigurable-arrays-with-arbitrary-link-redundancy\" class=\"wp-block-heading\">Recognition of Catastrophic Faults in Reconfigurable Arrays with Arbitrary Link Redundancy<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Amiya Nayak, Linda Pagli, Nicola Santoro<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Fault tolerance through the incorporation of redundancy and reconfiguration is quite common. The distribution of faults can have severe impact on the effectiveness of any reconfiguration scheme; in fact, patterns of faults occurring at strategic locations may render an entire system unusable regardless of its component redundancy and of its reconfiguration capabilities. The characterization of such patterns is crucial for the identification and detection of such catastrophic events. A complete characterization was given for reconfigurable systolic arrays with 2-link redundancy; i.e., a bypass link of fixed length is provided to each element of the array in addition to the regular link. In this paper, we study the more general case of arbitrary (but regular) link re\u00addundancy. In particular, we focus on the problem of deciding whether a pattern of k faults is catastrophic for a k-link redundant system; i.e., in addition to the regular link of length g1 = 1, each element of the array is provided with k-1 bypass links of length. g2, g3, \u2026 , 9k, respectively.<br>We study this problem and prove some fundamental properties which any catas\u00adtrophic fault pattern must satisfy. We then show that these properties together consti\u00adtute a necessary and sufficient condition for a fault pattern to be catastrophic for k-link redundant system. As a consequence, we derive a provably correct recognition algo\u00adrithm whose worse-case time complexity is O(kgk)i this also improves on the previous algorithm for k = 2.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-204.pdf\">TR-204.pdf<\/a><\/p>\n\n\n","protected":false},"excerpt":{"rendered":"<p>ÐÓ°ÉÔ­´´ UniversityTechnical Report&nbsp;TR-204March 1992 Recognition of Catastrophic Faults in Reconfigurable Arrays with Arbitrary Link Redundancy Amiya Nayak, Linda Pagli, Nicola Santoro Abstract Fault tolerance through the incorporation of redundancy and reconfiguration is quite common. The distribution of faults can have severe impact on the effectiveness of any reconfiguration scheme; in fact, patterns of faults occurring [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11910,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-15038","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15038","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=15038"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15038\/revisions"}],"predecessor-version":[{"id":24508,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15038\/revisions\/24508"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11910"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=15038"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=15038"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}