AN OPTIMAL ALGORITHM FOR GLOBAL TERMINATION DETECTION IN SHARED-MEMORY ASYNCHRONOUS MULTIPROCESSOR SYSTEMS

In the literature, the problem of global termination detection in para llel systems is usually solved by message passing. In shared-memory sy stems, this problem can also be solved by using exclusively accessible variables with locking mechanisms. In this paper, we present an algor ithm that solves the problem of global termination detection in shared -memory asynchronous multiprocessor systems without using locking. We assume a reasonable computation model in which concurrent reading does not require locking and concurrent writing different values without l ocking results in an arbitrary one of the values being actually writte n. For a system of n processors, the algorithm allocates a working spa ce of 2n + 1 bits. The worst case time complexity of the algorithm is n + 2 root n + 1, which we prove is the lower bound under a reasonable model of computation.