© 1998 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
Fault-Tolerant Broadcasting on the Arrangement Graph
1 Department of Communication, Faculty of Engineering, Osaka University, Yamada Oka 2-1, Suita, Osaka 565-0871, Japan Email: lequiang{at}comm.eng.osaka-u.ac.jp, 2 Faculty of Engineering, Kansai University, Yamate-cho, Suita, Osaka 564-8680, Japan, 3 Media Center, Osaka City University, Sugimoto, Sumiyoshi-ku, Osaka 558-8585, Japan
This paper proposes a distributed fault-tolerant algorithm for one-to-all broadcasting in the one-port communication model on the arrangement graph. Exploiting the hierarchical properties of the arrangement graph to constitute different-sized broadcasting trees for different-sized subgraphs, we propose a distributed algorithm with optimal time complexity and without message redundancy for one-to-all broadcasting in the one-port communication model for the fault-free arrangement graph. According to the property that there is a family of k(n – k) node-disjoint paths between any two nodes, we develop a fast fault-tolerant procedure capable of sending a message from a node to its adjacent nodes on the (n, k)-arrangement graph with less than k(n – k) faulty edges. Combining the fault-tolerant procedure and the optimal broadcasting algorithm, a fault-tolerant broadcasting is achieved on the arrangement graph. It is shown that a message can be broadcast to all the other (n!/(n – k)!) – 1 processors in O(k lg n) steps if no faults exist on the (n, k)-arrangement graph, and in O(k2 lg n + k lg2 n)) steps if the number of faulty edges is less than k(n – k).
Received June 4, 1996. revised March 26, 1998.