Abstract
In this dissertation, we study the self-stabilizing unison protocols on uniform systems. A self-stabilizing system does not need any initialization; it guarantees that the system reaches some legitimate state after a finite number of steps. This makes a self-stabilizing system be able to cope with transient faults. Many distributed systems have to proceed in consecutive phases. In such systems, all processors must have their computation synchronized. Therefore, the unison problems are fundamental problems for the distributed systems. There are two types of unison systems: one is the synchronous unison system and the other is the asynchronous phase synchronization system. In this dissertation, we study these two kinds of systems on uniform rings. Three synchronous unison protocols and one asynchronous phase synchronization protocol are proposed. The first protocol is a binary clock protocol. In the binary clock protocol, each processor only requires two binary variables. This protocol improves the previous results on synchronous unison problems if the processor state is a major consideration. The second protocol is a 2^m-clock protocol, where m is any positive integer. This protocol can be applied on the applications in which each round has 2^m phases. Besides the variables for maintaining the clocks, in the 2^m-clock protocol, each processor only requires one additional bit. The third protocol is a randomized K-clock protocol, where K is any positive integer. The K-clock protocol breaks the symmetric actions by the random decision and the expected number of phases for the system to be synchronized is O(n^2), where n is the number of processors in the ring. The last protocol is an asynchronous phase synchronization protocol for uniform rings with odd size. This protocol guarantees that all phase values among all processors are never more than one apart when the system is synchronized.