For the most recent entries see the Petri Nets Newsletter.

Optimal Wait-Free Clock Synchronization Protocol on a Shared-Memory Multi-Processor System.

Inoue, Michiko; Moriya, Sen; Masuzawa, Toshimitsu; Fujiware, Hideo

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..


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography