Document Open Access Logo

Beeping a Deterministic Time-Optimal Leader Election

Authors Fabien Dufoulon , Janna Burman, Joffroy Beauquier

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.20.pdf
  • Filesize: 449 kB
  • 17 pages

Document Identifiers

Author Details

Fabien Dufoulon
  • LRI, Université Paris-Sud, CNRS, Université Paris-Saclay, Orsay, France
Janna Burman
  • LRI, Université Paris-Sud, CNRS, Université Paris-Saclay, Orsay, France
Joffroy Beauquier
  • LRI, Université Paris-Sud, CNRS, Université Paris-Saclay, Orsay, France

Cite AsGet BibTex

Fabien Dufoulon, Janna Burman, and Joffroy Beauquier. Beeping a Deterministic Time-Optimal Leader Election. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.20

Abstract

The beeping model is an extremely restrictive broadcast communication model that relies only on carrier sensing. In this model, we solve the leader election problem with an asymptotically optimal round complexity of O(D + log n), for a network of unknown size n and unknown diameter D (but with unique identifiers). Contrary to the best previously known algorithms in the same setting, the proposed one is deterministic. The techniques we introduce give a new insight as to how local constraints on the exchangeable messages can result in efficient algorithms, when dealing with the beeping model. Using this deterministic leader election algorithm, we obtain a randomized leader election algorithm for anonymous networks with an asymptotically optimal round complexity of O(D + log n) w.h.p. In previous works this complexity was obtained in expectation only. Moreover, using deterministic leader election, we obtain efficient algorithms for symmetry-breaking and communication procedures: O(log n) time MIS and 5-coloring for tree networks (which is time-optimal), as well as k-source multi-broadcast for general graphs in O(min(k,log n) * D + k log{(n M)/k}) rounds (for messages in {1,..., M}). This latter result improves on previous solutions when the number of sources k is sublogarithmic (k = o(log n)).

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Distributed algorithms
  • Theory of computation → Design and analysis of algorithms
Keywords
  • distributed algorithms
  • leader election
  • beeping model
  • time complexity
  • deterministic algorithms
  • wireless networks

Metrics

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

Related Versions

References

  1. Y. Afek, N. Alon, Z. Bar-Joseph, A. Cornejo, B. Haeupler, and F. Kuhn. Beeping a maximal independent set. Distributed Computing, 26(4):195-208, Aug 2013. Google Scholar
  2. D. Alistarh, A. Cornejo, M. Ghaffari, and N. Lynch. Firefly synchronization with asynchronous wake-up. In Workshop on Biological Distributed Algorithms, 2014. Google Scholar
  3. J. Beauquier, J. Burman, F. Dufoulon, and S. Kutten. Fast Beeping Protocols for Deterministic MIS and (Δ+1)-Coloring in Sparse Graphs. In IEEE INFOCOM, 2018, to appear. Google Scholar
  4. A. Casteigts, Y. Métivier, J. M. Robson, and A. Zemmari. Design Patterns in Beeping Algorithms. In OPODIS, pages 15:1-15:16, 2016. Google Scholar
  5. A. Casteigts, Y. Métivier, J.M. Robson, and A. Zemmari. Deterministic leader election in 𝒪(D+ logn) time with messages of size 𝒪(1). In DISC, pages 16-28, 2016. Google Scholar
  6. I. Chlamtac and S. Kutten. On broadcasting in radio networks - problem analysis and protocol design. IEEE Transactions on Communications, 33(12):1240-1246, 1985. Google Scholar
  7. A. Cornejo and F. Kuhn. Deploying wireless networks with beeps. In DISC, pages 148-162, 2010. Google Scholar
  8. A. Czumaj and P. Davies. Optimal leader election in multi-hop radio networks. ArXiv e-prints, 2015. URL: http://arxiv.org/abs/1505.06149.
  9. A. Czumaj and P. Davies. Brief announcement: Optimal leader election in multi-hop radio networks. In PODC, pages 47-49, 2016. Google Scholar
  10. A. Czumaj and P. Davies. Communicating with Beeps. In OPODIS, pages 1-16, 2016. Google Scholar
  11. Y. Dinitz and N. Solomon. Two absolute bounds for distributed bit complexity. In Structural Information and Communication Complexity, pages 115-126, 2005. Google Scholar
  12. K.-T. Förster, J. Seidel, and R. Wattenhofer. Deterministic leader election in multi-hop beeping networks. In DISC, pages 212-226, 2014. Google Scholar
  13. M. Ghaffari and B. Haeupler. Near optimal leader election in multi-hop radio networks. In SODA, pages 748-766, 2013. Google Scholar
  14. S. Gilbert and C. Newport. The computational power of beeps. In DISC, pages 31-46, 2015. Google Scholar
  15. R. Guerraoui and A. Maurer. Byzantine fireflies. In DISC, pages 47-59, 2015. Google Scholar
  16. S. Kutten, G. Pandurangan, D. Peleg, P. Robinson, and A. Trehan. On the complexity of universal leader election. In PODC, pages 100-109, 2013. Google Scholar
  17. Y. Métivier, J.M. Robson, and A. Zemmari. Analysis of fully distributed splitting and naming probabilistic procedures and applications. Theoretical Computer Science, 584:115-130, 2015. Special Issue on Structural Information and Communication Complexity. Google Scholar
  18. K. Nakano and S. Olariu. Randomized o(log log n)-round leader election protocols in packet radio networks. In Algorithms and Computation, pages 210-219, 1998. Google Scholar
  19. S. Navlakha and Z. Bar-Joseph. Distributed information processing in biological and computational systems. Commun. ACM, 58(1):94-102, 2014. Google Scholar
  20. D. Peleg. Time-efficient broadcasting in radio networks: A review. In Distributed Computing and Internet Technology, pages 1-18, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. Google Scholar
  21. J. Schneider and R. Wattenhofer. What is the use of collision detection (in wireless networks)? In DISC, pages 133-147, 2010. Google Scholar
  22. A. Scott, P. Jeavons, and L. Xu. Feedback from nature: An optimal distributed algorithm for maximal independent set selection. In PODC, pages 147-156, 2013. Google Scholar
  23. J. Seidel. Anonymous distributed computing: computability, randomization and checkability. PhD thesis, ETH Zurich, Zürich, Switzerland, 2015. URL: http://d-nb.info/1080812695.
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