research-article

Self-Stabilizing Leader Election in Regular Graphs

Authors:

Hsueh-Ping Chen,

Ho-Lin ChenAuthors Info & Claims

PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing

Pages 210 - 217

https://doi.org/10.1145/3382734.3405733

Published: 31 July 2020 Publication History

Abstract

Population protocols [3] are used as a distributed model that captures the behavior of passively mobile agents. Leader election is one of the most well-studied problems in this model. In this paper, we focus on the self-stabilizing leader election (SSLE) problem proposed by Angluin et al. [5]. Previously, it is known that SSLE can be performed on arbitrary rings and tori with a constant number of states [11], but SSLE on complete graphs requires Ω(n) states [9].

In this paper, we propose the first SSLE population protocol for arbitrary k-regular graphs, which solves an open question proposed in [5]. There are two different SSLE protocols in this paper. In both protocols, the number of states is independent of the size of the graph. The first protocol is simpler and more intuitive but requires O((64c)^k · k^4k+4) states, where c is the constant number of states used by the SSLE protocol for rings [11]. The second protocol is more carefully designed to reduce the number of states to O(k¹²). Both of these two constructions can apply to arbitrary graphs if every node knows its own degree.

References

[1]

Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L Rivest. 2017. Time-space trade-offs in population protocols. In Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms. SIAM, 2560--2579.

Digital Library

[2]

Dan Alistarh and Rati Gelashvili. 2015. Polylogarithmic-time leader election in population protocols. In International Colloquium on Automata, Languages, and Programming. Springer, 479--491.

[3]

Dana Angluin, James Aspnes, Zoë Diamadi, Michael J Fischer, and René Peralta. 2006. Computation in networks of passively mobile finite-state sensors. Distributed computing 18, 4 (2006), 235--253.

[4]

Dana Angluin, James Aspnes, and David Eisenstat. 2008. Fast computation by population protocols with a leader. Distributed Computing 21, 3 (2008), 183--199.

Digital Library

[5]

Dana Angluin, James Aspnes, Michael J Fischer, and Hong Jiang. 2008. Self-stabilizing population protocols. ACM Transactions on Autonomous and Adaptive Systems (TAAS) 3, 4 (2008), 13.

[6]

Joffroy Beauquier, Peva Blanchard, and Janna Burman. 2013. Self-stabilizing leader election in population protocols over arbitrary communication graphs. In International Conference On Principles Of Distributed Systems. Springer, 38--52.

Digital Library

[7]

Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach. 2018. Simple and efficient leader election. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[8]

Janna Burman, David Doty, Thomas Nowak, Eric E Severson, and Chuan Xu. 2019. Efficient self-stabilizing leader election in population protocols. arXiv preprint arXiv:1907.06068 (2019).

[9]

Shukai Cai, Taisuke Izumi, and Koichi Wada. 2012. How to prove impossibility under global fairness: On space complexity of self-stabilizing leader election on a population protocol model. Theory of Computing Systems 50, 3 (2012), 433--445.

Digital Library

[10]

Ho-Lin Chen, David Doty, and David Soloveichik. 2014. Deterministic function computation with chemical reaction networks. Natural computing 13, 4 (2014), 517--534.

[11]

Hsueh-Ping Chen and Ho-Lin Chen. 2019. Self-stabilizing leader election. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. 53--59.

Digital Library

[12]

Edsger W Dijkstra. 1974. Self-stabilizing Systems in Spite of Distributed Control. Communications (1974).

[13]

David Doty and David Soloveichik. 2018. Stable leader election in population protocols requires linear time. Distributed Computing 31, 4 (2018), 257--271.

Digital Library

[14]

Michael Fischer and Hong Jiang. 2006. Self-stabilizing leader election in networks of finite-state anonymous agents. In International Conference On Principles Of Distributed Systems. Springer, 395--409.

Digital Library

[15]

Leszek Gąsieniec, Grzegorz Stachowiak, and Przemyslaw Uznanski. 2019. Almost logarithmic-time space optimal leader election in population protocols. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures. 93--102.

Digital Library

[16]

Leszek Gąsieniec and Grzegorz Staehowiak. 2018. Fast space optimal leader election in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2653--2667.

[17]

Gene Itkis and Leonid Levin. 1994. Fast and lean self-stabilizing asynchronous protocols. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science. 226--239.

Digital Library

[18]

Richard M Karp and Raymond E Miller. 1969. Parallel program schemata. Journal of Computer and system Sciences 3, 2 (1969), 147--195.

Digital Library

[19]

Carl Adam Petri. 1966. Communication with automata. (1966).

[20]

Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K Datta, and Lawrence L Larmore. 2018. Loosely-Stabilizing Leader Election for Arbitrary Graphs in Population Protocol Model. IEEE Transactions on Parallel and Distributed Systems 30, 6 (2018), 1359--1373.

Cited By

Yokota DSudo YOoshita FMasuzawa TOshman RNolin AHalldorsson MBalliu A(2023)A Near Time-optimal Population Protocol for Self-stabilizing Leader Election on Rings with a Poly-logarithmic Number of StatesProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594586(2-12)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594586
Alistarh DRybicki JVoitovych SMilani AWoelfel P(2022)Near-Optimal Leader Election in Population Protocols on GraphsProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538435(246-256)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538435
YOKOTA DSUDO YMASUZAWA T(2021)Time-Optimal Self-Stabilizing Leader Election on Rings in Population ProtocolsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2020EAP1125E104.A:12(1675-1684)Online publication date: 1-Dec-2021
https://doi.org/10.1587/transfun.2020EAP1125
Show More Cited By

Index Terms

Self-Stabilizing Leader Election in Regular Graphs
1. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms

Recommendations

Near-Optimal Leader Election in Population Protocols on Graphs
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing

In the stochastic population protocol model, we are given a connected graph with n nodes, and in every time step, a scheduler samples an edge of the graph uniformly at random and the nodes connected by this edge interact. A fundamental task in this ...
Self-Stabilizing Leader Election
PODC '19: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing

In this paper, we study the self-stabilizing leader election (SSLE) problem in population protocols. We construct a non-deterministic population protocol that can solve SSLE on directed rings of all sizes. Our algorithm uses a constant number of states ...
Time-Optimal Self-Stabilizing Leader Election in Population Protocols
PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

We consider the standard population protocol model, where (a priori) indistinguishable and anonymous agents interact in pairs according to uniformly random scheduling. The self-stabilizing leader election problem requires the protocol to converge on a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing

July 2020

539 pages

ISBN:9781450375825

DOI:10.1145/3382734

General Chair:
Yuval Emek
Technion, Israel
,
Program Chair:
Christian Cachin
University of Bern, Switzerland

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part 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 components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 July 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Ministry of Science and Technology, Taiwan

Conference

PODC '20

Sponsor:

PODC '20: ACM Symposium on Principles of Distributed Computing

August 3 - 7, 2020

Virtual Event, Italy

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
203
Total Downloads

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

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yokota DSudo YOoshita FMasuzawa TOshman RNolin AHalldorsson MBalliu A(2023)A Near Time-optimal Population Protocol for Self-stabilizing Leader Election on Rings with a Poly-logarithmic Number of StatesProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594586(2-12)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594586
Alistarh DRybicki JVoitovych SMilani AWoelfel P(2022)Near-Optimal Leader Election in Population Protocols on GraphsProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538435(246-256)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538435
YOKOTA DSUDO YMASUZAWA T(2021)Time-Optimal Self-Stabilizing Leader Election on Rings in Population ProtocolsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2020EAP1125E104.A:12(1675-1684)Online publication date: 1-Dec-2021
https://doi.org/10.1587/transfun.2020EAP1125
Burman JChen HChen HDoty DNowak TSeverson EXu CMiller ACensor-Hillel K(2021)Time-Optimal Self-Stabilizing Leader Election in Population ProtocolsProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467898(33-44)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467898
Yokota DSudo YMasuzawa T(2020)Time-Optimal Self-stabilizing Leader Election on Rings in Population ProtocolsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-64348-5_24(301-316)Online publication date: 18-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64348-5_24

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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents