A Probabilistic Approach to Fault Tolerant Broadcast Routing Algorithms on Mesh Networks Conference Paper uri icon

abstract

  • 2003 IEEE. 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.

name of conference

  • Proceedings International Parallel and Distributed Processing Symposium

published proceedings

  • Proceedings International Parallel and Distributed Processing Symposium

author list (cited authors)

  • Wang, G., Chen, J., & Wang, G.

citation count

  • 2

complete list of authors

  • Wang, Gaocai||Chen, Jianer||Wang, Guojun

publication date

  • January 2003