
For FullText 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.

Broadcasting in Hypercubes with Randomly Distributed Byzantine Faults
Feng BAO Yoshihide IGARASHI Keiko KATANO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E78A
No.9
pp.12391246 Publication Date: 1995/09/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: PAPER Category: Reliability and Fault Analysis Keyword: hypercubes, broadcasting, faulttolerance, random faults, Byzantine faults,
Full Text: PDF>>
Summary:
We study alltoall broadcasting in hypercubes with randomly distributed Byzantine faults. We construct an efficient broadcasting scheme BC1ncube running on the ndimensional hypercube (ncube for short) in 2n rounds, where for communication by each node of the ncube, only one of its links is used in each round. The scheme BC1ncube can tolerate (n1)/2 Byzantine faults of nodes and/or links in the worst case. If there are exactly f Byzantine faulty nodes randomly distributed in the ncabe, BC1ncube succeeds with a probability higher than 1(64nf/2^{n}) ^{n/2}. In other words, if 1/(64nk) of all the nodes(i.e., 2^{n}/(64nk) nodes) fail in Byzantine manner randomly in the ncube, then the scheme succeeds with a probability higher than 1k^{n/2}. We also consider the case where all nodes are faultless but links may fail randomly in the ncube. Broadcasting by BC1ncube is successful with a probability hig her than 1k^{n/2} provided that not more than 1/(64(n1)k) of all the links in the ncube fail in Byzantine manner randomly. For the case where only links may fail, we give another broadcasting scheme BC2ncube which runs in 2n^{2} rounds. Broadcasting by BC2ncube is successful with a high probability if the number of Byzantine faulty links randomly distributed in the ncube is not more than a constant fraction of the total number of links. That is, it succeeds with a probability higher than 1nk^{n/2} if 1/(48k) of all the links in the ncube fail randomly in Byzantine manner.

