announcement

Brief Announcement: Optimal Leader Election in Multi-Hop Radio Networks

Authors:

Artur Czumaj,

Peter DaviesAuthors Info & Claims

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

Pages 47 - 49

https://doi.org/10.1145/2933057.2933076

Published: 25 July 2016 Publication History

Get Access

Abstract

We present optimal randomized leader election algorithms for multi-hop radio networks, which run in expected time asymptotically equal to that required to broadcast one message to the network. We first observe that, under certain assumptions, a simulation approach of Bar-Yehuda, Golreich and Itai (1991) can be used to obtain an algorithm that for directed and undirected networks elects a leader in O(D log n/D + log² n) expected time, where n is the number of the nodes and $D$ is the eccentricity of the network. We then extend this approach to present an algorithm which operates on undirected radio networks with collision detection (and in fact the weaker beep model) and elects a leader in O(D + log n) expected time.

We also give an algorithm for the model without collision detection which runs in time O(D log n/D + log² n) ⋅ Ω√log n), and succeeds with high probability. While slightly slower than the algorithm of Ghaffari and Haeupler (2013), it has the advantage of working in directed networks, and is the fastest leader election algorithm to achieve a high-probability bound therein.

References

[1]

N. Alon, A. Bar-Noy, N. Linial, and D. Peleg. A lower bound for radio broadcast. JCSS, 43(2):290--298, 1991.

Digital Library

Google Scholar

[2]

R. Bar-Yehuda, O. Goldreich, and A. Itai. Efficient emulation of single-hop radio network with collision on multi-hop radio network with no collision detection. Distributed Computing, 5:67--71, 1991.

Digital Library

Google Scholar

[3]

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. JCSS, 45(1):104--126, 1992.

Digital Library

Google Scholar

[4]

B. S. Chlebus, D. R. Kowalski, and A. Pelc. Electing a leader in multi-hop radio networks. In ¶roc 16th International Conference on Principles of Distributed Systems (OPODIS), pages 106--120, 2012.

Google Scholar

[5]

A. Cornejo and F. Kuhn. Deploying wireless networks with beeps. In ¶roc 24th DISC, pages 148--262, 2010.

Digital Library

Google Scholar

[6]

A. Czumaj and P. Davies. Communicating with beeps. In ¶roc 19th International Conference on Principles of Distributed Systems (OPODIS), 2015.

Google Scholar

[7]

A. Czumaj and W. Rytter. Broadcasting algorithms in radio networks with unknown topology. In ¶roc 44th FOCS, pages 492--501, 2003.

Digital Library

Google Scholar

[8]

M. Ghaffari and B. Haeupler. Near optimal leader election in multi-hop radio networks. In ¶roc 24th SODA, pages 748--766, 2013.

Digital Library

Google Scholar

[9]

D. Kowalski and A. Pelc. Broadcasting in undirected ad hoc radio networks. Distributed Computing, 18(1):43--57, 2005.

Digital Library

Google Scholar

[10]

E. Kushilevitz and Y. Mansour. An Ω(D łog (N/D)) lower bound for broadcast in radio networks. SICOMP, 27(3):702--712, 1998.

Digital Library

Google Scholar

[11]

D. E. Willard. Log-logarithmic selection resolution protocols in a multiple access channel. SICOMP, 15(2):468--477, 1986.

Digital Library

Google Scholar

Cited By

View all

Chang YKopelowitz TPettie SWang RZhan W(2019)Exponential Separations in the Energy Complexity of Leader ElectionACM Transactions on Algorithms10.1145/334111115:4(1-31)Online publication date: 4-Oct-2019
https://dl.acm.org/doi/10.1145/3341111
Dufoulon FBurman JBeauquier JNewport CKeidar I(2018)Brief AnnouncementProceedings of the 2018 ACM Symposium on Principles of Distributed Computing10.1145/3212734.3212779(237-239)Online publication date: 23-Jul-2018
https://dl.acm.org/doi/10.1145/3212734.3212779
Czumaj ADavies PSchiller ESchwarzmann A(2017)Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio NetworksProceedings of the ACM Symposium on Principles of Distributed Computing10.1145/3087801.3087825(3-12)Online publication date: 25-Jul-2017
https://dl.acm.org/doi/10.1145/3087801.3087825
Show More Cited By

Index Terms

Brief Announcement: Optimal Leader Election in Multi-Hop Radio Networks
1. Networks
  1. Network algorithms
    1. Control path algorithms
      1. Network control algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms
      1. Self-organization

Recommendations

Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing
Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially ...
Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks
PODC '17: Proceedings of the ACM Symposium on Principles of Distributed Computing

We study two fundamental communication primitives: broadcasting and leader election in the classical model of multi-hop radio networks with unknown topology and without collision detection mechanisms. It has been known for almost 20 years that in ...
Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets
PODC '17: Proceedings of the ACM Symposium on Principles of Distributed Computing

We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. Our work is motivated by the following central question: can we break the long-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

July 2016

508 pages

ISBN:9781450339643

DOI:10.1145/2933057

General Chair:
George Giakkoupis
INRIA, France

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2016

Check for updates

Author Tags

Qualifiers

Announcement

Conference

PODC '16

Sponsor:

PODC '16: ACM Symposium on Principles of Distributed Computing

July 25 - 28, 2016

Illinois, Chicago, USA

Acceptance Rates

PODC '16 Paper Acceptance Rate 40 of 149 submissions, 27%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
165
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chang YKopelowitz TPettie SWang RZhan W(2019)Exponential Separations in the Energy Complexity of Leader ElectionACM Transactions on Algorithms10.1145/334111115:4(1-31)Online publication date: 4-Oct-2019
https://dl.acm.org/doi/10.1145/3341111
Dufoulon FBurman JBeauquier JNewport CKeidar I(2018)Brief AnnouncementProceedings of the 2018 ACM Symposium on Principles of Distributed Computing10.1145/3212734.3212779(237-239)Online publication date: 23-Jul-2018
https://dl.acm.org/doi/10.1145/3212734.3212779
Czumaj ADavies PSchiller ESchwarzmann A(2017)Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio NetworksProceedings of the ACM Symposium on Principles of Distributed Computing10.1145/3087801.3087825(3-12)Online publication date: 25-Jul-2017
https://dl.acm.org/doi/10.1145/3087801.3087825
Chang YKopelowitz TPettie SWang RZhan WHatami HMcKenzie PKing V(2017)Exponential separations in the energy complexity of leader electionProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055481(771-783)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055481

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks

Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets