A broadcasting algorithm with time and message optimum on arrangement graphs. (English) Zbl 0895.68063

Bai, Leqiang; Maeda, Hajime; Ebara, Hiroyuki; Nakano, Hideo

J. Graph Algorithms Appl. 2, Paper No. 2, 17 p. (1998).

Summary: We propose a distribution broadcasting algorithm with optimal time complexity and without message redundancy for one-to-all 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! \over (n-k)!)}-1\) processors in at most \(O(k\lg n)\) 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.

MSC:

68W10

Parallel algorithms in computer science

Keywords:

distribution broadcasting algorithm; optimal time complexity