Information Disseminating Schemes for Fault Tolerance in Hypercubes

Svante CARLSSON  Yoshihide IGARASHI  Kumiko KANAI  Andrzej LINGAS  Kinya MIURA  Ola PETERSSON  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E75-A   No.2   pp.255-260
Publication Date: 1992/02/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs, Networks and Matroids
broadcasting, distributed systems,  fault tolerance,  hypercubes,  networks,  porallel processing,  

Full Text: PDF>>
Buy this Article

We present schemes for disseminating information in the n-dimensional hypercube with some faulty nodes/edges. If each processor can send a message to t neighbors at each round, and if the number of faulty nodes/edges is k(kn), then this scheme will broadcast information from any source to all destinations within any consecutive n+[(k+l)/t] rounds. We also discuss the case where the number of faulty nodes is not less than n.