BROADCASTING IN HYPERCUBES WITH RANDOMLY DISTRIBUTED BYZANTINE FAULTS

We study all-to-all broadcasting in hypercubes with randomly distribut ed Byzantine faults. We construct an efficient broadcasting scheme BC1 -n-cube running on the n-dimensional hypercube (n-cube for short) in 2 n rounds, where for communication by each node of the n-cube, only one of its links is used in each round. The scheme BC1-n-cube can tolerat e [(n-1)/2] Byzantine faults of nodes and/or links in the worst case. If there are exactly f Byzantine faulty nodes randomly distributed in the n-cube, BC1-n-cube succeeds with a probability higher than 1 - (64 nf/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 n-cube, the n the scheme succeeds with a probability higher than 1 - k(-)[(n/2)]. We also consider the case where all nodes are faultless but links may fail randomly in the n-cube. Broadcasting by BC1-n-cube is successful with a probability higher than 1-k-[(n/2)] provided that not more than 1/(64(n + 1)k) of all the links in the n-cube fail in Byzantine manne r randomly. For the case where only links may fail, we give another br oadcasting scheme BC2-n-cube which runs in 2n(2) rounds. Broadcasting by BC2-n-cube is successful with a high probability if the number of B yzantine faulty links randomly distributed in the n-cube is not more t han a constant fraction of the total number of links. That is, it succ eeds with a probability higher than 1 - n . k (-)[(n/2)] if 1/(48k) of all the links in the n-cube fail randomly in Byzantine manner.