Gossiping with multiple sends and receives

AbstractWe consider the problem of gossiping in several important networks in as few rounds as possible. During a single round, each processor may send 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, grids, hypercubes, and toroidal (or “wrap-around”) grids. As an interesting 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