research-article

Self-Stabilizing Leader Election

Authors:

Hsueh-Ping Chen,

Ho-Lin ChenAuthors Info & Claims

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

Pages 53 - 59

https://doi.org/10.1145/3293611.3331616

Published: 16 July 2019 Publication History

Abstract

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 and can be converted to a deterministic population protocol on undirected rings using previous techniques [8]. Furthermore, we extend our algorithm to perform SSLE on directed and undirected tori of arbitrary sizes.

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.

Digital Library

[3]

Dan Alistarh, Rati Gelashvili, and Milan Vojnović. 2015. Fast and exact majority in population protocols. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. ACM, 47--56.

Digital Library

[4]

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

Digital Library

[5]

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

Digital Library

[6]

Dana Angluin, James Aspnes, and David Eisenstat. 2008b. A simple population protocol for fast robust approximate majority. Distributed Computing, Vol. 21, 2 (2008), 87--102.

Digital Library

[7]

Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. 2007. The computational power of population protocols. Distributed Computing, Vol. 20, 4 (2007), 279--304.

Digital Library

[8]

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

Digital Library

[9]

James Aspnes, Joffroy Beauquier, Janna Burman, and Devan Sohier. 2016. Time and space optimal counting in population protocols. arXiv preprint arXiv:1611.07238 (2016).

[10]

James Aspnes and Eric Ruppert. 2009. An introduction to population protocols. In Middleware for Network Eccentric and Mobile Applications. Springer, 97--120.

[11]

Joffroy Beauquier, Janna Burman, Simon Clavière, and Devan Sohier. 2015. Space-optimal counting in population protocols. In International Symposium on Distributed Computing. Springer, 631--646.

Digital Library

[12]

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, Vol. 50, 3 (2012), 433--445.

Digital Library

[13]

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

Digital Library

[14]

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

Digital Library

[15]

Shlomi Dolev, Amos Israeli, and Shlomo Moran. 1997. Uniform dynamic self-stabilizing leader election. IEEE Transactions on Parallel and Distributed Systems, Vol. 8, 4 (1997), 424--440.

Digital Library

[16]

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

Digital Library

[17]

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

[18]

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

[19]

Gene Itkis, Chengdian Lin, and Janos Simon. 1995. Deterministic, constant space, self-stabilizing leader election on uniform rings. In International Workshop on Distributed Algorithms. 288--302.

Digital Library

[20]

Synnöve Kekkonen-Moneta. 2002. Torus orientation. Distributed Computing, Vol. 15, 1 (2002), 39--48.

Digital Library

[21]

David Soloveichik, Matthew Cook, Erik Winfree, and Jehoshua Bruck. 2008. Computation with finite stochastic chemical reaction networks. Natural Computing, Vol. 7, 4 (2008), 615--633.

Digital Library

[22]

Axel Thue. 1912. Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Kra. Vidensk. Selsk. Skrifer, I. Mat. Nat. Kl. (1912), 1--67.

Cited By

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
Show More Cited By

Index Terms

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

Recommendations

Self-Stabilizing Leader Election in Regular Graphs
PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing

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)...
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 ...
How to Prove Impossibility Under Global Fairness: On Space Complexity of Self-Stabilizing Leader Election on a Population Protocol Model

A population protocol is one of distributed computing models for passively-mobile systems, where a number of agents change their states by pairwise interactions between two agents. In this paper, we investigate the solvability of the self-stabilizing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

July 2019

563 pages

ISBN:9781450362177

DOI:10.1145/3293611

General Chair:
Peter Robinson
City University of Hong Kong
,
Program Chair:
Faith Ellen
University of Toronto, Canada

Copyright © 2019 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: 16 July 2019

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 '19

Sponsor:

PODC '19: ACM Symposium on Principles of Distributed Computing

July 29 - August 2, 2019

Toronto ON, Canada

Acceptance Rates

PODC '19 Paper Acceptance Rate 48 of 173 submissions, 28%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
470
Total Downloads

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

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Sudo YShibata MNakamura JKim YMasuzawa T(2021)Self-Stabilizing Population Protocols With Global KnowledgeIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.307676932:12(3011-3023)Online publication date: 1-Dec-2021
https://doi.org/10.1109/TPDS.2021.3076769
Srinivasan Skandukoori R(2021)A synod based deterministic and indulgent leader election protocol for asynchronous large groupsInternational Journal of Parallel, Emergent and Distributed Systems10.1080/17445760.2021.187906737:2(220-247)Online publication date: 1-Feb-2021
https://doi.org/10.1080/17445760.2021.1879067
Chen HChen HEmek YCachin C(2020)Self-Stabilizing Leader Election in Regular GraphsProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3405733(210-217)Online publication date: 31-Jul-2020
https://dl.acm.org/doi/10.1145/3382734.3405733
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
Sudo YShibata MNakamura JKim YMasuzawa T(2020)The Power of Global Knowledge on Self-stabilizing Population ProtocolsStructural Information and Communication Complexity10.1007/978-3-030-54921-3_14(237-254)Online publication date: 29-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-54921-3_14
Ben-David NChang YDory MLeitersdorf D(2019)PODC 2019 ReviewACM SIGACT News10.1145/3374857.337486650:4(33-45)Online publication date: 4-Dec-2019
https://dl.acm.org/doi/10.1145/3374857.3374866
Alistarh D(2019)Distributed Computing Column 76ACM SIGACT News10.1145/3374857.337486550:4(31-32)Online publication date: 4-Dec-2019
https://dl.acm.org/doi/10.1145/3374857.3374865

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