Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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:
DateEvent
4 October 2018Published
19 July 2018Accepted
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:
Project/Grant IDRIOXX Funder NameFunder ID
EP/D063191/1[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
EP/N011163/1[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
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:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us