Abstract
A randomized self-stabilizing algorithm \({\cal A}\) is an algorithm that, whatever the initial configuration is, reaches a set \({\cal L}\) of legal configurations in finite time with probability 1. The proof of convergence towards \({\cal L}\) is generally done by exhibiting a potential function ϕ, which measures the “vertical” distance of any configuration to \({\cal L}\), such that ϕ decreases with non-null probability at each step of \({\cal A}\). We propose here a method, based on the notion of coupling, which makes use of a “horizontal” distance δ between any pair of configurations, such that δ decreases in expectation at each step of \({\cal A}\). In contrast with classical methods, our coupling method does not require the knowledge of \({\cal L}\). In addition to the proof of convergence, the method allows us to assess the convergence rate according to two different measures. Proofs produced by the method are often simpler or give better upper bounds than their classical counterparts, as examplified here on Herman’s mutual exclusion and Iterated Prisoner’s Dilemma algorithms in the case of cyclic graphs.
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
Aldous, A., Fill, J.: Reversible Markov Chains and Random Walks on Graph (to appear), draft at http://www.stat.Berkeley.EDU/users/aldous/book.html
Aspnes, J., Herlihy, M.: Fast randomized consensus using shared memory. Journal of Algorithms 11(3), 441–461 (1990)
Bubley, R., Dyer, M.: Path coupling: A technique for proving rapid mixing in Markov chains. In: Proc. of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1997), pp. 223–231 (1997)
Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Communications of the ACM 17(11), 643–644 (1974)
Dolev, S., Israeli, A., Moran, S.: Analyzing expected time by scheduler luck games. IEEE transactions on Software Engineering 21(5), 429–439 (1995)
Duflot, M., Fribourg, L., Picaronny, C.: Randomized distributed algorithms as Markov chains. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol. 2180, pp. 240–254. Springer, Heidelberg (2001)
Dyer, M., Goldberg, L.A., Greenhill, C., Istrate, G., Jerrum, M.: Convergence of the Iterated Prisoner’s Dilemma Game. Combinatorics, Probability and Computing 11(2) (2002)
Dyer, M.E., Greenhill, C.: A more rapidly mixing Markov chain for graph colorings. Random Structures and Algorithms 13, 285–317 (1998)
Flatebo, M., Datta, A.K.: Two-state self-stabilizing algorithms for token rings. IEEE Transactions on Software Engineering 20(6), 500–504 (1994)
Herman, T.: Probabilistic self-stabilization. IPL 35(2), 63–67 (1990)
Huber, M.: Exact sampling and approximate counting techniques. In: Proc. of the 30th Annual ACM Symp. on Theory of Computing (STOC 1998), pp. 31–40 (1998)
Kemeny, J.G., Snell, J.L.: Finite Markov Chains. D. van Nostrand Co. (1969)
Kittock, J.E.: Emergent conventions and the structure of multi-agent systems. In: Nadel, L., Stein, D. (eds.) Proc. of the 1993 Complex systems summer school. Santa Fe Institute Studies in the Sciences of Complexity, Addison-Wesley, Reading (1995)
Lamport, L.: Solved problems, unsolved problems and non-problems in concurrency. In: Proc. of the 3rd ACM Symp. on Principles of Distributed Computing (PODC 1984), pp. 1–11 (1984)
Lovász, L., Winkler, P.: Mixing Times. In: Microsurveys in Discrete Probability, pp. 85–134 (1998)
Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann Publishers, Inc., San Francisco (1997)
Mayer, A., Ostrovsky, R., Yung, M.: Self-Stabilizing Algorithms for Synchronous Unidirectional Rings. In: Proc. of the 7th ACM-SIAM Symp. on Discrete Algorithms, SODA 1996 (1996)
Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Interscience, Hoboken (1994)
Randall, D.: Mixing. In: Proc. of the 44th Annual IEEE Symp. on Foundations of Computer Science, FOCS 2003 (2003)
Schneider, M.: Self-stabilization. ACM Computing Surveys 25, 45–67 (1993)
Segala, R.: Modeling and Verification of Randomized Distributed Real-Time Systems. PhD thesis, Massachusetts Institue of Technology (June 1995)
Sinclair, A.: Convergence rates for Monte Carlo experiments. In: Numerical Methods for Polymeric Systems. Mathematics & Its application, vol. IMA, pp. 1–18 (1997)
Williams, D.: Probability with Martingales. Cambridge University Press, Cambridge (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fribourg, L., Messika, S., Picaronny, C. (2004). Coupling and Self-stabilization. In: Guerraoui, R. (eds) Distributed Computing. DISC 2004. Lecture Notes in Computer Science, vol 3274. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30186-8_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-30186-8_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23306-0
Online ISBN: 978-3-540-30186-8
eBook Packages: Springer Book Archive