F. Bao et al., BROADCASTING IN HYPERCUBES WITH RANDOMLY DISTRIBUTED BYZANTINE FAULTS, IEICE transactions on fundamentals of electronics, communications and computer science, E78A(9), 1995, pp. 1239-1246
Citations number
NO
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
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.