Time of deterministic broadcasting in radio networks with local knowledge

Dariusz R. Kowalski, Andrzej Pelc

Research output: Contribution to journalArticlepeer-review

49 Scopus citations


The deterministic broadcasting time in radio networks, whose node know only their immediate nodes, is discussed. The broadcasting in radio networks was modeled as undirected graphs. In each of the step every node acts either as a transmitter or as a receiver. A node acting as a transmitter sends a message in which can reach all of its neighbor. A node acting as a receiver in a given step gets a message if and only if exactly one of its neighbor transmits in this step. The results shows that lower bound proves an exponential gap between time of deterministic and randomized broadcastings in radio networks.

Original languageEnglish (US)
Pages (from-to)870-891
Number of pages22
JournalSIAM Journal on Computing
Issue number4
StatePublished - May 2004
Externally publishedYes


  • Broadcasting
  • Deterministic
  • Distributed
  • Radio network

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)


Dive into the research topics of 'Time of deterministic broadcasting in radio networks with local knowledge'. Together they form a unique fingerprint.

Cite this