×

On stabilization in Herman’s algorithm. (English) Zbl 1333.68038

Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-22011-1/pbk). Lecture Notes in Computer Science 6756, 466-477 (2011).
Summary: 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 expected time to stabilization in terms of the initial configuration.
It is straightforward that the algorithm achieves stabilization almost surely from any initial configuration, and it is known that the worst-case expected time to stabilization (with respect to the initial configuration) is \(\Theta (N ^{2})\). Our first contribution is to give an upper bound of \(0.64N ^{2}\) on the expected stabilization time, improving on previous upper bounds and reducing the gap with the best existing lower bound. We also introduce an asynchronous version of the protocol, showing a similar \(O(N ^{2})\) convergence bound in this case.
Assuming that errors arise from the corruption of some number \(k\) of bits, where \(k\) is fixed independently of the size of the ring, we show that the expected time to stabilization is \(O(N)\). This reveals a hitherto unknown and highly desirable property of Herman’s algorithm: it recovers quickly from bounded errors. We also show that if the initial configuration arises by resetting each bit independently and uniformly at random, then stabilization is significantly faster than in the worst case.
For the entire collection see [Zbl 1217.68004].

MSC:

68M12 Network protocols
68M14 Distributed systems
68W15 Distributed algorithms
68W20 Randomized algorithms

Software:

PRISM
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Balding, D.: Diffusion-reaction in one dimension. J. Appl. Prob. 25, 733–743 (1988) · Zbl 0658.60112
[2] PRISM case studies. Randomised self-stabilising algorithms, http://www.prismmodelchecker.org/casestudies/self-stabilisation.php
[3] Cox, D., Miller, H.: The theory of stochastic processes. Chapman & Hall/CRC (2001) · Zbl 0149.12902
[4] Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Commun. ACM 17(11), 643–644 (1974) · Zbl 0305.68048
[5] Dolev, S.: Self-Stabilization. MIT Press, Cambridge (2000) · Zbl 1026.93001
[6] Durrett, R., Kesten, H.: Random Walks, Brownian Motion and Interacting Particle Systems. Birkhauser Verlag AG, Basel (1991) · Zbl 0733.00027
[7] Feller, W.: An introduction to probability theory and its applications, vol. 1. John Wiley & Sons, Chichester (1968) · Zbl 0155.23101
[8] Flatebo, M., Datta, A.K.: Two-state self-stabilizing algorithms for token rings. IEEE Trans. Softw. Eng. 20(6), 500–504 (1994) · Zbl 05113992
[9] Fribourg, L., Messika, S., Picaronny, C.: Coupling and self-stabilization. Distributed Computing 18, 221–232 (2005) · Zbl 1264.68216
[10] Habib, S., Lindenberg, K., Lythe, G., Molina-Paris, C.: Diffusion-limited reaction in one dimension: Paired and unpaired nucleation. Journal of Chemical Physics 115, 73–89 (2001)
[11] Herman, T.: Probabilistic self-stabilization. Information Processing Letters 35(2), 63–67 (1990), Technical Report at ftp://ftp.math.uiowa.edu/pub/selfstab/H90.html · Zbl 0697.68027
[12] Israeli, A., Jalfon, M.: Token management schemes and random walks yield self-stabilizing mutual exclusion. In: Proceedings of PODC 1990, pp. 119–131. ACM, New York (1990)
[13] Kiefer, S., Murawski, A., Ouaknine, J., Worrell, J., Zhang, L.: On stabilization in Herman’s algorithm. Technical report, arxiv.org (2011), http://arxiv.org/abs/1104.3100 · Zbl 1333.68038
[14] Kutten, S., Patt-Shamir, B.: Stabilizing time-adaptive protocols. Theor. Comput. Sci. 220(1), 93–111 (1999) · Zbl 0916.68009
[15] Liggett, T.M.: Interacting particle systems. Springer, Heidelberg (2005) · Zbl 1103.82016
[16] McIver, A., Morgan, C.: An elementary proof that Herman’s ring is {\(\theta\)}(n 2). Inf. Process. Lett. 94(2), 79–84 (2005) · Zbl 1182.68358
[17] Nakata, T.: On the expected time for Herman’s probabilistic self-stabilizing algorithm. Theoretical Computer Science 349(3), 475–483 (2005) · Zbl 1086.68020
[18] Schneider, M.: Self-stabilization. ACM Comput. Surv. 25(1), 45–67 (1993)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.