Phase synchronization on asynchronous uniform rings with odd size

This paper proposes a self-stabilizing phase synchronization protocol for u niform rings with an odd size. Nodes in the ring work asynchronously and pr oceed in a cyclic sequence of K phases, where K is even. The phase values o f all the nodes are required to be no more than one apart. A system state w hich satisfies the requirement is therefore called a legitimate state. The proposed protocol guarantees that no matter with which initial state the sy stem may start, the ring stabilizes eventually at a state after which the c losure property on the legitimate state holds. Phase values should never go backward. The closure property on the legitimate states commonly used in p revious works on self-stabilization cannot capture this requirement. This p aper defines two terms, legitimate step and illegitimate step, to address t his issue. An execution step that brings the ring from a legitimate state t o another legitimate state in a way that the phase values of the nodes only advance is called a legitimate step. An execution step that observes the c losure property on the legitimate states but makes some phase values go bac kward is modeled as an illegitimate step. It is shown that. for the propose d protocol, only a finite number of illegitimate steps are possible. After all possible illegitimate steps have occurred, the closure property on the legitimate steps holds.