Carleton University
Technical Report TR-207
April 1992
Distributed Computing on Anonymous Hypercubes with Faulty Components
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 identical protocols given identical data. Initially, they know only the size of the network (in this instance, a power of 2) and that they are interconnected in a hypercube network. Faults may occur only before the start of the computation (and that despite this the hypercube remains a connected 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.