A Broadcasting Algorithm with Time and Message Optimum on Arrangement Graphs

Abstract

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 dierent-sized broadcasting trees for dierent-sized subgraphs. These dierent-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! (n k)! 1 processors in at most O(k lgn) steps on the (n;k)-arrangement graph interconnection network. The algorithm can also guarantee that each of processors on the arrangement graph interconnection network receives the message exactly once.