Document Open Access Logo

Faster Deterministic Communication in Radio Networks

Authors Artur Czumaj, Peter Davies

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.139.pdf
  • Filesize: 498 kB
  • 14 pages

Document Identifiers

Author Details

Artur Czumaj
Peter Davies

Cite AsGet BibTex

Artur Czumaj and Peter Davies. Faster Deterministic Communication in Radio Networks. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 139:1-139:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://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 Delta, 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*Delta}*log(n)*log(Delta))/(log(log(Delta)))) time, improving over the previous best O(n*log^2(n))-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(n*log(D)*log(log((D*Delta)/n))) time. This is the fastest known algorithm for this problems, improving upon the O(n*log(n)*log*log(n))-time algorithm of De Marco (2010) and the O(n*log^2(D))-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 Omega(n*log(D)) 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.
Keywords
  • Radio networks
  • Communication networks
  • Broadcasting
  • Wake-Up
  • Deterministic algorithms

Metrics

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

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. R. Bar-Yehuda, O. Goldreich, and A. Itai. On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. Journal of Computer and System Sciences, 45(1):104-126, 1992. Google Scholar
  3. B. Chlebus, L. Gąsieniec, D. R. Kowalski, and T. Radzik. On the wake-up problem in radio networks. In Proceedings of the 32nd Annual International Colloquium on Automata, Languages and Programming (ICALP), pages 347-359, 2005. Google Scholar
  4. B. Chlebus and D. R. Kowalski. A better wake-up in radio networks. In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 266-274, 2004. Google Scholar
  5. B. S. Chlebus, L. Gąsieniec, A. Gibbons, A. Pelc, and W. Rytter. Deterministic broadcasting in unknown radio networks. Distributed Computing, 15(1):27-38, 2002. Google Scholar
  6. B. S. Chlebus, L. Gąsieniec, A. Östlin, and J. M. Robson. Deterministic radio broadcasting. In Proceedings of the 27th Annual International Colloquium on Automata, Languages and Programming (ICALP), pages 717-728, 2000. Google Scholar
  7. B. S. Chlebus, D. R. Kowalski, and A. Pelc. Electing a leader in multi-hop radio networks. In Proceedings of the 16th International Conference on Principles of Distributed Systems (OPODIS), pages 106-120, 2012. Google Scholar
  8. M. Chrobak, L. Gąsieniec, and D. R. Kowalski. The wake-up problem in multihop radio networks. SIAM Journal on Computing, 36(5):1453-1471, 2007. Google Scholar
  9. M. Chrobak, L. Gąsieniec, and W. Rytter. Fast broadcasting and gossiping in radio networks. Journal of Algorithms, 43(2):177-189, 2002. Google Scholar
  10. A. E. F. Clementi, A. Monti, and R. Silvestri. Distributed broadcasting in radio networks of unknown topology. Theoretical Computer Science, 302(1-3):337-364, 2003. Google Scholar
  11. 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
  12. M. Ghaffari, B. Haeupler, , and M. Khabbazian. Randomized broadcast in radio networks with collision detection. In Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 325-334, 2013. Google Scholar
  13. M. Ghaffari and B. Haeupler. Near optimal leader election in multi-hop radio networks. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 748-766, 2013. Google Scholar
  14. P. Indyk. Explicit constructions of selectors and related combinatorial structures, with applications. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 697-704, 2002. Google Scholar
  15. T. Jurdziński and D. R. Kowalski. The wake-up problem in multi-hop radio networks. In M. Y. Kao, editor, Encyclopedia of Algorithms. Springer-Verlag, Berlin, 2015. Google Scholar
  16. D. Kowalski. On selection problem in radio networks. In Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 158-166, 2005. Google Scholar
  17. D. Kowalski and A. Pelc. Faster deterministic broadcasting in ad hoc radio networks. SIAM Journal on Discrete Mathematics, 18:332-346, 2004. Google Scholar
  18. D. Kowalski and A. Pelc. Broadcasting in undirected ad hoc radio networks. Distributed Computing, 18(1):43-57, 2005. Google Scholar
  19. 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
  20. G. De Marco. Distributed broadcast in unknown radio networks. SIAM Journal on Computing, 39(6):2162-2175, 2010. Google Scholar
  21. G. De Marco and A. Pelc. Faster broadcasting in unknown radio networks. Information Processing Letters, 79:53-56, 2001. Google Scholar
  22. D. Peleg. Time-efficient broadcasting in radio networks: A review. In Proceedings of the 4th International Conference on Distributed Computing and Internet Technology (ICDCIT), pages 1-18, 2007. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact