Gossiping in Minimal Time
- 1 February 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 21 (1), 111-139
- https://doi.org/10.1137/0221010
Abstract
The gossip problem involves communicating a unique item fromeach node in a graph to every other node. We study the minimumtime required to do this under the weakest model of parallel communicationwhich allows each node to participate in just one communicationat a time as either sender or receiver. We study a number of topologiesincluding the complete graph, grids, hypercubes and rings. Definitivenew optimal time algorithms are derived for complete graphs, rings,regular grids and toroidal ...Keywords
This publication has 11 references indexed in Scilit:
- Fast Gossiping for the HypercubeSIAM Journal on Computing, 1992
- Parallel algorithms for gossiping by mailInformation Processing Letters, 1990
- A survey of gossiping and broadcasting in communication networksNetworks, 1988
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous WritesSIAM Journal on Computing, 1986
- Routing, merging, and sorting on parallel models of computationJournal of Computer and System Sciences, 1985
- Gossips and telegraphsJournal of the Franklin Institute, 1979
- Some Complexity Results for Matrix Computations on Parallel ProcessorsJournal of the ACM, 1978
- Spreading information by conferencesDiscrete Mathematics, 1976
- Fast Parallel Matrix Inversion AlgorithmsSIAM Journal on Computing, 1976
- New gossips and telephonesDiscrete Mathematics, 1975