Reliable broadcasting in product networks in the presence of faulty nodes

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