Distributed computing on oriented anonymous hypercubes with faulty components

We give efficient algorithms for distributed computation on oriented, anony mous, asynchronous hypercubes with possible faulty components (i.e. process ors and links) and deterministic processors. Initially, the processors know only the size of the network and that they are inter-connected in a hyperc ube topology. Faults may occur only before the start of the computation (an d that despite this the hypercube remains a connected network). However, th e processors do not know where these faults are located. As a measure of co mplexity we use the total number of bits transmitted during the execution o f 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 comp uting, Boolean functions on anonymous hypercubes with bit cost O(N delta (n )(gamma)(2)lambda log log N), where gamma is the number of faulty component s (i.e. links plus processors), lambda is the number of links which are eit her faulty, or non-faulty but adjacent to faulty processors, and delta (n) (gamma) is the diameter of the hypercube with gamma faulty components.