Limits and power of the simplest uniform and self-stabilizing phase clock algorithm

In this paper, the phase clock algorithm which stabilizes on general graphs is studied on anonymous rings. The authors showed that this K-clock algorithm works with K⩾2D, where D is the diameter of the graph. We prove that this algorithm works on unidirectional (bidirectional) rings iff K satisfies K>K´K/K´+n(2K>2K´-K/K´+n, respectively) where K´ is the greatest divisor of K (K´≠K) and n is the size of the ring. From this characterization, we show that any ring stabilizes with some K<2D if K is odd. We also prove that, if K is prime, unidirectional and bidirectional rings stabilize with K<2[n/2]≃D and K<2[n/3]≃4D/3, respectively. Finally, we generalize the algorithm to synchronize any ring with any clock value