In Dijkstra (Commun ACM 17(11):643-644, 1974) introduced the notion of self-stabilizing algorithms and presented three such algorithms for the problem of mutual exclusion on a ring of n processors. The third algorithm...
详细信息
In Dijkstra (Commun ACM 17(11):643-644, 1974) introduced the notion of self-stabilizing algorithms and presented three such algorithms for the problem of mutual exclusion on a ring of n processors. The third algorithm is the most interesting of these three but is rather non intuitive. In Dijkstra (Distrib Comput 1:5-6, 1986) 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 3(13)/(18)n(2) + O(n) for the complexity of this algorithm. We also show a lower bound of 1(5)/(6)n(2) - O(n) for the worst case complexity. For computing the upper bound, we use two techniques: potential functions and amortized analysis. We also present a new-threestate self-stabilizing algorithm for mutual exclusion and show a tight bound of (5)/(6)n(2) + O(n) for the worst case complexity of this algorithm. In Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1-17.13, 1995) presented a similar three-state algorithm, with an upper bound of 5(3)/(4)n(2) + O(n) and a lower bound of (1)/(8)n(2) - O(n) for its stabilization time. For this algorithm we prove an upper bound of 1(1)/(2)n(2) + O(n) and show a lower bound of n(2) - O(n). As far Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1-17.13, 1995) is better than the one in Dijkstra (Commun ACM 17(11): 643-644, 1974) and our algorithm is better than both.
暂无评论