Fast gossiping in square meshes/tori with bounded-size packets
Francis C. M. Lau, Shiheng Zhang · IEEE Transactions on Parallel and Distributed Systems · 2002
Gossiping is a communication problem in which each node has a unique message (token) to be transmitted to every other node. The nodes exchange their tokens by means of packets. A solution to the problem is judged by how many rounds of packet sending are required. In this paper, we consider a version of the problem in which small-sized packets (each carrying exactly one token) are used, 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). This is also known as the H* model. We study the model on a 2D square mesh and on a 2D square torus. An improved, asymptotically optimal algorithm for the mesh and an optimal algorithm for the torus are presented.