NDLI: The wireless synchronization problem

Please wait, while we are loading the content...

The life and times of a zookeeper

Preventing versus curing: avoiding conflicts in transactional memories

Tight bounds for clock synchronization

The weakest failure detector for solving k-set agreement

The forgiving graph: a distributed data structure for low stretch under adversarial attack

Fast distributed random walks

The wireless synchronization problem

Efficient broadcasting in known topology radio networks with long-range interference

Brief announcement: Stateless distributed algorithms for generalized packing linear programs

Brief announcement: a note on distributed stable matching

Brief announcement: the price of anonymity: optimal consensus despite asynchrony, crash and anonymity

Brief announcement: PUSH, a DISC shell

Brief announcement: the theory of network tracing

Brief announcement: hardness of broadcasting in wireless networks with unreliable communication

Refining the way to consensus

Cassandra: structured storage system on a P2P network

Dynamic atomic storage without consensus

Load balancing without regret in the bulletin board model

Simple and efficient asynchronous byzantine agreement with optimal resilience

A distributed polylogarithmic time algorithm for self-stabilizing skip graphs

Distributed and parallel algorithms for weighted vertex cover and other covering problems

SINR diagrams: towards algorithmically usable SINR models of wireless networks

The effect of power-law degrees on the navigability of small worlds: [extended abstract]

Brief announcement: concurrent non-commutative boosted transactions

On a selfish caching game

Brief announcement: minimum spanning trees and cone-based topology control

Brief announcement: deaf, dumb, and chatting robots

Brief announcement: (more) efficient pruning of ad-hoc wireless networks

Brief announcement: complexity analysis and algorithm design for pipeline configuration in distributed networks

Memory models: a case for rethinking parallel languages and hardware

Pregel: a system for large-scale graph processing - "ABSTRACT"

Randomized mutual exclusion in O(log N / log log N) RMRs

Concurrent imitation dynamics in congestion games

Partial synchrony based on set timeliness

The flip markov chain and a randomising P2P protocol

Return of the primal-dual: distributed metric facilitylocation

Coloring unstructured wireless multi-hop networks

Bounding the locality of distributed routing algorithms

Brief announcement: distributed phase synchronization of dynamic set of processes

Brief announcement: non-self-stabilizing and self-stabilizing gathering in networks of mobile agents--the notion of speed

Brief announcement: locality-based aggregate computation in wireless sensor networks

Brief announcement: global consistency can be easier than point-to-point communication

Brief announcement: self-assembly as graph grammar as distributed system

Brief announcement: exactly electing a unique leader is not harder than computing symmetric functions on anonymous quantum networks

Emerging challenges and opportunities in parallel computing: the cretaceous redux?

Max registers, counters, and monotone circuits

Extracting quorum failure detectors

Fast scalable deterministic consensus for crash failures

Correctness of gossip-based membership under message loss

Oblivious interference scheduling

Parsimonious flooding in dynamic graphs

Brief announcement: how to speed-up fault-tolerant clock generation in VLSI systems-on-chip via pipelining

The disagreement power of an adversary: extended abstract

Brief announcement: tight lower bounds for greedy routing in uniform small world rings

Vertical paxos and primary-backup replication

Distributed discovery of large near-cliques

Brief announcement: impossibility results for optimistic fair exchange with multiple autonomous arbiters

Brief announcement: perfectly secure message transmission in directed networks re-visited

Brief announcement: weakest failure detectors via an egg-laying simulation

Brief announcement: optimal self-stabilizing multi-token ring: a randomized solution

Brief announcement: topology knowledge affects probabilistic reliable communication

Brief announcement: lightweight key agreement and digital certificates for wireless sensor networks

Brief announcement: collaborative measurement of upload speeds in P2P systems

Brief announcement: virtual world consistency: a new condition for STM systems

Brief announcement: optimization based rate allocation for application layer multicast

Brief announcement: fast scalable Byzantine agreement in the full information model with a nonadaptive adversary

Brief announcement: a platform for experimenting with mobile algorithms in a laboratory

Brief announcement: distributed algorithms for approximating wireless network capacity

Brief announcement: new bounds for the controller problem

The wireless synchronization problem

Content Provider	ACM Digital Library
Author	Newport, Calvin Dolev, Shlomi Guerraoui, Rachid Gilbert, Seth Kuhn, Fabian
Abstract	In this paper, we study the wireless synchronization problem 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 begin executing in different rounds and the exact number of participants is not known in advance. We first prove a lower bound, demonstrating that at least $Ω(log^{2}n/(F-t)loglogn$ + Ft/F-t logn) rounds are needed to synchronize. We then describe two algorithms. The first algorithm almost matches the lower bound, yielding a running time of O(F/F - t $log^{2}n$ + Ft/F - t logn) rounds. The second algorithm is adaptive, terminating in O(t′ $log^{3}n)$ rounds in good executions, that is, when the devices begin executing at the same time, and there are never more than t′ frequencies disrupted in any given round, for some t′ < t. In all executions, even those that are not good, it terminates in O(F $log^{3}n)$ rounds.
Starting Page	190
Ending Page	199
Page Count	10
File Format	PDF
ISBN	9781605583969
DOI	10.1145/1582716.1582749
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-08-10
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Disrupted radio channel Synchronization
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in