Abstract
In this paper, we propose a silent self-stabilizing leader election algorithm for bidirectional connected identified networks of arbitrary topology. This algorithm is written in the locally shared memory model. It assumes the distributed unfair daemon, the most general scheduling hypothesis of the model. Our algorithm requires no global knowledge on the network (such as an upper bound on the diameter or the number of processes, for example). We show that its stabilization time is in Θ(n 3) steps in the worst case, where n is the number of processes. Its memory requirement is asymptotically optimal, i.e., Θ(logn) bits per processes. Its round complexity is of the same order of magnitude — i.e., Θ(n) rounds — as the best existing algorithm [10] designed with similar settings. To the best of our knowledge, this is the first self-stabilizing leader election algorithm for arbitrary identified networks that is proven to achieve a stabilization time polynomial in steps. By contrast, we show that the previous best existing algorithm designed with similar settings [10] stabilizes in a non polynomial number of steps in the worst case.
This work has been partially supported by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025-01) funded by the French program Investissement d’avenir and the AGIR project DIAMS.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Afek, Y., Bremler-Barr, A.: Self-Stabilizing Unidirectional Network Algorithms by Power Supply. Chicago J. Theor. Comput. Sci. 1998 (1998)
Altisen, K., Cournier, A., Devismes, S., Durand, A., Petit, F.: Self-Stabilizing Leader Election in Polynomial Steps. Tech. rep., CNRS (2014), http://hal.archives-ouvertes.fr/hal-00980798
Arora, A., Gouda, M.G.: Distributed Reset. IEEE Trans. Computers 43(9), 1026–1038 (1994)
Awerbuch, B., Kutten, S., Mansour, Y., Patt-Shamir, B., Varghese, G.: Time Optimal Self-stabilizing Synchronization. In: STOC, pp. 652–661 (1993)
Blin, L., Tixeuil, S.: Brief Announcement: Deterministic Self-stabilizing Leader Election with O(log log n)-bits. In: PODC, pp. 125–127 (2013)
Burman, J., Kutten, S.: Time Optimal Asynchronous Self-stabilizing Spanning Tree. In: Pelc, A. (ed.) DISC 2007. LNCS, vol. 4731, pp. 92–107. Springer, Heidelberg (2007)
Chang, E.J.H.: Echo Algorithms: Depth Parallel Operations on General Graphs. IEEE Trans. Software Eng. 8(4), 391–401 (1982)
Datta, A.K., Larmore, L.L., Piniganti, H.: Self-stabilizing Leader Election in Dynamic Networks. In: Dolev, S., Cobb, J., Fischer, M., Yung, M. (eds.) SSS 2010. LNCS, vol. 6366, pp. 35–49. Springer, Heidelberg (2010)
Datta, A.K., Larmore, L.L., Vemula, P.: An O(n)-time Self-stabilizing Leader Election Algorithm. J. Parallel Distrib. Comput. 71(11), 1532–1544 (2011)
Datta, A.K., Larmore, L.L., Vemula, P.: Self-stabilizing Leader Election in Optimal Space under an Arbitrary Scheduler. Theor. Comput. Sci. 412(40), 5541–5561 (2011)
Dijkstra, E.W.: Self-stabilizing Systems in Spite of Distributed Control. Commun. ACM 17(11), 643–644 (1974)
Dolev, S., Gouda, M.G., Schneider, M.: Memory Requirements for Silent Stabilization. Acta Inf. 36(6), 447–462 (1999)
Dolev, S., Herman, T.: Superstabilizing Protocols for Dynamic Distributed Systems. Chicago J. Theor. Comput. Sci. 1997 (1997)
Kravchik, A., Kutten, S.: Time Optimal Synchronous Self Stabilizing Spanning Tree. In: Afek, Y. (ed.) DISC 2013. LNCS, vol. 8205, pp. 91–105. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Altisen, K., Cournier, A., Devismes, S., Durand, A., Petit, F. (2014). Self-stabilizing Leader Election in Polynomial Steps. In: Felber, P., Garg, V. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2014. Lecture Notes in Computer Science, vol 8756. Springer, Cham. https://doi.org/10.1007/978-3-319-11764-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-11764-5_8
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11763-8
Online ISBN: 978-3-319-11764-5
eBook Packages: Computer ScienceComputer Science (R0)