Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

On the Performance of Dijkstra's 3rd Self-stabilizing Algorithm for Mutual Exclusion and Related Algorithms
event speaker icon
Viacheslav Chernoy (M.Sc. Thesis Seminar)
event date icon
Wednesday, 03.03.2010, 14:00
event location icon
Taub 601
event speaker icon
Advisor: 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.