Brief Announcement: Randomized Blind Radio Networks

Authors Artur Czumaj, Peter Davies



PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.43.pdf
  • Filesize: 245 kB
  • 3 pages

Document Identifiers

Author Details

Artur Czumaj
  • University of Warwick, Coventry, UK
Peter Davies
  • University of Warwick, Coventry, UK

Cite AsGet BibTex

Artur Czumaj and Peter Davies. Brief Announcement: Randomized Blind Radio Networks. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.43

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Networks → Network algorithms
Keywords
  • Broadcasting
  • Randomized Algorithms
  • Radio Networks

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. N. Alon, A. Bar-Noy, N. Linial, and D. Peleg. A lower bound for radio broadcast. Journal of Computer and System Sciences, 43(2):290-298, 1991. Google Scholar
  2. A. Czumaj and P. Davies. Communicating with beeps. In Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS), pages 1-16, 2015. Google Scholar
  3. A. Czumaj and W. Rytter. Broadcasting algorithms in radio networks with unknown topology. In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS), pages 492-501, 2003. Google Scholar
  4. T. Jurdziński and G. Stachowiak. Probabilistic algorithms for the wakeup problem in single-hop radio networks. Theory of Computing Systems, 38(3):347-367, 2005. Google Scholar
  5. D. Kowalski and A. Pelc. Broadcasting in undirected ad hoc radio networks. Distributed Computing, 18(1):43-57, 2005. Google Scholar
  6. E. Kushilevitz and Y. Mansour. An Ω(D log(N/D)) lower bound for broadcast in radio networks. SIAM Journal on Computing, 27(3):702-712, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail