Communicating with Beeps

Authors Artur Czumaj, Peter Davies



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2015.30.pdf
  • Filesize: 447 kB
  • 16 pages

Document Identifiers

Author Details

Artur Czumaj
Peter Davies

Cite AsGet BibTex

Artur Czumaj and Peter Davies. Communicating with Beeps. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.OPODIS.2015.30

Abstract

The beep model is a very weak communications model in which devices in a network can communicate only via beeps and silence. As a result of its weak assumptions, it has broad applicability to many different implementations of communications networks. This comes at the cost of a restrictive environment for algorithm design. Despite being only recently introduced, the beep model has received considerable attention, in part due to its relationship with other communication models such as that of ad-hoc radio networks. However, there has been no definitive published result for several fundamental tasks in the model. We aim to rectify this with our paper. We present algorithms for the tasks of broadcast, gossiping, and multi-broadcast, and also, as intermediary results, means of depth-first search and diameter estimation. Our O(D+log(M)-time algorithm for broadcasting is a simple formalization of a concept known as beep waves, and is asymptotically optimal. We give an O(n*log(L))-time depth-first search procedure, and show how this can be used as the basis for an O(n*log(L*M))-time gossiping algorithm. Finally, we approach the more general problem of multi-broadcast. We differentiate between two variants of this problem: one where nodes must know the origin of all source messages, and another where this information is not required. In the first instance we achieve an algorithm running in time O(k*log((L*M)/k)+D*log(L)), and in the second an O(k*log(M/k)+D*log(L))-time algorithm (or O(M+D*log(L)) when M <= k). We then give corresponding lower bounds: Omega(k*log((L*M)/k)+D) in the case where nodes must know message origins, and Omega(k*log(M/k)+D) and Omega(M+D) in the other case, for M > k and M <= k respectively. These lower bounds demonstrate that our algorithms are optimal except for the D*log(L) additive term. In these running-time expressions, n represents network size, D network diameter, L range of node labels, M range of source messages, and k number of sources. Our algorithms are all explicit, deterministic, and practical, and give efficient means of communication while making arguably the minimum possible assumptions about the network.
Keywords
  • Beep model
  • Communication networks
  • Broadcasting
  • Gossiping
  • Leader election

Metrics

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

References

  1. Y. Afek, N. Alon, Z. Bar-Joseph, A. Cornejo, B. Haeupler, and F. Kuhn. Beeping a maximal independent set. In Proceedings of the 25th International Symposium on Distributed Computing (DISC), pages 32-50, 2011. Google Scholar
  2. 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
  3. A. Cornejo and F. Kuhn. Deploying wireless networks with beeps. In Proceedings of the 24th International Symposium on Distributed Computing (DISC), pages 148-262, 2010. Google Scholar
  4. K.-T. Förster, J. Seidel, and R. Wattenhofer. Deterministic leader election in multi-hop beeping networks. In Proceedings of the 28th International Symposium on Distributed Computing (DISC), pages 212-226, 2014. Google Scholar
  5. 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
  6. 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
  7. S. Gilbert and C. Newport. The computational power of beeps. In Proceedings of the 29th International Symposium on Distributed Computing (DISC), pages 31-46, 2015. Google Scholar
  8. K. Hounkanli and A. Pelc. Deterministic broadcasting and gossiping with beeps. In arxiv 1508.06460, 2015. Google Scholar
  9. 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