Based on the Mendia and Sarkar's algorithm [8], we propose an optimal and nonredundant distributed broadcasting algorithm in star graphs. For an n-dimensional star graph, our algorithm takes O(nlog(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(mlog(2)n + nlog(2)n) time due to the nonredundant property of our broadcasting algorithm.
關聯:
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
