Fast broadcasting and gossiping in radio networks

Marek Chrobak; Leszek Ga̧sieniec; Wojciech Rytter

doi:10.1016/S0196-6774(02)00004-4

Fast broadcasting and gossiping in radio networks

Marek Chrobak
, Leszek Ga̧sieniec
, Wojciech Rytter

Research output: Contribution to journal › Article › peer-review

130 Scopus citations

Abstract

We establish an O(n log² n) upper bound on the time for determineistic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Ω(n log n). The fastest previously known algorithm for this problem works in tome O(n^3/2). Using our broadcasting algorithm, we develop an O(n^3/2 log² n) algorithm for gossiping in the same network model.

Original language	English (US)
Pages (from-to)	177-189
Number of pages	13
Journal	Journal of Algorithms
Volume	43
Issue number	2
DOIs	https://doi.org/10.1016/S0196-6774(02)00004-4
State	Published - May 2002
Externally published	Yes

ASJC Scopus subject areas

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1016/S0196-6774(02)00004-4

Cite this

@article{1fc2930f97fc4e6fabe9c48119b7ce91,

title = "Fast broadcasting and gossiping in radio networks",

abstract = "We establish an O(n log2 n) upper bound on the time for determineistic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Ω(n log n). The fastest previously known algorithm for this problem works in tome O(n3/2). Using our broadcasting algorithm, we develop an O(n3/2 log2 n) algorithm for gossiping in the same network model.",

author = "Marek Chrobak and Leszek G{\c a}sieniec and Wojciech Rytter",

note = "Funding Information: * Corresponding author. E-mail addresses: [email protected] (M. Chrobak), [email protected] (L. Ga¸sieniec), [email protected] (W. Rytter). 1 Research done while the author was visiting University of Liverpool. Research supported by grant EPSRC GR/N09077 (UK) and by NSF grant CCR-9988360. 2 Research supported by grants EPSRC GR/N09077 and NUF-NAL (The Nuffield Foundation Awards to Newly Appointed Lecturers). 3 Research supported by grants EPSRC GR/N09077 and KBN 8T11C03915.",

year = "2002",

month = may,

doi = "10.1016/S0196-6774(02)00004-4",

language = "English (US)",

volume = "43",

pages = "177--189",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Elsevier Inc.",

number = "2",

}

TY - JOUR

T1 - Fast broadcasting and gossiping in radio networks

AU - Chrobak, Marek

AU - Ga̧sieniec, Leszek

AU - Rytter, Wojciech

N1 - Funding Information: * Corresponding author. E-mail addresses: [email protected] (M. Chrobak), [email protected] (L. Ga¸sieniec), [email protected] (W. Rytter). 1 Research done while the author was visiting University of Liverpool. Research supported by grant EPSRC GR/N09077 (UK) and by NSF grant CCR-9988360. 2 Research supported by grants EPSRC GR/N09077 and NUF-NAL (The Nuffield Foundation Awards to Newly Appointed Lecturers). 3 Research supported by grants EPSRC GR/N09077 and KBN 8T11C03915.

PY - 2002/5

Y1 - 2002/5

N2 - We establish an O(n log2 n) upper bound on the time for determineistic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Ω(n log n). The fastest previously known algorithm for this problem works in tome O(n3/2). Using our broadcasting algorithm, we develop an O(n3/2 log2 n) algorithm for gossiping in the same network model.

AB - We establish an O(n log2 n) upper bound on the time for determineistic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Ω(n log n). The fastest previously known algorithm for this problem works in tome O(n3/2). Using our broadcasting algorithm, we develop an O(n3/2 log2 n) algorithm for gossiping in the same network model.

UR - https://www.scopus.com/pages/publications/0036591068

UR - https://www.scopus.com/pages/publications/0036591068#tab=citedBy

U2 - 10.1016/S0196-6774(02)00004-4

DO - 10.1016/S0196-6774(02)00004-4

M3 - Article

AN - SCOPUS:0036591068

SN - 0196-6774

VL - 43

SP - 177

EP - 189

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 2

ER -

Fast broadcasting and gossiping in radio networks

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this