Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. The Wireless Synchronization Problem
 
conference paper

The Wireless Synchronization Problem

Dolev, Shlomi
•
Gilbert, Seth  
•
Guerraoui, Rachid  
Show more
2009
Proceedings of the 28th Annual Symposium on Principles of Distributed Computing
Twenty-Eighth Annual Symposium on Principles of Distributed Computing

In this paper, we study the wireless synchronization prob- lem which requires devices activated at different times on a congested single-hop radio network to synchronize their round numbering. We assume a collection of n synchronous devices with access to a shared band of the radio spectrum, divided into F narrowband frequencies. We assume that the communication medium suffers from unpredictable, perhaps even malicious interference, which we model by an adversary that can disrupt up to t frequencies per round. Devices be- gin executing in different rounds and the exact number of participants is not known in advance. We first prove a lower bound, and we then describe two algorithms. The first algorithm (almost) matches the lower bound, in the worst case. The second algorithm is adaptive, terminating more rapidly in good executions, that is, when the devices begin executing at the same time and there are fewer than expected disrupted frequencies.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1145/1582716.1582749
Author(s)
Dolev, Shlomi
Gilbert, Seth  
Guerraoui, Rachid  
Kuhn, Fabian
Newport, Calvin
Date Issued

2009

Published in
Proceedings of the 28th Annual Symposium on Principles of Distributed Computing
Start page

190

End page

199

Subjects

Wireless networks

•

Disruption-prone networks

•

Interference

•

NCCR-MICS

•

NCCR-MICS/CL1

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Event nameEvent placeEvent date
Twenty-Eighth Annual Symposium on Principles of Distributed Computing

Calgary, Canada

August 10-12, 2009

Available on Infoscience
June 12, 2009
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/40417
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés