M.Sc Thesis | |
M.Sc Student | Chernoy Viacheslav |
---|---|
Subject | On the Performance of Dijkstra's Third Self-Stabilizing Algorithm for Mutual Exclusion and Related Algorithms |
Department | Department of Computer Science | Supervisors | PROFESSOR EMERITUS Shmuel Zaks |
PROF. Mordohay Salom | |
Full Thesis text | ![]() |
In a paper of 1974 Dijkstra 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 1986 a proof of its correctness was presented by Dijkstra, 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 work we solve this question and prove an upper bound of (3?) n2 O(n) for the complexity of this algorithm. We also show a lower bound of (1?) n2 - 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-three state self-stabilizing algorithm for mutual exclusion and show a tight bound of 5/6 n2 O(n) for the worst case complexity of this algorithm. In 1995 Beauquier and Debas presented a similar three-state algorithm, with an upper bound of (5?) n2 O(n) and a lower bound of 1/8 n2 - O(n) for its stabilization time. For this algorithm we prove an upper bound of (1?) n2 O(n) and show a lower bound of n2 - O(n). As far as the worst case performance is considered, the algorithm of Beauquier and Debas is better than the one of Dijkstra and our algorithm is better than both.