Abstract
In this dissertation, we first propose the concept of edge token and present a self-stabilizing algorithm to implement it. Based on the concept of edge token, many traditional problems are reconsidered and are solved more elegantly, such as ring orientation problem, leader election problem, token circulation problem and neighborhood synchronization problem. A self-stabilizing system guarantees to converge to a legitimate state in a finite time no matter what initial state it may start with. An attractive feature for a self-stabilizing system is that the system can recover from transient faults automatically without any outside intervention. This feature is highly desirable for distributed systems with fault-tolerance consideration. Consider the distributed system as a connected graph with processes (or nodes) and edges. An Edge Token with respect to an edge is a token maintained by the two processes connected by the edge. The token is held by one of the two processes and is passed between them as needed. Due to the exclusive property of edge token, different kinds of strategies for edge token holding can be used to solve the traditional problems efficiently. In the dissertation, we propose four self-stabilizing algorithms based on edge tokens: ring orientation, leader election for trees, token circulation for trees and neighborhood synchronization for trees. All the proposed algorithms are uniform and work under the distributed scheduler with read/write atomicity. Moreover, since each process only refers to its local state, these algorithms are simple and intuitive. The results are better than the previous works either in time complexity or in their elegancy. Beside that, a related self-stabilizing algorithm for planar graph coloring is proposed and the approach for neighborhood synchronization that does not use edge tokens is also given in Appendix for reference.