An Optimal Algorithm for Global Termination Detection in Shared-Memory Asynchronous Multiprocessor Systems

In the literature the problem of global termination detection in shared-memory asynchronous multiprocessor systems is solved by using exclusively accessible variables and locking mechanism. In this paper we present an algorithm that solves this problem without using locking. We assume that concurrent reading does not require locking and concurrent writing different values without locking results in arbitrary one of the values being actually written. For a system of n processors, the algorithm allocates a working space of 2n+1 bits. The worst case time complexity of the algorithm is n + 2 p n + 1, which we prove is the lower bound. 1 Introduction Consider a system of shared-memory asynchronous autonomous processors in which a processor can `throw' jobs to other processors at any time. The detection of global termination of execution in such a system is nontrivial: jobs could be thrown when the termination detection algorithm is being executed, and it is possible that global terminat..