The Library
Faster deterministic communication in radio networks
Tools
Czumaj, Artur and Davies, Peter (2018) Faster deterministic communication in radio networks. In: 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), Rome, Italy, 12-15 Jul 2016. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 55 pp. 1-14. ISBN 9783959770132. doi:10.4230/LIPIcs.ICALP.2016.139 ISSN 0097-5397.
|
PDF
WRAP_0583063-cs-090516-icalp_submission.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (770Kb) | Preview |
Official URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.139
Abstract
In this paper we improve the deterministic complexity of two fundamental communication primitives in the classical model of ad-hoc radio networks with unknown topology: broadcasting and wake-up. 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 in-degree of any node Δ, and the eccentricity of the network D.
For such networks, we first give an algorithm for wake-up, in both directed and undirected networks, based on the existence of small universal synchronizers. This algorithm runs in O(min{n,DΔ}lognlogΔloglogΔ) time, improving over the previous best O(nlog2n)-time result across all ranges of parameters, but particularly when maximum in-degree 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(nlogDloglogDΔn) time. This is the fastest known algorithm for this problems, improving upon the O(nlognloglogn)-time algorithm of De Marco (2010) and the O(nlog2D)-time algorithm due to Czumaj and Rytter (2003), the previous fastest results for directed networks, and is the first to come within a log-logarithmic factor of the Ω(nlogD) 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.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | T Technology > TK Electrical engineering. Electronics Nuclear engineering | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Wireless communication systems | ||||||
Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Publisher: | Schloss Dagstuhl ; Leibniz-Zentrum fuer Informatik | ||||||
ISBN: | 9783959770132 | ||||||
ISSN: | 0097-5397 | ||||||
Official Date: | 7 August 2018 | ||||||
Dates: |
|
||||||
Volume: | 55 | ||||||
Page Range: | pp. 1-14 | ||||||
Article Number: | 139 | ||||||
DOI: | 10.4230/LIPIcs.ICALP.2016.139 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Description: | Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), Rome, Italy, July 12 - 15, 2016. |
||||||
Date of first compliant deposit: | 10 May 2016 | ||||||
Date of first compliant Open Access: | 10 May 2016 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Rome, Italy | ||||||
Date(s) of Event: | 12-15 Jul 2016 | ||||||
Related URLs: | |||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year