Abstract
Herman’s algorithm is a synchronous randomized protocol for achieving self-stabilization in a token ring consisting of N processes. The interaction of tokens makes the dynamics of the protocol very difficult to analyze. In this paper we study the distribution of the time to stabilization, assuming that there are three tokens in the initial configuration. We show for arbitrary N and for an arbitrary timeout t that the probability of stabilization within time t is minimized by choosing as the initial three-token configuration the configuration in which the tokens are placed equidistantly on the ring. Our result strengthens a corollary of a theorem of McIver and Morgan (Inf. Process Lett. 94(2): 79–84, 2005), which states that the expected stabilization time is minimized by the equidistant configuration.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Balding D (1988) Diffusion-reaction in one dimension. J Appl Probab 25: 733–743
Cox D, Miller H (2001) The theory of stochastic processes. Chapman & Hall/CRC, London
Durrett, R, Kesten, H (eds) (1991) Random walks, Brownian motion and interacting particle systems. Birkhauser, Verlag
Dijkstra EW (1974) Self-stabilizing systems in spite of distributed control. Commun ACM 17(11): 643–644
Dolev S (2000) Self-stabilization. MIT Press, Cambridge
Fribourg L, Messika S, Picaronny C (2005) Coupling and self-stabilization. Distrib Comput 18: 221–232
Herman T (1990) Probabilistic self-stabilization. Inf Process Lett 35(2):63–67 (technical report at ftp://ftp.math.uiowa.edu/pub/selfstab/H90.html
Kiefer S, Murawski AS, Ouaknine J, Wachter B, Worrell J (2011) Language equivalence for probabilistic automata. In: Proceedings of CAV, volume 6806 of LNCS. Springer, New York, pp 526–540
Kiefer S, Murawski AS, Ouaknine J, Worrell J, Zhang L (2011) On stabilization in Herman’s algorithm. In: Proceedings of ICALP, volume 6756 of LNCS, Springer, New York, pp 466–477
Liggett TM (2005) Interacting particle systems. Springer, Berlin
Legay A, Murawski AS, Ouaknine J, Worrell J (2008) On automated verification of probabilistic programs. In: Proceedings of TACAS, volume 4963 of LNCS. Springer, New York, pp 173–187
McIver A, Morgan C (2005) An elementary proof that Herman’s ring is θ(n 2). Inf. Process. Lett. 94(2): 79–84
Murawski AS, Ouaknine J (2005) On probabilistic program equivalence and refinement. In: Proceedings of CONCUR, volume 3653 of LNCS, Springer, Berlin, pp 156–170
Nakata T (2005) On the expected time for Herman’s probabilistic self-stabilizing algorithm. Theor Comput Sci 349(3): 475–483
PRISM case studies. Randomised self-stabilising algorithms. http://www.prismmodelchecker.org/casestudies/self-stabilisation.php
Schneider M (1993) Self-stabilization. ACM Comput. Surv. 25(1): 45–67
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Peter Höfner, Robert van Glabbeek and Ian Hayes
Research supported by EPSRC (EP/G069158/1). Stefan Kiefer is supported by a postdoctoral fellowship of the German Academic Exchange Service (DAAD).
Rights and permissions
About this article
Cite this article
Kiefer, S., Murawski, A.S., Ouaknine, J. et al. Three tokens in Herman’s algorithm. Form Asp Comp 24, 671–678 (2012). https://doi.org/10.1007/s00165-012-0228-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00165-012-0228-5