Abstract
Self-stabilization algorithms are very important in designing fault-tolerant distributed systems. In this paper we consider Herman’s self-stabilization algorithm and study its expected self-stabilization time. McIver and Morgan have conjectured the optimal upper bound being 0.148N 2, where N denotes the number of processors. We present an elementary proof showing a bound of 0.167N 2, a sharp improvement compared with the best known bound 0.521N 2. Our proof is inspired by McIver and Morgan’s approach: we find a nearly optimal closed form of the expected stabilization time for any initial configuration, and apply the Lagrange multipliers method to give an upper bound of it.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Global Maximum
- Stabilization Time
- Lagrange Multiplier Method
- Strongly Connect Component
- State Markov Chain
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Balding, D.: Diffusion-reaction in one dimension. J. Appl. Prob. 25, 733–743 (1988)
Dijkstra, E.: Self-stabilizing systems in spite of distributed control. Communications of the ACM 17(11), 643–644 (1974)
Dolev, S.: Self-Stabilization. MIT Press (2000)
Feller, W.: An introduction to probability theory and its applications, vol. 1. John Wiley & Sons (1968)
Feng, Y., Zhang, L.: A tighter bound for the self-stabilization time in Herman’s algorithm. Inf. Process. Lett. 113(13), 486–488 (2013)
Fribourg, L., Messika, S., Picaronny, C.: Coupling and self-stabilization. Distributed Computing 18(3), 221–232 (2006)
Herman, T.: Probabilistic self-stabilization. Information Processing Letters 35(2), 63–67 (1990), Report at ftp://ftp.math.uiowa.edu/pub/selfstab/H90.html
Kiefer, S., Murawski, A.S., Ouaknine, J., Wachter, B., Worrell, J.: Three tokens in Herman’s algorithm. Formal Asp. Comput. 24(4-6), 671–678 (2012)
Kiefer, S., Murawski, A.S., Ouaknine, J., Worrell, J., Zhang, L.: On Stabilization in Herman’s Algorithm. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol. 6756, pp. 466–477. Springer, Heidelberg (2011)
Kwiatkowska, M.Z., Norman, G., Parker, D.: Probabilistic verification of Herman’s self-stabilisation algorithm. Formal Asp. Comput. 24(4-6), 661–670 (2012)
Liggett, T.: Interacting particle systems. Springer (2005)
McIver, A., Morgan, C.: An elementary proof that Herman’s ring is Θ(N 2). Inf. Process. Lett. 94(2), 79–84 (2005)
Nakata, T.: On the expected time for Herman’s probabilistic self-stabilizing algorithm. Theoretical Computer Science 349(3), 475–483 (2005)
Schneider, M.: Self-stabilization. ACM Comput. Surv. 25(1), 45–67 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Feng, Y., Zhang, L. (2014). A Nearly Optimal Upper Bound for the Self-Stabilization Time in Herman’s Algorithm. In: Baldan, P., Gorla, D. (eds) CONCUR 2014 – Concurrency Theory. CONCUR 2014. Lecture Notes in Computer Science, vol 8704. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44584-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-662-44584-6_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44583-9
Online ISBN: 978-3-662-44584-6
eBook Packages: Computer ScienceComputer Science (R0)