For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Optimal Schemes for Disseminating Information and Their Fault Tolerance
Yoshihide IGARASHI Kumiko KANAI Kinya MIURA Shingo OSAWA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1992/01/25
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Theoretical Foundations of Computing)
broadcasting, graphs, networks, fault tolerance, information dissemination,
Full Text: PDF>>
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.