Universal self-stabilizing phase clock protocol with bounded memory
Florent Nolot, Vincent Villain · 2002
We propose a self-stabilizing K-phase clock protocol which works on uniform tree networks (i.e. without any root). The protocol is self-stabilizing because it guarantees that eventually all clock valve variables will be synchronized and advance in the same value, no matter what the initial state is. It requires (Deg/sub u/+1)K states by processor u, where Deg/sub u/ is the degree of u; i.e., the number of neighbors that processor u has. The worst case stabilization time is D, where D is the diameter of the tree. This is the first universal protocol (i.e. working for any K), whose stabilization time does not depend on K. Moreover, it is the fastest of all the phase clock protocols with bounded memory.