FAULT-TOLERANT BROADCASTING ON THE ARRANGEMENT GRAPH

This paper proposes a distributed fault-tolerant algorithm for one-to- all broadcasting in the one-port communication model on the arrangemen t graph, Exploiting the hierarchical properties of the arrangement gra ph to constitute different-sized broadcasting trees for different-size d subgraphs, we propose a distributed algorithm with optimal time comp lexity and without message redundancy for one-to-all broadcasting in t he one-port communication model for the fault-free arrangement graph. According to the property that there is a family of k(n - k) node-disj oint paths between any two nodes, we develop a fast fault-tolerant pro cedure 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 al gorithm, 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 Ig n) steps if no faults exist on the (n, k)-arrangement graph, and in O(k(2) lgn + k lg(2) n)) steps i f the number of faulty edges is less than k(n - k).