abstract

Public Access

Brief Announcement: Leader Election in SINR Model with Arbitrary Power Control

Authors:

Magnús M. Halldórsson,

Stephan Holzer,

Evangelia Anna MarkatouAuthors Info & Claims

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

Pages 203 - 205

https://doi.org/10.1145/3087801.3087851

Published: 25 July 2017 Publication History

PDF eReader

Abstract

In this article, we study the leader election problem in the Signal-to-Interference-plus-Noise-Ratio (SINR) model where nodes can adjust their transmission power. We show that in this setting it is possible to solve the leader election problem in two communication rounds, with high probability. Previously, it was known that Omega(log n) rounds were sufficient and necessary when using uniform power, where n is the number of nodes in the network.

We then examine how much power control is needed to achieve fast leader election. We show that any 2-round leader election algorithm in the SINR model running correctly w.h.p. requires a power range 2^Ω(n) even when n is known. We match this with an algorithm that uses power range 2^θ(n), when n is known and 2^Õ(n1.5) when n is not known. We also explore tradeoffs between time and power used, and show that to elect a leader in t rounds, a power range exp(n^1θ(t)) is sufficient and necessary.

References

[1]

Jeremy T Fineman, Seth Gilbert, Fabian Kuhn, and Calvin Newport. Contention resolution on a fading channel. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 155--164. ACM, 2016.

Digital Library

Google Scholar

[2]

Calvin C. Newport. Radio network lower bounds made easy. CoRR, abs/1405.7300, 2014.

Google Scholar

Index Terms

Brief Announcement: Leader Election in SINR Model with Arbitrary Power Control
1. Networks
  1. Network algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms

Recommendations

Leader election in SINR model with arbitrary power control
Abstract
We consider the Leader Election Problem in the Signal-to-Interference-plus-Noise-Ratio (SINR) model where nodes can adjust their transmission power. We show that in this setting it is possible to elect a leader in two communication ...
Brief Announcement: Optimal Leader Election in Multi-Hop Radio Networks
PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

July 2017

480 pages

ISBN:9781450349925

DOI:10.1145/3087801

General Chair:
Elad Michael Schiller
Chalmers University of Technology, Sweden
,
Program Chair:
Alexander A. Schwarzmann
University of Connecticut, USA

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 2017

Check for updates

Author Tags

Qualifiers

Abstract

Funding Sources

AFOSR
Icelandic Research Fund
National Science Foundation

Conference

PODC '17

Sponsor:

PODC '17: ACM Symposium on Principles of Distributed Computing

July 25 - 27, 2017

DC, Washington, USA

Acceptance Rates

PODC '17 Paper Acceptance Rate 38 of 154 submissions, 25%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
152
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)9

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Index Terms

Recommendations

Leader election in SINR model with arbitrary power control

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

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