Article

Free access

Memory space requirements for self-stabilizing leader election protocols

Authors:

Joffroy Beauquier,

Maria Gradinariu,

Colette JohnenAuthors Info & Claims

PODC '99: Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing

Pages 199 - 207

https://doi.org/10.1145/301308.301358

Published: 01 May 1999 Publication History

PDF eReader

References

[1]

Y. Afek, S. Kutten, and M. Yung. Memory-efficient self-stabilization on general networks. In WDAG90 Distributed Algorithms jth International Workshop Proceedings, Springer-Verlag LNCS:J86, pages 15-28, 1990.

Crossref

Google Scholar

[2]

S. Aggaxwal and S. Kutten. Time optimal selfstabilizing spanning tree algorithm. In FSTTCS93 Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science, Springer-Verlag LNCS:761, pages 400-410, 1993.

Digital Library

Google Scholar

[3]

A. Arora and M.G. Gouda. Distributed reset. IEEE Transactions on Computers, 43:1026-1038, 1994.

Digital Library

Google Scholar

[4]

B. Awerbuch and R. Ostrovsky. Memory-efficient and self-stabilizing network reset. In PODCgj Proceedings of the Thirteenth Annual A CM Symposium on Principles of Distributed Computing, pages 254-263, 1994.

Digital Library

Google Scholar

[5]

J. Beauquier. Proving self-stabilizing randomized protocols. In Hermes, editor, OPODIS97 Proceedings of the first international conference On Principles Of Distributed Systems, pages 279-284, 1997.

Google Scholar

[6]

J. Beauquier, S. Cordier, and S. Dela~t. Optimum probabilistic self-stabilization on uniform rings. In Proceedings of the Second Workshop on Self-Stabilizing Systems, pages 15.1-15.15, 1995.

Google Scholar

[7]

J.E. Burns, M.G. Gouda, and R.E. Miller. On relaxing interleaving assumptions. In Proceedings of the MCC Workshop on Self-Stabilizing Systems, MCC Technical Report No. STP-379-89, 1989.

Google Scholar

[8]

J.E. Burns and J. Pachl. Uniform self-stabilizing rings. A CM Transactions on Programming Languages and Systems, 11:330-344, 1989.

Digital Library

Google Scholar

[9]

E.W. Dijkstra. Self stabilizing systems in spite of distributed control. Communications of the Association of the Computing Machinery, 17:643-644, 1974.

Digital Library

Google Scholar

[10]

E.W. Dijkstra. Self-stabilization in spite of distributed control. In Selected Writings on Computing: A Personal Perspective, pages 41-46. Springer-Verlag, 1982. (paper's original date is 1973).

Google Scholar

[11]

S. Dolev. Optimal time self-stabilization in dynamic systems. In WDAG93 Distributed Algorithms 7th International Workshop Proceedings, Springer- Verlag LNCS:725, pages 160-173, 1993.

Digital Library

Google Scholar

[12]

S. Dolev, M.G. Gouda, and M. Schneider. Memory requirements for silent stabilization. In PODC96 Proceedings of the Fifteenth Annual A CM Symposium on Principles of Distributed Computing, pages 27-34, 1996.

Digital Library

Google Scholar

[13]

T. Herman. Probabilistic self-stabilization. Information Processing Letters, 35:63-67, 1990.

Digital Library

Google Scholar

[14]

A. Israeli and M. Jalfon. Token management schemes and random walks yield self-stabilizing mutual exclusion. In PODC90 Proceedings of the Ninth Annual A CM Symposium on Principles of Distributed Computing, pages 119-131, 1990.

Digital Library

Google Scholar

[15]

G. Itkis and L. Levin. Fast and lean self-stabilizing asynchronous protocols. In FocsgJ Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, pages 226-239, 1994.

Digital Library

Google Scholar

[16]

G. Itkis, C. Lin, and J. Simon. Deterministic, constant space, self-stabilizing leader election on uniform rings. In WDAG95 Distributed Algorithms 9th International Workshop Proceedings, Springer- Verlag LNCS:972, pages 288-302, 1995.

Digital Library

Google Scholar

[17]

C. Johnen. Deterministic, silent and self-stabilizing leader election algorithm on id-based rings. Technical report, Laboratoire de Recherche en Informatique, Universit~ de Paris-Sud, 1998.

Google Scholar

[18]

H. Kakugawa and M. Yamashita. Uniform and self-stabilizing token rings allowing unfair daemon. IEEE Transactions on Parallel and Distributed Systems, 8:154-162, 1997.

Digital Library

Google Scholar

[19]

C. Lin and J. Simon. Possibility and impossibility results for self-stabilizing phase clocks on synchronous rings, in Proceedings of the Second Workshop on Self- Stabilizing Systems, pages 10.1-10.15, 1995.

Google Scholar

[20]

A. Mayer, Y. Ofek, R. Ostrovsky, and M. Yung. Selfstabilizing symmetry breaking in constant-space. In STOC92 Proceedings of the ~~th Annual A CM Symposium on Theory of Computing, pages 667-678, 1992.

Digital Library

Google Scholar

[21]

A. Mayer, R. Ostrovsky, and M. Yung. Self-stabilizing algorithms for synchronous unidirectional rings. In Proceedings of the Seventh Annual A CM-SIAM Symposium on Discrete Algorithms (SODA96), pages 564- 573, 1996.

Digital Library

Google Scholar

[22]

A. Pogosyants, R. Segala, and N. Lynch. Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study. In WDAG97 Distributed Algorithms 11th International Workshop Proceedings, Springer-Verlag LNCS:13~O, pages 22-36, 1997.

Digital Library

Google Scholar

Cited By

View all

Zaiser FMurawski AOng C(2025)Guaranteed Bounds on Posterior Distributions of Discrete Probabilistic Programs with LoopsProceedings of the ACM on Programming Languages10.1145/37048749:POPL(1104-1135)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704874
Herman T(2022)Origin of Self-StabilizationEdsger Wybe Dijkstra10.1145/3544585.3544592(81-104)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3544585.3544592
Parihar AChakraborty S(2021)Token-based approach in distributed mutual exclusion algorithms: a review and direction to future researchThe Journal of Supercomputing10.1007/s11227-021-03802-8Online publication date: 12-May-2021
https://doi.org/10.1007/s11227-021-03802-8
Show More Cited By

Index Terms

Memory space requirements for self-stabilizing leader election protocols

Recommendations

Self-Stabilizing Leader Election in Dynamic Networks

Two silent self-stabilizing asynchronous distributed algorithms are given for the leader election problem in a dynamic network with unique IDs. A leader is elected for each connected component of the network. A BFS DAG, rooted at the leader, is ...
Self-stabilizing leader election in optimal space under an arbitrary scheduler

A silent self-stabilizing asynchronous distributed algorithm, SSLE, is given for the leader election problem in a connected unoriented (bidirectional) network with unique IDs. SSLE also constructs a BFS tree on the network rooted at that leader. 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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '99: Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing

May 1999

286 pages

ISBN:1581130996

DOI:10.1145/301308

Chairmen:
Brian Coan
Bellcore, Morristown, NJ
,
Jennifer Welch
Texas A & M Univ., College Station

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC99

Sponsor:

PODC99: ACM Symposium on Principles of Distributed Computing

May 4 - 6, 1999

Georgia, Atlanta, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
569
Total Downloads

Downloads (Last 12 months)39
Downloads (Last 6 weeks)13

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zaiser FMurawski AOng C(2025)Guaranteed Bounds on Posterior Distributions of Discrete Probabilistic Programs with LoopsProceedings of the ACM on Programming Languages10.1145/37048749:POPL(1104-1135)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704874
Herman T(2022)Origin of Self-StabilizationEdsger Wybe Dijkstra10.1145/3544585.3544592(81-104)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3544585.3544592
Parihar AChakraborty S(2021)Token-based approach in distributed mutual exclusion algorithms: a review and direction to future researchThe Journal of Supercomputing10.1007/s11227-021-03802-8Online publication date: 12-May-2021
https://doi.org/10.1007/s11227-021-03802-8
Blin LTixeuil S(2020)Compact self-stabilizing leader election for general networksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2020.05.019Online publication date: Jun-2020
https://doi.org/10.1016/j.jpdc.2020.05.019
Blin LDubois SFeuilloley L(2020)Silent MST Approximation for Tiny MemoryStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-64348-5_10(118-132)Online publication date: 25-Nov-2020
https://doi.org/10.1007/978-3-030-64348-5_10
Doty DEftekhari MRobinson PEllen F(2019)Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population ProtocolsProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331627(34-42)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331627
Srimani PWang JDing Y(2018)Self-Stabilizing Master-Slave Token Circulation in Unoriented Cactus Graphs2018 IEEE/WIC/ACM International Conference on Web Intelligence (WI)10.1109/WI.2018.0-109(41-48)Online publication date: Dec-2018
https://doi.org/10.1109/WI.2018.0-109
Blin LTixeuil S(2018)Compact deterministic self-stabilizing leader election on a ringDistributed Computing10.1007/s00446-017-0294-231:2(139-166)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s00446-017-0294-2
Zuck LMcMillan KTorf J(2017)$$P^5$$ : Planner-less Proofs of Probabilistic Parameterized ProtocolsVerification, Model Checking, and Abstract Interpretation10.1007/978-3-319-73721-8_16(336-357)Online publication date: 29-Dec-2017
https://doi.org/10.1007/978-3-319-73721-8_16
Blin LFraigniaud P(2015)Space-Optimal Time-Efficient Silent Self-Stabilizing Constructions of Constrained Spanning Trees2015 IEEE 35th International Conference on Distributed Computing Systems10.1109/ICDCS.2015.66(589-598)Online publication date: Jun-2015
https://doi.org/10.1109/ICDCS.2015.66
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

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

Self-Stabilizing Leader Election in Dynamic Networks

Self-stabilizing leader election in optimal space under an arbitrary scheduler

Time-Optimal Self-Stabilizing Leader Election in Population Protocols