Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



ID: 356648.0, MPI für Informatik / Algorithms and Complexity Group
The wake-up problem in multihop radio networks
Authors:Chrobak, Marek; Gasieniec, Leszek; Kowalski, Dariusz R.
Language:English
Date of Publication (YYYY-MM-DD):2007
Title of Journal:SIAM Journal on Computing
Volume:36
Issue / Number:5
Start Page:1453
End Page:1471
Review Status:Peer-review
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2008-02-28
External Publication Status:published
Document Type:Article
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C12573CC004A8E26-40739073EBED9539C12573E9004477EA-...
DOI:10.1137/S0097539704442726
ISSN:0097-5397
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.