Optimal Time Broadcasting Schemes in Faulty Star Graphs

Aohan MEI, Feng BAO, Yukihiro HAMADA, Yoshihide IGARASHI

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.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.5 pp.722-732
• Publication Date: 1999/05/25
• Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Authors

Aohan MEI
Feng BAO
Yukihiro HAMADA
Yoshihide IGARASHI

Keyword

broadcasting,  Byzantine faults,  crash faults,  fault tolerance,  star graph