The Wireless Synchronization ProblemReportar como inadecuado

The Wireless Synchronization Problem - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Presented at: Twenty-Eighth Annual Symposium on Principles of Distributed Computing, Calgray, Canada, August 10-12, 2009 Published in: Proceedings of the 28th Annual Symposium on Principles of Distributed Computing : , 2009

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.

Keywords: Wireless networks ; Disruption-prone networks ; Interference ; NCCR-MICS ; NCCR-MICS/CL1 Reference LPD-CONF-2009-008

Autor: Dolev, Shlomi; Gilbert, Seth; Guerraoui, Rachid; Kuhn, Fabian; Newport, Calvin


Documentos relacionados