Optimal Schemes for Disseminating Information and Their Fault Tolerance

Yoshihide IGARASHI  Kumiko KANAI  Kinya MIURA  Shingo OSAWA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.1   pp.22-29
Publication Date: 1992/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Theoretical Foundations of Computing)
Category: 
Keyword: 
broadcasting,  graphs,  networks,  fault tolerance,  information dissemination,  

Full Text: PDF(747.3KB)>>
Buy this Article




Summary: 
We describe two information disseminating schemes, t-disseminate and t-Rdisseminate in a computer network with N processors, where each processor can send a message to t-directions at each round. If no processors have failed, these schemes are time optimal. When at most t processors have failed, for t1 and t2 any of these schemes can broadcast information within any consecutive logt+1N2 rounds, and for an arbitrary t they can broadcast information within any consecutive logt+1N3 rounds.