On Self-Stabilizing Wait-Free Clock Synchronization
Marina Papatriantafilou, Philippas Tsigas · Parallel Processing Letters · 1997
A protocol which can tolerate any number of processors failing by ceasing operation for unbounded time and resuming operation (with or) without knowing that they were faulty is called wait-free; if it also works correctly even when the starting state of the system is arbitrary, it is called wait-free, self-stabilizing. This work is on the problem of wait-free, self-stabilizing clock synchronization of n processors in "in-phase" multiprocessor systems and presents a protocol that achieves quadratic synchronization time, by "re-parameterizing" and improving the best previously known solution, which had cubic synchronization time. Both the protocol and its analysis are intuitive and easy to understand.