RELIABLE BROADCASTING IN PRODUCT NETWORKS

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.