License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.43
URN: urn:nbn:de:0030-drops-98323
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9832/
Go to the corresponding LIPIcs Volume Portal

Czumaj, Artur ; Davies, Peter

Brief Announcement: Randomized Blind Radio Networks

pdf-format:
LIPIcs-DISC-2018-43.pdf (0.2 MB)

Abstract

Radio networks are a long-studied model for distributed system of devices which communicate wirelessly. When these devices are mobile or have limited capabilities, the system is best modeled by the ad-hoc variant, in which the devices do not know the structure of the network. Much work has been devoted to designing algorithms for the ad-hoc model, particularly for fundamental communications tasks such as broadcasting. Most of these algorithms, however, assume that devices have some network knowledge (usually bounds on the number of nodes in the network n, and the diameter D), which may not be realistic in systems with weak devices or gradual deployment. Little is known about what can be done without this information.
This is the issue we address in this work, by presenting the first randomized broadcasting algorithms for blind networks in which nodes have no prior knowledge whatsoever. We demonstrate that lack of parameter knowledge can be overcome at only a small increase in running time. Specifically, we show that in networks without collision detection, broadcast can be achieved in O(D log n/D log^2 log n/D + log^2 n) time, almost reaching the Omega(D log n/D + log^2 n) lower bound. We also give an even faster algorithm for directed networks with collision detection.

BibTeX - Entry

@InProceedings{czumaj_et_al:LIPIcs:2018:9832,
  author =	{Artur Czumaj and Peter Davies},
  title =	{{Brief Announcement: Randomized Blind Radio Networks}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{43:1--43:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9832},
  URN =		{urn:nbn:de:0030-drops-98323},
  doi =		{10.4230/LIPIcs.DISC.2018.43},
  annote =	{Keywords: Broadcasting, Randomized Algorithms, Radio Networks}
}

Keywords: Broadcasting, Randomized Algorithms, Radio Networks
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI