A self-stabilizing algorithm with tight bounds for mutual exclusion on a ring. Submitted for publication, 2008. EW Dijkstra. Self stabilizing systems in spite of distributed control

In [Dij74] Dijkstra introduced the notion of self-stabilizing algorithms and presented, among others, an algorithm with three states for the problem of mutual exclusion on a ring of processors. In this work we present a new three state self-stabilizing algorithm for mutual exclusion, with a tight bound of 56n 2 +O(n) for the worst case complexity, which is the number of moves of the algorithm until it stabilizes. This bound is better than lower bounds of other algorithms, including Dijkstra’s. Using similar techniques we improve the analysis of the upper bound for Dijkstra’s algorithm and show a bound of 31318