On randomized broadcasting and gossiping in radio networks

Ding Liu, Manoj Prabhakaran

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper has two parts. In the first part we give an alternative (and much simpler) proof for the best known lower bound of Ω(Dlog (N/D)) time-steps for randomized broadcasting in radio networks with unknown topology. In the second part we give an O(N log3N)-time randomized algorithm for gossiping in such radio networks. This is an improvement over the fastest previously known algorithm that works in time O(N log4 N).

Original languageEnglish (US)
Title of host publicationComputing and Combinatorics - 8th Annual International Conference, COCOON 2002, Proceedings
EditorsOscar H. Ibarra, Louxin Zhang
PublisherSpringer-Verlag Berlin Heidelberg
Pages340-349
Number of pages10
ISBN (Print)354043996X, 9783540439967
StatePublished - Jan 1 2002
Event8th Annual International Conference on Computing and Combinatorics, COCOON 2002 - Singapore, Singapore
Duration: Aug 15 2002Aug 17 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2387
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th Annual International Conference on Computing and Combinatorics, COCOON 2002
CountrySingapore
CitySingapore
Period8/15/028/17/02

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On randomized broadcasting and gossiping in radio networks'. Together they form a unique fingerprint.

Cite this