Abstract
This paper makes two contributions: (1) On a completely connected network of n anonymous processes, it presents a synchronous randomized algorithm to solve the weak leader election problem in expected O(1) time using \(O(\sqrt{n} \log n)\) messages with high probability, (2) It presents a self-stabilizing algorithm for the strong leader election problem on a completely connected network of processes with unique ids – it stabilizes in expected O(1) number of rounds (or in O(logn) rounds with high probability) using O(n) messages. In doing so, the algorithm also solves the stabilizing unison problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Katz, S., Perry, K.J.: Self-stabilizing extensions for message-passing systems. Distrib. Comput. 7(1), 17–26 (1993), http://dx.doi.org/10.1007/BF02278852
Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: Sublinear bounds for randomized leader election. In: Frey, D., Raynal, M., Sarkar, S., Shyamasundar, R.K., Sinha, P. (eds.) ICDCN 2013. LNCS, vol. 7730, pp. 348–362. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Alsulaiman, T., Berns, A., Ghosh, S. (2013). Low-Communication Self-stabilizing Leader Election in Large Networks. In: Higashino, T., Katayama, Y., Masuzawa, T., Potop-Butucaru, M., Yamashita, M. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2013. Lecture Notes in Computer Science, vol 8255. Springer, Cham. https://doi.org/10.1007/978-3-319-03089-0_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-03089-0_26
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03088-3
Online ISBN: 978-3-319-03089-0
eBook Packages: Computer ScienceComputer Science (R0)