Abstract
In [7] Dijkstra introduced the notion of self-stabilizing algorithms, and presented three such algorithms for the problem of mutual exclusion on a ring of processors. The third algorithm is the most interesting of these three, but is rather non intuitive. In [8] a proof of its correctness was presented, but the question of determining its worst case complexity – that is, providing an upper bound on the number of moves of this algorithm until it stabilizes – remained open. In this paper we solve this question, and prove an upper bound of O(n 2) (n being the size of the ring) for this algorithm’s complexity. This complexity applies to a centralized as well as to a distributed scheduler.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Beauquier, J., Debas, O.: An optimal self-stabilizing algorithm for mutual exclusion on bidirectional non uniform rings. In: Proceedings of the Second Workshop on Self-Stabilizing Systems, pp. 17.1–17.13 (1995)
Beauquier, J., Johnen, C., Messika, S.: Brief announcement: Computing automatically the stabilization time against the worst and the best schedules. In: Dolev, S. (ed.) DISC 2006. LNCS, vol. 4167, pp. 543–547. Springer, Heidelberg (2006)
Burns, J.E., Gouda, M.G., Miller, R.E.: On relaxing interleaving assumptions. In: Proceedings of the MCC Workshop on Self-Stabilizing Systems, MCC Technical Report No. STP-379-89 (1989)
Chang, E.J.H., Gonnet, G.H., Rotem, D.: On the costs of self-stabilization. Information Processing Letters 24, 311–316 (1987)
Chernoy, V., Shalom, M., Zaks, S.: Better bounds for Dijkstra’s 3rd algorithm on mutual exclusion. (in preparation)
Cobb, J.A., Gouda, M.G.: Stabilization of general loop-free routing. Journal of Parallel and Distributed Computing 62(5), 922–944 (2002)
Dijkstra, E.W.: Self stabilizing systems in spite of distributed control. Communications of the Association of the Computing Machinery 17(11), 643–644 (1974)
Dijkstra, E.W.: A belated proof of self-stabilization. Distributed Computing 1, 5–6 (1986)
Dolev, S.: Self-Stabilization. MIT Press, Cambridge (2000)
Kessels, J.L.W.: An exercise in proving self-stabilization with a variant function. Information Processing Letters 29, 39–42 (1988)
Kruijer, H.S.M.: Self-stabilization (in spite of distributed control) in tree-structured systems. Information Processing Letters 8, 91–95 (1979)
Nakaminami, Y., Kakugawa, H., Masuzawa, T.: An advanced performance analysis of self-stabilizing protocols: stabilization time with transient faults during convergence. In: IPDPS 2006. 20th International Parallel and Distributed Processing Symposium, 25-29 April 2006. Rhodes Island, Greece, (2006)
Schneider, M.: Self-stabilization. ACM Computing Surveys 25, 45–67 (1993)
Tchuente, M.: Sur l’auto-stabilisation dans un réseau d’ordinateurs. RAIRO Informatique Theoretique 15, 47–66 (1981)
Tsuchiya, T., Tokuda, Y., Kikuno, T.: Computing the stabilization times of self-stabilizing systems. IEICE Transactions on Fundamentals of Electronic Communications and Computer Sciences E83A(11), 2245–2252 (2000)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chernoy, V., Shalom, M., Zaks, S. (2007). On the Performance of Dijkstra’s Third Self-stabilizing Algorithm for Mutual Exclusion. In: Masuzawa, T., Tixeuil, S. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2007. Lecture Notes in Computer Science, vol 4838. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-76627-8_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-76627-8_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-76626-1
Online ISBN: 978-3-540-76627-8
eBook Packages: Computer ScienceComputer Science (R0)