Time of deterministic broadcasting in radio networks with local knowledge

Dariusz R. Kowalski, Andrzej Pelc

Research output: Contribution to journalArticlepeer-review

49 Scopus citations

Abstract

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
Volume33
Issue number4
DOIs
StatePublished - May 2004
Externally publishedYes

Keywords

  • Broadcasting
  • Deterministic
  • Distributed
  • Radio network

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics

Fingerprint

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

Cite this