We investigate the reliability of broadcasting in product networks con
taining faulty nodes and/or links. Faults considered in this paper are
mainly of the Byzantine type, i.e., a faulty node or a faulty link ma
y not only stop sending a message but also arbitrarily change a messag
e passing through the faulty place or even fabricate a false message.
We assume that no nodes have a priori information about faults in a ne
twork. Hence, the key problem of reliable broadcasting in our model is
how to control the message transmission so that any corrupted message
cannot affect the result of the broadcasting too much. We propose the
concept of an n-channel graph which has n-independent spanning trees
rooted at each node. The fault tolerance can be achieved by sending n
copies of the message along the n-independent spanning trees rooted at
the source node. In this paper we show how to construct n-independent
spanning trees of a product network from spanning trees of n-componen
t graphs. Furthermore, we can design an efficient and reliable broadca
sting scheme based on independent spanning trees for a product network
from simple broadcasting schemes for component networks. The degrees
of fault tolerance against crash faults and Byzantine faults of nodes
and/or links are, respectively, n - 1 and [(n - 1)/2] in the worst cas
e. We can successfully broadcast with a probability higher than 1 - k(
-[n/2]) in any product network of order N consisting of n-component gr
aphs of order b or less, if at most N/4b(3)nk faulty nodes are randoml
y distributed in the network. We can also successfully broadcast with
a probability higher than 1 - k(-[n/2]) in any product network of size
L, of n component graphs of size b or less, if at most L/12b(2)k faul
ty links are randomly distributed in the network. (C) 1998 Elsevier Sc
ience B.V. All rights reserved.