A Broadcasting Algorithm with Time and Message Optimum on Arrangement Graphs
Leqiang Bai, Hajime Maeda, Hiroyuki Ebara, Hideo Nakano · Journal of Graph Algorithms and Applications · 1998
In this paper, we propose a distributed broadcasting algorithm with optimal time complexity and without message redundancy for one-toall broadcasting in the one-port communication model on arrangement graph interconnection networks. The algorithm exploits the hierarchical property of the arrangement graph to construct different-sized broadcasting trees for different-sized subgraphs. These different-sized broadcasting trees constitute a spanning tree on the arrangement graph. Every processor individually performs its broadcasting procedure based on the spanning tree. It is shown that a message can be broadcast to all the other n! − 1 processors in at most O(k lg n) steps on the (n, k)-arrangement (n−k)! graph interconnection network. The algorithm can also guarantee that each of processors on the arrangement graph interconnection network receives the message exactly once.