Fault-Tolerant Broadcasting on the Arrangement Graph
Lu Bai · The Computer Journal · 1998
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 lg2n)) steps if the number of faulty edges is less than k(n − k).