Probabilistic Analysis of Fault Tolerant Broadcast Routing Algorithms on Mesh Networks
Mesh网络容错广播路由算法的概率分析

One-to-all or broadcast communication is one of the most important communication patterns and occurs in many important applications in parallel computing. This paper proposes a fault tolerant, local-information-based, and distributed broadcast routing algorithm based on the concept of k-submesh-connectivity in all-port mesh networks. The paper analyzes the fault tolerance of the algorithm in terms of node failure probability. Suppose that every node has independent failure probability, and deduce the success probability of the broadcast routing, which successfully routes a message from a source node to all non-faulty nodes in the networks. The paper strictly proves that the broadcast routing algorithm with the success probability of 99% to route among all non-faulty nodes on mesh networks with forty thousand nodes, in case that the node failure probability is controlled within 0. 12%. Simulation results show that the algorithm is practically efficient and effective, and the time steps of the algorithm are very close to the optimum.