Premium
A randomized algorithm for gossiping in radio networks
Author(s) -
Chrobak Marek,
Ga̧sieniec Leszek,
Rytter Wojciech
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10109
Subject(s) - gossip , randomized algorithm , computer science , radio networks , algorithm , binary logarithm , combinatorics , mathematics , discrete mathematics , wireless network , telecommunications , wireless , psychology , social psychology
We present an O ( n log 4 n )‐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 time O ( n 3/2 log 2 n ). © 2004 Wiley Periodicals, Inc.