A novel neighbourhood broadcasting algorithm on star graphs

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 simulate 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 (1998) 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 (2001) 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 Ω (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 ≤ x = n mod 2^└<span>log n┘/ ≤ 3), our algorithm is easy to implement since routing for all nodes involved is uniform, and simpler conceptually. It uses the cycle structures of star graphs as well as the standard technique of recursive doubling.