|
Published Articles >> Table of Contents >> Abstract
Ninth International Conference on Parallel and Distributed Systems (ICPADS'02)
p. 37
A Novel Neighbourhood Broadcasting Algorithm on Star Graphs
Ke Qiu, Acadia University
Sajal K. Das, University of Texas at Arlington
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICPADS.2002.1183375
Send link to a friend
| Abstract |
|
The neighbourhood broadcasting problem is defined as sending a message of fixed size from the source node to all its neighbours in an interconnection network, where in one time unit, a node can send to or receive from one and only one of its neighbours a datum item of constant size. In other words, the neighbourhood broadcasting is to stimulate a single step of an all-port model on a single-port model. On a star interconnection network, this problem has been recently studied by Fujita who showed (1) a lower bound of [log n] for an n-star; and (2) a neighbourhood broadcasting algorithm on an n-star that requires 1.5[log(n-2)] + 3 steps. The algorithm is later improved by Mkwawa and Kouvatsos to require 1.33[log(n-1)] + O(1) steps. In this paper, we present a novel and interesting O(log n) neighbourhood broadcasting algorithm on an n- star. In view of the \Omega(log n) lower bound, our algorithm is also optimal. Although the actual number of steps required is 4 [log(n/2)] + 1 (or 4 [log(n/2)] + 1 + x, if 1 /le x = n mod 2[log n] /le 3), our algorithm is easy to implement since routing for all nodes involved is unifrom, and simpler conceptually. It uses the cycle structures of star graphs as well as the standard technique of recursive doubling.
|
 Additional Information
|
Citation:
Ke Qiu, Sajal K. Das,
"A Novel Neighbourhood Broadcasting Algorithm on Star Graphs,"
icpads,
p. 37,
Ninth International Conference on Parallel and Distributed Systems (ICPADS'02),
2002
|
|
