LAUSR

In 1973 E.W. Dijkstra introduced the notion of self-stabilization in the context of mutual exclusion. Considering the same problem on an array, we present a game theoretic analysis of self-stabilizing systems with three- ‎or four-state machines. We give a formalized definition of the problem as a game where each player’s strategy represents the state of its corresponding machine. For the three-state case, we prove the impossibility of any infinite self-stabilizing systems on an array. For the four-state case we consider two algorithms. For Ghosh’s solution [1] we prove the upper bound of (n – 1)(n – 3) steps and that this bound is tight. Also we present another four-state self-stabilizing system, ‎and prove that at most n2 – 5n + 7 steps are required for the system to reach self-stabilization.