Gossiping with multiple sends and receives
type: Item
instance of: scholarly article
title: Gossiping with multiple sends and receives
zbMATH Open document ID: 0863.90063
DOI: 10.1016/0166-218X(95)00123-9
author: S. Louis Hakimi
author: Anindo Bagchi
author: E. Schmeichel
published in: Discrete Applied Mathematics
publication date: 1997-05-20T00:00:00Z
full work available at URL: dam
review text: 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.
Mathematics Subject Classification ID: 90B18
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 897357
zbMATH Keywords: dissemination of information
zbMATH Keywords: wrap-around
zbMATH Keywords: gossiping
zbMATH Keywords: networks of processors
zbMATH Keywords: grid
zbMATH Keywords: hypercube
zbMATH Keywords: toroidal grids
reviewed by: Martin Middendorf
MaRDI profile type: Publication
cites work: Parallel algorithms for gossiping by mail
cites work: Gossips and telegraphs
cites work: A survey of gossiping and broadcasting in communication networks
cites work: Fast Gossiping for the Hypercube
cites work: Gossiping in Minimal Time
cites work: Fast information sharing in a complete network
Recommended article: Gossiping With Multiple Messages
Recommended article: Gossiping for communication-efficient broadcast
Recommended article: Q3972008
Recommended article: Quick gossiping without duplicate transmissions
Recommended article: Q5753992
Recommended article: On generalized gossiping and broadcasting
Recommended article: On the Role of Mobility for Multimessage Gossip
Recommended article: Fast gossiping with short unreliable messages
description: scientific article; zbMATH DE number 897357