Gossiping with multiple sends and receives (Q1917243)

The gossiping problem is studied for different networks of processors. Assuming that each processor possesses a unique piece of information the problem is to disseminate every piece of information to all processors. The model of communication used is that during a single round each processor may send an unlimited size message to \(k\) neighbors, or receive messages from \(k\) neighbors, but a processor can not both send and receive messages from \(k\) neighbors during the same round. The main result is that if every dimension of a toroidal (or ``wrap-around'') grid \(G\) is even, then gossiping can be completed in \(G\) in \(\text{diam}(G)+1\) rounds when \(k=2\), but cannot be completed in \(\text{diam}(G)\) rounds regardless of the size of \(k\). As an immediate corollary the authors obtain an optimal \((d+1)\)-round algorithm for gossiping in a \(d\)-dimensional hypercube with \(k=2\). Moreover, some results concerning gossiping in toroidal grids with uneven dimensions, grids without ``wrap-around'' connections, and trees are given.