The Library
Deterministic blind radio networks
Tools
Tools
Tools
Czumaj, Artur and Davies, Peter (2018) Deterministic blind radio networks. In: 32nd International Symposium on Distributed Computing (DISC 2018), New Orleans, LA, 15-19 Oct 2018. Published in: 32nd International Symposium on Distributed Computing (DISC 2018), 121 15:1-15:17. ISBN 9783959770927. ISSN 1868-8969. doi:10.4230/LIPIcs.DISC.2018.15
|
PDF
WRAP-deterministic-blind-radio-networks-Czumaj-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (462Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.DISC.2018.15
Abstract
Ad-hoc radio networks and multiple access channels are classical and well-studied models of distributed systems, with a large body of literature on deterministic algorithms for fundamental communications primitives such as broadcasting and wake-up. However, almost all of these algorithms assume knowledge of the number of participating nodes and the range of possible IDs, and often make the further assumption that the latter is linear in the former. These are very strong assumptions for models which were designed to capture networks of weak devices organized in an ad-hoc manner. It was believed that without this knowledge, deterministic algorithms must necessarily be much less efficient.
In this paper we address this fundamental question and show that this is not the case. We present deterministic algorithms for blind networks (in which nodes know only their own IDs), which match or nearly match the running times of the fastest algorithms which assume network knowledge (and even surpass the previous fastest algorithms which assume parameter knowledge but not small labels).
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TK Electrical engineering. Electronics Nuclear engineering |
|||||||||
| Divisions: | Faculty of Science > Computer Science | |||||||||
| Library of Congress Subject Headings (LCSH): | Radio, Distributed algorithms | |||||||||
| Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
| Journal or Publication Title: | 32nd International Symposium on Distributed Computing (DISC 2018) | |||||||||
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | |||||||||
| ISBN: | 9783959770927 | |||||||||
| ISSN: | 1868-8969 | |||||||||
| Official Date: | 4 October 2018 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 121 | |||||||||
| Page Range: | 15:1-15:17 | |||||||||
| DOI: | 10.4230/LIPIcs.DISC.2018.15 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Open Access | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | 32nd International Symposium on Distributed Computing (DISC 2018) | |||||||||
| Type of Event: | Conference | |||||||||
| Location of Event: | New Orleans, LA | |||||||||
| Date(s) of Event: | 15-19 Oct 2018 | |||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
