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

Viacheslav Chernoy (M.Sc. Thesis Seminar)

Wednesday, 03.03.2010, 14:00

Taub 601

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.