Reliable broadcasting in product networks in the presence of faulty nodes
Sabine R. Öhring, Maximilian Ibel, Sajal Kumar Das · 2002
Product networks define a class of topologies used very often as interconnection networks for multicomputers such as meshes, tori and hypercubes. In this paper we define the maximal number of node-disjoint paths in a product network and characterize the number of shortest paths among them. The construction of a maximal number of spanning trees allows an operational broadcasting in the product network even in the presence of a maximal number (equal to the nodes's connectivity) of node failures, given that the unique paths to a given node in each spanning tree are mutually node-disjoint. Additionally, even if there are more faulty nodes than the graph's connectivity, such that theoretically the broadcasting may fail, the probability of the network to be non-operational is shown to be quite small. Compared with other reliable broadcasting algorithms, for instance in faulty hypercubes, our broadcasting scheme requires less time.