{"id":15044,"date":"2022-06-16T20:14:01","date_gmt":"2022-06-17T00:14:01","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=15044"},"modified":"2026-06-09T09:53:21","modified_gmt":"2026-06-09T13:53:21","slug":"tr-207-distributed-computing-on-anonymous-hypercubes-with-faulty-components","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1992\/tr-207-distributed-computing-on-anonymous-hypercubes-with-faulty-components\/","title":{"rendered":"TR-207: Distributed Computing on Anonymous Hypercubes with Faulty Components"},"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-207: Distributed Computing on Anonymous Hypercubes with Faulty Components\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n\n\n<p>Carleton University<br><a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1992\/\">Technical Report<\/a>&nbsp;<strong>TR-207<\/strong><br>April 1992<\/p>\n\n\n\n<h2 id=\"distributed-computing-on-anonymous-hypercubes-with-faulty-components\" class=\"wp-block-heading\">Distributed Computing on Anonymous Hypercubes with Faulty Components<\/h2>\n\n\n\n<p>Evangelos Kranakis &amp; Nicola Santoro<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>We give efficient algorithms for distributed computation on anonymous, labeled, asynchronous hypercubes with possible faulty components (i.e. processors and links). The processors are deterministic and execute iden\u00adtical protocols given identical data. Initially, they know only the size of the network (in this instance, a power of 2) and that they are inter\u00adconnected in a hypercube network. Faults may occur only before the start of the computation (and that despite this the hypercube remains a con\u00adnected network). However the processors do not know where these faults are located. As a measure of complexity we use the total number of bits transmitted during the execution of the algorithm and we concentrate on giving algorithms that will minimize this number of bits. The main result of this paper is an algorithm for computing boolean functions on anonymous hypercubes with at most ; faulty components, ; ?: 1, with bit complexity O(N6n(;}2 .2 log log N), where ; is the number of faulty components, of which .A is the number of faulty links, and 6n (\u2018Y) is the diameter of the hypercube.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-207.pdf\">TR-207.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-207April 1992 Distributed Computing on Anonymous Hypercubes with Faulty Components Evangelos Kranakis &amp; Nicola Santoro Abstract We give efficient algorithms for distributed computation on anonymous, labeled, asynchronous hypercubes with possible faulty components (i.e. processors and links). The processors are deterministic and execute iden\u00adtical protocols given identical data. Initially, they know only the size [&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-15044","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15044","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=15044"}],"version-history":[{"count":3,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15044\/revisions"}],"predecessor-version":[{"id":24503,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15044\/revisions\/24503"}],"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=15044"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=15044"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}