Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Chrobak, Marek
Gasieniec, Leszek
Kowalski, Dariusz R.

dblp
dblp
dblp

Not MPG Author(s):

Chrobak, Marek
Gasieniec, Leszek

BibTeX cite key*:

Chrobak2007

Title

Title*:

The wake-up problem in multihop radio networks

Journal

Journal Title*:

SIAM Journal on Computing

Journal's URL:


Download URL
for the article:

http://link.aip.org/link/?SMJ/36/1453/1

Language:

English

Publisher

Publisher's
Name:

SIAM

Publisher's URL:


Publisher's
Address:

Philadelphie, PA, USA

ISSN:

0097-5397

Vol, No, pp, Date

Volume*:

36

Number:

5

Publishing Date:

January 2007

Pages*:

1453-1471

Number of
VG Pages:


Page Start:

1453

Page End:

1471

Sequence Number:


DOI:

10.1137/S0097539704442726

Note, Abstract, ©

Note:


(LaTeX) Abstract:

We study the problem of waking up a collection of $n$ processors connected by a multihop ad hoc ratio network with unknown topology, no access to a global clock, and no collision detection mechanism available. Each node in the network either wakes up spontaneously or gets activated by receiving a wake-up signal from another node. All active nodes transmit the wake-up signals according to a given protocol $\calW$. The running time of $\calW$ is the number of steps counted from the first spontaneous wake-up until all nodes become activated. We provide two protocols for this problem. The first one is a deterministic protocol with running time $O(n^{5/3}\log n)$. Our protocol is based on a novel concept of a shift-tolerant selector to which we refer as a (radio) synchronizer. The second protocol is randomized, and its expected running time is $O(D \log^2 n)$, where $D$ is the diameter of the network. Subsequently we show how to employ our wake-up protocols to solve two other communication primitives: leader election and clock synchronization.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Chrobak2007,
AUTHOR = {Chrobak, Marek and Gasieniec, Leszek and Kowalski, Dariusz R.},
TITLE = {The wake-up problem in multihop radio networks},
JOURNAL = {SIAM Journal on Computing},
PUBLISHER = {SIAM},
YEAR = {2007},
NUMBER = {5},
VOLUME = {36},
PAGES = {1453--1471},
ADDRESS = {Philadelphie, PA, USA},
MONTH = {January},
ISBN = {0097-5397},
DOI = {10.1137/S0097539704442726},
}


Entry last modified by Anja Becker, 02/28/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Anja Becker
Created
02/08/2008 01:27:51 PM
Revision
0.



Editor
Anja Becker



Edit Date
08.02.2008 13:33:14