Distributed computing on oriented anonymous hypercubes with faulty components |
| |
Authors: | Evangelos Kranakis Nicola Santoro |
| |
Affiliation: | (1) School of Computer Science, Carleton University, K1S 5B6, Ottawa, Ontario, Canada (e-mail: {kranakis,santoro}@scs.carleton.ca) , CA |
| |
Abstract: | 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 , 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 is the diameter of the hypercube with faulty components.
Received: October 1992 / Accepted: April 2001 |
| |
Keywords: | : Anonymous networks – Boolean functions – Computability – Hypercubes – Faulty links and/or nodes |
本文献已被 SpringerLink 等数据库收录! |
|