A randomized algorithm for gossiping in radio networks
- 15 January 2004
- Vol. 43 (2) , 119-124
- https://doi.org/10.1002/net.10109
Abstract
We present anO(nlog4n)‐time randomized algorithm for gossiping in radio networks with unknown topology. This is the first algorithm for gossiping in this model whose running time is only a polylogarithmic factor away from the optimum. The fastest previously known (deterministic) algorithm for this problem works in timeO(n3/2log2n).Keywords
Funding Information
- EPSRC (GR/N09077, GR/R85921)
- NSF (CCR-9988360, CCR-0208856)
This publication has 20 references indexed in Scilit:
- Information theory and communication networks: an unconsummated unionIEEE Transactions on Information Theory, 1998
- Lower bounds for the broadcast problem in mobile radio networksDistributed Computing, 1997
- GOSSIPING ON A RING WITH RADIOSParallel Processing Letters, 1996
- Asymptotically optimal gossiping in radio networksDiscrete Applied Mathematics, 1995
- On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomizationJournal of Computer and System Sciences, 1992
- Single round simulation on radio networksJournal of Algorithms, 1992
- A survey of gossiping and broadcasting in communication networksNetworks, 1988
- A perspective on multiaccess channelsIEEE Transactions on Information Theory, 1985
- The collision channel without feedbackIEEE Transactions on Information Theory, 1985
- An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channelsIEEE Transactions on Information Theory, 1985