A Randomized Algorithm for Gossiping in Radio Networks

Marek Chrobak, Leszek Ga̧sieniec, Wojciech Rytter

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


We present an O(n log 4n)-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/2log 2n).

Original languageEnglish (US)
Pages (from-to)119-124
Number of pages6
Issue number2
StatePublished - Mar 2004
Externally publishedYes


  • Gossiping
  • Radio networks
  • Randomized algorithms

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'A Randomized Algorithm for Gossiping in Radio Networks'. Together they form a unique fingerprint.

Cite this