Fast gossiping in square meshes/tori with bounded-size packets

Author

Lau, Francis C M ; Zhang, Shi-Heng

Author_Institution

Dept. of Comput. Sci., Hong Kong Univ., China

Volume

13

Issue

4

fYear

2002

fDate

4/1/2002 12:00:00 AM

Firstpage

349

Lastpage

358

Abstract

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

Keywords

broadcasting; multiprocessor interconnection networks; packet switching; protocols; H* model; active incident edges; all-port nodes; all-to-all broadcasting; asymptotically optimal algorithm; bounded-size packets; collective communication; communication nodes; communication optimization; gossiping; half-duplex all-port model; half-duplex network links; interconnection networks; network edges; packet-sending rounds; parallel algorithms; scheduling; square mesh; square torus; token exchange; total exchange; unique message transmission;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.995815

Filename

995815