On the Performance of Dijkstra's 3rd Self-stabilizing Algorithm for Mutual Exclusion and Related Algorithms

Viacheslav Chernoy, M.Sc. Thesis Seminar
Wednesday, 3.3.2010, 14:00
Taub 601
Prof. Sh. Zaks and Dr. M. Shalom

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\frac{13}{18} n^2 + O(n)$ for the complexity of this algorithm. We also show a lower bound of $1\frac{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-three state self-stabilizing algorithm for mutual exclusion and show a tight bound of $\frac{5}{6} n^2 + 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\frac{3}{4}n^2+O(n)$ and a lower bound of $\frac{1}{8}n^2-O(n)$ for its stabilization time. For this algorithm we prove an upper bound of $1\frac{1}{2}n^2 + O(n)$ and show a lower bound of $n^2 - 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.

Back to the index of events