Cited By
View all- Chang YDuan RJiang S(2023)Near-Optimal Time–Energy Tradeoffs for Deterministic Leader ElectionACM Transactions on Algorithms10.1145/361442919:4(1-23)Online publication date: 26-Sep-2023
The Energy Complexity of Las Vegas Leader Election
Pages 75 - 86
Abstract
We consider the time (number of communication rounds) and energy (number of non-idle communication rounds per device) complexities of randomized leader election in a multiple-access channel, where the number of devices n ≥ 2 is unknown. It is well-known that for polynomial-time randomized leader election algorithms with success probability 1 - 1/poly(n), the optimal energy complexity is Θ(log log* n) if receivers can detect collisions, and it is Θ(log* n) otherwise.
References
[1]
Noga Alon, Amotz Bar-Noy, Nathan Linial, and David Peleg. 1991. A lower bound for radio broadcast. J. Comput. System Sci. 43, 2 (1991), 290--298.
[2]
Noga Alon, Mohsen Ghaffari, Bernhard Haeupler, and Majid Khabbazian. 2014. Broadcast throughput in radio networks: routing vs. network coding. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms (SODA). SIAM, 1831--1843.
[3]
Christoph Ambühl. 2005. An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks. In International Colloquium on Automata, Languages, and Programming (ICALP). Springer, 1139--1150.
[4]
Christoph Ambühl. 2008. Minimum Energy Broadcasting in Wireless Geometric Networks. In Encyclopedia of Algorithms, Ming-Yang Kao (Ed.). Springer US, Boston, MA, 526--528. https://doi.org/10.1007/978-0--387--30162--4_233
[5]
John Augustine, William K Moses Jr, and Gopal Pandurangan. 2022. Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds. arXiv preprint arXiv:2204.08385 (2022).
[6]
Reuven Bar-Yehuda, Oded Goldreich, and Alon Itai. 1992. On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. J. Comput. System Sci. 45, 1 (1992), 104--126.
[7]
Leonid Barenboim and Tzalik Maimon. 2021. Deterministic Logarithmic Completeness in the Distributed Sleeping Model. In 35th International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 209), Seth Gilbert (Ed.). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 10:1--10:19. https://doi.org/10.4230/LIPIcs.DISC.2021.10
[8]
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Maxwell Young. 2018. Scaling Exponential Backoff: Constant Throughput, Polylogarithmic Channel- Access Attempts, and Robustness. J. ACM 66, 1, Article 6 (dec 2018). https://doi.org/10.1145/3276769
[9]
Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young. 2018. Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses. SIAM J. Comput. 47, 5 (2018), 1735--1754. https://doi.org/10.1137/17M1158604
[10]
Petra Berenbrink, Colin Cooper, and Zengjian Hu. 2009. Energy efficient randomised communication in unknown adhoc networks. Theoretical Computer Science 410, 27--29 (2009), 2549--2561.
[11]
I. Caragiannis, C. Galdi, and C. Kaklamanis. 2005. Basic computations in wireless networks. In International Symposium on Algorithms and Computation. Springer, 533--542.
[12]
Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, and Wei Zhan. 2019. Exponential Separations in the Energy Complexity of Leader Election. ACM Transactions on Algorithms 15, 4, Article 49 (2019). https://doi.org/10.1145/3341111
[13]
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, and Seth Pettie. 2018. The Energy Complexity of Broadcast. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC). ACM, 95--104. https://doi.org/10.1145/3212734.3212774
[14]
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, and Seth Pettie. 2020. The Energy Complexity of BFS in Radio Networks. In Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC). ACM, 273--282. https://doi.org/10.1145/3382734.3405713
[15]
Yi-Jun Chang, Ran Duan, and Shunhua Jiang. 2021. Near-Optimal Time-Energy Trade-Offs for Deterministic Leader Election. In Proceedings of the 33th annual ACM symposium on Parallelism in algorithms and architectures (SPAA). ACM.
[16]
Yi-Jun Chang and Shunhua Jiang. 2022. The Energy Complexity of Las Vegas Leader Election. arXiv preprint arXiv:2205.08642 (2022).
[17]
Soumyottam Chatterjee, Robert Gmyr, and Gopal Pandurangan. 2020. Sleeping is Efficient: MIS in(1)-Rounds Node-Averaged Awake Complexity. In Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC). ACM, 99--108. https://doi.org/10.1145/3382734.3405718
[18]
A. E. F. Clementi, A. Monti, and R. Silvestri. 2003. Distributed broadcast in radio networks of unknown topology. Theoretical Computer Science 302, 1 (2003), 337--364.
[19]
Varsha Dani, Aayush Gupta, Thomas P. Hayes, and Seth Pettie. 2021. Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks. arXiv preprint arXiv:2104.09096 (2021).
[20]
Fabien Dufoulon, William K Moses Jr, and Gopal Pandurangan. 2022. Sleeping is Superefficient: MIS in Exponentially Better Awake Complexity. arXiv preprint arXiv:2204.08359 (2022).
[21]
Martín Farach-Colton, Rohan J. Fernandes, and Miguel A. Mosteiro. 2006. Lower Bounds for Clear Transmissions in Radio Networks. In Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN). 447--454. https://doi.org/10.1007/11682462_42
[22]
Leszek Gasieniec, Erez Kantor, Dariusz R Kowalski, David Peleg, and Chang Su. 2007. Energy and time efficient broadcasting in known topology radio networks. In International Symposium on Distributed Computing (DISC). Springer, 253--267.
[23]
Leszek Gasieniec, Andrzej Pelc, and David Peleg. 2001. The Wakeup Problem in Synchronous Broadcast Systems. SIAM Journal on Discrete Mathematics 14, 2 (2001), 207--222. https://doi.org/10.1137/S0895480100376022
[24]
Seth Gilbert, Calvin Newport, Nitin Vaidya, and Alex Weaver. 2021. Contention Resolution with Predictions. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC). Association for Computing Machinery, New York, NY, USA, 127--137. https://doi.org/10.1145/3465084.3467911
[25]
Tomasz Jurdzi'ski, Miroslaw Kutyowski, and Jan Zatopia'ski. 2002. Efficient algorithms for leader election in radio networks. In Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing (PODC). 51--57. https://doi.org/10.1145/571825.571833
[26]
T. Jurdzinski, M. Kutylowski, and J. Zatopianski. 2002. Energy-Efficient Size Approximation of Radio Networks with No Collision Detection. In Proceedings of the 8th Annual International Conference on Computing and Combinatorics (COCOON). 279--289. https://doi.org/10.1007/3--540--45655--4_31
[27]
Tomasz Jurdzi'ski and Grzegorz Stachowiak. 2005. Probabilistic algorithms for the wake-up problem in single-hop radio networks. Theory of Computing Systems 38, 3 (2005), 347--367.
[28]
Lefteris M Kirousis, Evangelos Kranakis, Danny Krizanc, and Andrzej Pelc. 2000. Power consumption in packet radio networks. Theoretical Computer Science 243, 1--2 (2000), 289--305.
[29]
Marek Klonowski and Dominik Pajak. 2018. Brief Announcement: Broadcast in Radio Networks, Time vs. Energy Tradeoffs. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PDOC). Association for Computing Machinery, New York, NY, USA, 115--117. https://doi.org/10.1145/3212734.3212786
[30]
C. Lavault, J.-F. Marckert, and V. Ravelomanana. 2007. Quasi-optimal energyefficient leader election algorithms in radio networks. Information and Computation 205, 5 (2007), 679--693.
[31]
Matthew J Miller and Nitin H Vaidya. 2005. A MAC protocol to reduce sensor network energy consumption using a wakeup radio. IEEE Transactions on mobile Computing 4, 3 (2005), 228--242.
[32]
Koji Nakano and Stephan Olariu. 2000. Randomized leader election protocols in radio networks with no collision detection. In International Symposium on Algorithms and Computation (ISAAC). Springer, 362--373.
[33]
Koji Nakano and Stephan Olariu. 2002. Uniform leader election protocols for radio networks. IEEE transactions on parallel and distributed systems 13, 5 (2002), 516--526.
[34]
Calvin Newport. 2014. Radio Network Lower Bounds Made Easy. In Proceedings of the 28th International Symposium on Distributed Computing (DISC). 258--272. https://doi.org/10.1007/978--3--662--45174--8_18
[35]
Brian M Sadler. 2005. Fundamentals of energy-constrained sensor network systems. IEEE Aerospace and Electronic Systems Magazine 20, 8 (2005), 17--35.
[36]
Ravelomanana Vlady. 2016. Time-optimal and energy-efficient size approximation of radio networks. In 2016 International Conference on Distributed Computing in Sensor Systems (DCOSS). IEEE, 233--237.
[37]
Yongqiang Wang, Felipe Nunez, and Francis J Doyle. 2012. Energy-efficient pulse-coupled synchronization strategy design for wireless sensor networks through reduced idle listening. IEEE Transactions on Signal Processing 60, 10 (2012), 5293--5306.
[38]
Dan E. Willard. 1986. Log-Logarithmic Selection Resolution Protocols in a Multiple Access Channel. SIAM J. Comput. 15, 2 (1986), 468--477. https://doi.org/10.1137/0215032
[39]
Xinyu Zhang and Kang G Shin. 2012. E-MiLi: Energy-minimizing idle listening in wireless networks. IEEE Transactions on Mobile Computing 11, 9 (2012), 1441--1454.
Index Terms
- The Energy Complexity of Las Vegas Leader Election
Recommendations
Exponential Separations in the Energy Complexity of Leader Election
Energy is often the most constrained resource for battery-powered wireless devices, and most of the energy is often spent on transceiver usage (i.e., transmitting and receiving packets) rather than computation. In this article, we study the energy ...
Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election
We consider the energy complexity of the leader election problem in the single-hop radio network model, where each device v has a unique identifier ID(v) ∈{ 1, 2, ⋖ , N} . Energy is a scarce resource for small battery-powered devices. For such devices, ...
Sublinear bounds for randomized leader election
This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O ( 1 ) rounds and (with high probability) uses only O ( n log 3 / 2 n ) ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2022
464 pages
ISBN:9781450391467
DOI:10.1145/3490148
- General Chair:
- Kunal Agrawal,
- Program Chair:
- I-Ting Angelina Lee
Copyright © 2022 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
- SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
- SIGARCH: ACM Special Interest Group on Computer Architecture
- EATCS: European Association for Theoretical Computer Science
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 July 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- NUS ODPRT
Conference
SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures
July 11 - 14, 2022
PA, Philadelphia, USA
Acceptance Rates
Overall Acceptance Rate 447 of 1,461 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 155Total Downloads
- Downloads (Last 12 months)63
- Downloads (Last 6 weeks)16
Reflects downloads up to 28 Nov 2024
Other Metrics
Citations
Cited By
View all- Chang YDuan RJiang S(2023)Near-Optimal Time–Energy Tradeoffs for Deterministic Leader ElectionACM Transactions on Algorithms10.1145/361442919:4(1-23)Online publication date: 26-Sep-2023
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in