GOSSIPING WITH MULTIPLE SENDS AND RECEIVES

We consider the problem of gossiping in several important networks in as few rounds as possible. During a single round, each processor may s end an unlimited size message to k neighbors, or receive messages from k neighbors, but a processor cannot both send and receive during the same round. The network architectures we consider are trees, cycles, g rids, hypercubes, and toroidal (or ''wrap-around'') grids. As an inter esting corollary of several of our main results, we obtain an optimal (d + 1)-round gossiping algorithm for the d-dimensional hypercube when k = 2 and show that gossiping in d rounds is impossible regardless of the size of k.