Optimal Time Broadcasting Schemes in Faulty Star Graphs

Aohan MEI  Feng BAO  Yukihiro HAMADA  Yoshihide IGARASHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E82-A   No.5   pp.722-732
Publication Date: 1999/05/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
broadcasting,  Byzantine faults,  crash faults,  fault tolerance,  star graph,  

Full Text: PDF>>
Buy this Article




Summary: 
We propose two fault-tolerant broadcasting schemes in star graphs. One of the schemes can tolerate up to n2 faults of the crash type in the n-star graph. The other scheme can tolerate up to (n3d1)/2 faults of the Byzantine type in the n-star graph, where d is the smallest positive integer satisfying nd!. Each of the schemes is designed for the single-port mode, and it completes the broadcasting in O(n log n) time. These schemes are time optimal. For the former scheme we analyze the reliability in the case where faults of the crash type are randomly distributed. It can tolerate (n!)α faults randomly distributed in the n-star graph with a high probability, where α is any constant less than 1.