Wait-Free Clock Synchronization (Extended Abstract).
Shlomi Dolev, Jennifer Lundelius Welch · 1993
Multi-processor computer systems with many processors are becoming increasingly important as vehicles for solving computationally expensive problems. Synchronization among the processors is achieved with a variety of clock configurations. A new notion of fault-tolerance for clock synchronization algorithms is defined, tailored to the requirements and failure patterns of multiprocessors. Algorithms in this class can tolerate any number of processors that can fail by ceasing operation for an arbitrary time interval and then resuming operation (with or) without recognizing that a fault has occurred. These algorithms guarantee that, for some fixed k, once a processor P has been working correctly for at least k time, then as long as it continues to work correctly, (1) P does not adjust its clock, and (2) P 's clock agrees with the clock of every other processor that has also been working correctly for at least k time. Because a working processor must synchronize in a fixed amou...