Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer SciencesVol.E82-ANo.5pp.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>>
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.