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

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.


68W10 Parallel algorithms in computer science
Full Text: DOI EuDML