Abstract
In 1974, Dijkstra [D74] introduced the term “self-stabilization” to distinguish any system that has the following property: if the system starts at any, possibly illegitimate state, it is guaranteed to converge to a legitimate state in a finite time.Alternator was proposed by M.G. Gouda and F. Haddix [GH99b] and can be used in realizing many of synchronization problems. An alternator is a network of processes that satisfy the following three conditions. (1) If one process is in critical section, no neighbor of the process will be in critical section at the same time. (2) Along any infinite time, each process enters critical section infinitely often. (3) The alternator is self-stabilizing to the above conditions. The alternator in [GH99b] works under non-uniform networks and may not be an optimal alternator.In this thesis, we will propose a general approach to implementing alternators. By using this approach, we designed optimal alternators for hypercube and mesh. The concept of the approach can also be applied in general, uniform networks for optimal alternators. Protocols in this thesis works under synchronous model.