Efficient all-to-all broadcast in star graph interconnection networks

Yu-Chee Tseng*, Wu Lin Chang, Jang Ping Sheu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


In this paper, we study the all-to-all personalized and non-personalized broadcast problems in a star graph. This work is motivated by the observation that existing works in the literature only try to optimize the data transmission time, but ignore the start-up time required to initialize communication. As a result, existing algorithms, although claimed to be optimal, are only so when the start-up time is negligible. In this paper we try to optimize both costs at the same time. We develop an all-to-all personalized broadcast algorithm that is more efficient than existing results. We also present an all-to-all non-personalized broadcast algorithm that outperforms existing results in most cases except when the start-up time is very small (in a ratio of O(1/(n - 1)!), where n is the dimension of the star graph) compared to the transmission time. Extensive simulations have been conducted, which show 10% approx. 80% improvement over existing results.

Original languageEnglish
Pages (from-to)811-819
Number of pages9
JournalProceedings of the National Science Council, Republic of China, Part A: Physical Science and Engineering
Issue number6
StatePublished - 1 Nov 1998


Dive into the research topics of 'Efficient all-to-all broadcast in star graph interconnection networks'. Together they form a unique fingerprint.

Cite this