A probabilistic approach to fault tolerant broadcast routing algorithms on mesh networks

One-to-all or broadcast communication is one of the most important communication patterns and occurs in many important applications in parallel computing. In this paper, we propose a fault tolerant, local-information-based, and distributed broadcast routing algorithm based on the concept of k-submesh connectivity in all-port mesh networks. We analyze the fault tolerance of our algorithm in terms of node failure probability. Under the assumption that every node has independent failure probability, we show that our broadcast routing algorithm has a high success probability. For example, we formally prove that if the node failure probability is bounded by 0.12%, our broadcast routing algorithm works successfully with probability at least 99%. Simulation results show that our algorithm is practically efficient and effective, and the time steps of our algorithm is very close to the optimum.