Optimal gossiping in paths and cycles

Abstract

In the gossiping problem, each node in a network possesses a token initially; after gossiping, every node has a copy of every other node's token. The nodes exchange their tokens by packets. A solution to the problem is judged by how many rounds of packet sending it requires. In this paper, we consider the version of the problem in which a packet is of limited size (a packet can hold up to p tokens), the links (edges) of the network are half-duplex (only one packet can flow through a link at a time), and the nodes are all-port (a node's incident edges can all be active at the same time). We study the path and the cycle which are essential building blocks for more complex structures. We present tight lower bounds and algorithms which match them. The results also lead to the conclusion that p = 2 is the optimal packet size. © 2003 Elsevier B.V. All rights reserved.