Czumaj, Artur ;
Davies, Peter
Faster Deterministic Communication in Radio Networks
Abstract
In this paper we improve the deterministic complexity of two fundamental communication primitives in the classical model of adhoc radio networks with unknown topology: broadcasting and wakeup. We consider an unknown radio network, in which all nodes have no prior knowledge about network topology, and know only the size of the network n, the maximum indegree of any node Delta, and the eccentricity of the network D.
For such networks, we first give an algorithm for wakeup, in both directed and undirected networks, based on the existence of small universal synchronizers. This algorithm runs in O((min{n,D*Delta}*log(n)*log(Delta))/(log(log(Delta)))) time, improving over the previous best O(n*log^2(n))time result across all ranges of parameters, but particularly when maximum indegree is small.
Next, we introduce a new combinatorial framework of block synchronizers and prove the existence of such objects of low size. Using this framework, we design a new deterministic algorithm for the fundamental problem of broadcasting, running in O(n*log(D)*log(log((D*Delta)/n))) time. This is the fastest known algorithm for this problems, improving upon the O(n*log(n)*log*log(n))time algorithm of De Marco (2010) and the O(n*log^2(D))time algorithm due to Czumaj and Rytter (2003), the previous fastest results for directed networks, and is the first to come within a loglogarithmic factor of the Omega(n*log(D)) lower bound due to Clementi et al. (2003).
Our results have also direct implications on the fastest deterministic leader election and clock synchronization algorithms in both directed and undirected radio networks, tasks which are commonly used as building blocks for more complex procedures.
BibTeX  Entry
@InProceedings{czumaj_et_al:LIPIcs:2016:6283,
author = {Artur Czumaj and Peter Davies},
title = {{Faster Deterministic Communication in Radio Networks}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {139:1139:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6283},
URN = {urn:nbn:de:0030drops62838},
doi = {10.4230/LIPIcs.ICALP.2016.139},
annote = {Keywords: Radio networks, Communication networks, Broadcasting, WakeUp, Deterministic algorithms}
}
23.08.2016
Keywords: 

Radio networks, Communication networks, Broadcasting, WakeUp, Deterministic algorithms 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

23.08.2016 