An optimal broadcasting algorithm without message redundancy in star graphs
Jang‐Ping Sheu, Chao-Tsung Wu, Tzung-Shi Chen · IEEE Transactions on Parallel and Distributed Systems · 1995
Based on the V.E. Mendia and D. Sarkar's algorithm (1992), we propose an optimal and nonredundant distributed broadcasting algorithm in star graphs. For an n-dimensional star graph, our algorithm takes O(n log/sub 2/ n) time and guarantees that all nodes in the star graph receive the message exactly once. Moreover, broadcasting m packets in a pipeline fashion takes O(m log/sub 2/ n+n log/sub 2/ n) time due to the nonredundant property of our broadcasting algorithm.>