In: Mavronicolas, M.; Tsigas, Ph.: Lecture Notes in Computer Science, Vol. 1320: Distributed Algorithms, Proc. of 11th International Workshop, WDAG'97, Saarbrücken, Germany, pages 290-304. Springer, September 1997.
Abstract: We consider wait-free clock synchronization protocols on an in-phase shared memory multi-processor system. A wait-free clock synchronization protocol guarantees that, for a fixed k, local clocks of processors which have been working consecutively for at least k pulses are synchronized. Such k is called synchronization time. The best previous result with regard to the synchronization time is O(nē), where n is the number of processors. In this paper, we present a wait-free synchronization protocol with synchronization time O(n), and also show that this synchronization time is asymptotically optimal.
Keywords: clock-synchronization, shared-memory multi-processor system, wait-freedom, fault-tolerance, napping fault..