Document Open Access Logo

Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms

Authors Lélia Blin , Laurent Feuilloley , Gabriel Le Bouder

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2021.24.pdf
  • Filesize: 0.6 MB
  • 12 pages

Document Identifiers

Author Details

Lélia Blin
  • Sorbonne Université, Université d’Evry-Val-d’Essonne, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France
Laurent Feuilloley
  • Univ. Lyon, Université Lyon 1, LIRIS UMR CNRS 5205, F-69621, Lyon, France
Gabriel Le Bouder
  • Sorbonne Université, CNRS, INRIA, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France

Funding

Support by ANR ESTATE (ANR-16-CE25-0009-03) and ANR GrR (ANR-18-CE40-0032).

Acknowledgements

We thank the reviewers for their useful comments.

Cite AsGet BibTex

Lélia Blin, Laurent Feuilloley, and Gabriel Le Bouder. Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 24:1-24:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.OPODIS.2021.24

Abstract

Given a boolean predicate Π on labeled networks (e.g., proper coloring, leader election, etc.), a self-stabilizing algorithm for Π is a distributed algorithm that can start from any initial configuration of the network (i.e., every node has an arbitrary value assigned to each of its variables), and eventually converge to a configuration satisfying Π. It is known that leader election does not have a deterministic self-stabilizing algorithm using a constant-size register at each node, i.e., for some networks, some of their nodes must have registers whose sizes grow with the size n of the networks. On the other hand, it is also known that leader election can be solved by a deterministic self-stabilizing algorithm using registers of O(log log n) bits per node in any n-node bounded-degree network. We show that this latter space complexity is optimal. Specifically, we prove that every deterministic self-stabilizing algorithm solving leader election must use Ω(log log n)-bit per node registers in some n-node networks. In addition, we show that our lower bounds go beyond leader election, and apply to all problems that cannot be solved by anonymous algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • Space lower bound
  • memory tight bound
  • self-stabilization
  • leader election
  • anonymous
  • identifiers
  • state model
  • ring topology

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jordan Adamek, Mikhail Nesterenko, and Sébastien Tixeuil. Evaluating practical tolerance properties of stabilizing programs through simulation: The case of propagation of information with feedback. In Stabilization, Safety, and Security of Distributed Systems - 14th International Symposium, SSS 2012, pages 126-132, 2012. URL: https://doi.org/10.1007/978-3-642-33536-5_13.
  2. Baruch Awerbuch and Rafail Ostrovsky. Memory-efficient and self-stabilizing network RESET (extended abstract). In 13th Annual ACM Symposium on Principles of Distributed Computing, PODC 1994, pages 254-263, 1994. URL: https://doi.org/10.1145/197917.198104.
  3. Joffroy Beauquier, Maria Gradinariu, and Colette Johnen. Memory space requirements for self-stabilizing leader election protocols. In 18th Annual ACM Symposium on Principles of Distributed Computing, PODC 1999, pages 199-207, 1999. URL: https://doi.org/10.1145/301308.301358.
  4. Lélia Blin and Pierre Fraigniaud. Space-optimal time-efficient silent self-stabilizing constructions of constrained spanning trees. In 35th IEEE International Conference on Distributed Computing Systems, ICDCS 2015, pages 589-598, 2015. URL: https://doi.org/10.1109/ICDCS.2015.66.
  5. Lélia Blin and Sébastien Tixeuil. Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative. Distributed Computing, 31(2):139-166, 2018. URL: https://doi.org/10.1007/s00446-017-0294-2.
  6. Lélia Blin and Sébastien Tixeuil. Compact self-stabilizing leader election for general networks. In LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, pages 161-173, 2018. URL: https://doi.org/10.1007/978-3-319-77404-6_13.
  7. Lucas Boczkowski, Amos Korman, and Emanuele Natale. Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 2540-2559, 2017. URL: https://doi.org/10.1137/1.9781611974782.168.
  8. Ajoy Kumar Datta, Colette Johnen, Franck Petit, and Vincent Villain. Self-stabilizing depth-first token circulation in arbitrary rooted networks. Distributed Computing, 13(4):207-218, 2000. URL: https://doi.org/10.1007/PL00008919.
  9. Edsger W. Dijkstra. Self-stabilizing systems in spite of distributed control. Commun. ACM, 17(11):643-644, 1974. URL: https://doi.org/10.1145/361179.361202.
  10. Edsger W. Dijkstra. Self-Stabilization in Spite of Distributed Control, pages 41-46. Springer New York, New York, NY, 1982. URL: https://doi.org/10.1007/978-1-4612-5695-3_7.
  11. Shlomi Dolev, Mohamed G. Gouda, and Marco Schneider. Memory requirements for silent stabilization. Acta Inf., 36(6):447-462, 1999. URL: https://doi.org/10.1007/s002360050180.
  12. Swan Dubois and Sébastien Tixeuil. A taxonomy of daemons in self-stabilization, 2011. URL: http://arxiv.org/abs/1110.0334.
  13. Laurent Feuilloley. Introduction to local certification. CoRR, abs/1910.12747, 2019. URL: http://arxiv.org/abs/1910.12747.
  14. Laurent Feuilloley and Pierre Fraigniaud. Survey of distributed decision. Bulletin of the EATCS, 119, 2016. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/411/391, URL: http://arxiv.org/abs/1606.04434.
  15. Mohsen Ghaffari and Merav Parter. MST in log-star rounds of congested clique. In 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, pages 19-28, 2016. URL: https://doi.org/10.1145/2933057.2933103.
  16. James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato. Toward optimal bounds in the congested clique: Graph connectivity and MST. In 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, pages 91-100, 2015. URL: https://doi.org/10.1145/2767386.2767434.
  17. Ted Herman and Sriram V. Pemmaraju. Error-detecting codes and fault-containing self-stabilization. Inf. Process. Lett., 73(1-2):41-46, 2000. URL: https://doi.org/10.1016/S0020-0190(99)00164-7.
  18. Gene Itkis and Leonid A. Levin. Fast and lean self-stabilizing asynchronous protocols. In 35th Annual Symposium on Foundations of Computer Science FOCS 1994, pages 226-239, 1994. URL: https://doi.org/10.1109/SFCS.1994.365691.
  19. Gene Itkis, Chengdian Lin, and Janos Simon. Deterministic, constant space, self-stabilizing leader election on uniform rings. In Distributed Algorithms, 9th International Workshop, WDAG '95, pages 288-302, 1995. URL: https://doi.org/10.1007/BFb0022154.
  20. Colette Johnen. Memory efficient, self-stabilizing algorithm to construct BFS spanning trees. In Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, PODC 97, page 288, 1997. URL: https://doi.org/10.1145/259380.259508.
  21. Tomasz Jurdzinski and Krzysztof Nowicki. MST in O(1) rounds of congested clique. In 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 2620-2632, 2018. URL: https://doi.org/10.1137/1.9781611975031.167.
  22. Amos Korman and Shay Kutten. Distributed verification of minimum spanning trees. Distributed Computing, 20(4):253-266, 2007. URL: https://doi.org/10.1007/s00446-007-0025-1.
  23. Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Computing, 22(4):215-233, 2010. URL: https://doi.org/10.1007/s00446-010-0095-3.
  24. Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. Minimum-weight spanning tree construction in O(log log n) communication rounds. SIAM J. Comput., 35(1):120-131, 2005. URL: https://doi.org/10.1137/S0097539704441848.
  25. Moni Naor and Larry J. Stockmeyer. What can be computed locally? SIAM J. Comput., 24(6):1259-1277, 1995. URL: https://doi.org/10.1137/S0097539793254571.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact