{"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":"2022-06-16T20:14:01","modified_gmt":"2022-06-17T00:14:01","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":"

Carleton University
\nTechnical Report<\/a> TR-207<\/strong>
\nApril 1992<\/p>\n

Distributed Computing on Anonymous Hypercubes with Faulty Components<\/h2>\n
Evangelos Kranakis & Nicola Santoro<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n

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 (‘Y) is the diameter of the hypercube.<\/p>\n

<\/div>\n

TR-207.pdf<\/a><\/p>\n