K. Qiu (Canada)
interconnection network, neighbourhood broadcasting.
The neighbourhood broadcasting problem on an intercon nection network is defined as sending a fixed sized message from the source node to all its neighbours where in one time unit, a node can send to or receive from exactly one of its neighbours a datum of constant size. Previously, this prob lem has been studied for the hypercube, the star and the pancake interconnection networks, and a special family of Cayley graphs of permutation groups formed by transposi tions. Here, we study the problem when the source node has m multiple messages (or a single message of size m). We develop a simple and novel scheme so that the neigh bourhood broadcasting of m messages can be done in as ymptotically optimal time of O(m + log n), where n is the degree of the source node. This scheme is a general and unified scheme in that it applies to several interconnection networks such as the hypercube, the star, and the pancake, all in the family of Cayley graphs. The scheme can be used in any regular interconnection networks with the similar cy cle structure as in the aforementioned graphs.
Important Links:
Go Back
