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?) *n*^{2} O(*n*) for
the complexity of this algorithm. We also show a lower bound of (1?) *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 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?) *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?) *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.