We give efficient algorithms for distributed computation on oriented, anonymous, asynchronous hypercubes with possible faulty components (i.e. processors and links) and deterministic processors. Initially, the processors know only the size of the network and that they are inter-connected in a hypercube topology. 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 bit cost O(Nδn(γ)2λ log log N), where γ is the number of faulty components (i.e. links plus processors), λ is the number of links which are either faulty, or non-faulty but adjacent to faulty processors, and δn(γ) is the diameter of the hypercube with γ faulty components.

, , , ,
Distributed Computing
School of Computer Science

Kranakis, E, & Santoro, N. (2001). Distributed computing on oriented anonymous hypercubes with faulty components. Distributed Computing, 14(3), 185–189.