A Randomized Algorithm for Gossiping in Radio Networks

Marek Chrobak; Leszek Ga̧sieniec; Wojciech Rytter

doi:10.1002/net.10109

A Randomized Algorithm for Gossiping in Radio Networks

Marek Chrobak, Leszek Ga̧sieniec, Wojciech Rytter

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

10 Scopus citations

Abstract

We present an O(n log ⁴n)-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 ²n).

Original language	English (US)
Pages (from-to)	119-124
Number of pages	6
Journal	Networks
Volume	43
Issue number	2
DOIs	https://doi.org/10.1002/net.10109
State	Published - Mar 2004
Externally published	Yes

Keywords

Gossiping
Radio networks
Randomized algorithms

ASJC Scopus subject areas

Software
Information Systems
Hardware and Architecture
Computer Networks and Communications

Access to Document

10.1002/net.10109

Cite this

@article{baba63e5844b43efa825e9e8876ac19a,

title = "A Randomized Algorithm for Gossiping in Radio Networks",

abstract = "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).",

keywords = "Gossiping, Radio networks, Randomized algorithms",

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

year = "2004",

month = mar,

doi = "10.1002/net.10109",

language = "English (US)",

volume = "43",

pages = "119--124",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Liss Inc.",

number = "2",

}

TY - JOUR

T1 - A Randomized Algorithm for Gossiping in Radio Networks

AU - Chrobak, Marek

AU - Ga̧sieniec, Leszek

AU - Rytter, Wojciech

PY - 2004/3

Y1 - 2004/3

N2 - 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).

AB - 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).

KW - Gossiping

KW - Radio networks

KW - Randomized algorithms

UR - http://www.scopus.com/inward/record.url?scp=2042515611&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=2042515611&partnerID=8YFLogxK

U2 - 10.1002/net.10109

DO - 10.1002/net.10109

M3 - Article

AN - SCOPUS:2042515611

SN - 0028-3045

VL - 43

SP - 119

EP - 124

JO - Networks

JF - Networks

IS - 2

ER -

A Randomized Algorithm for Gossiping in Radio Networks

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this