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.