Distributed Algorithms for Detecting Conjunctive Predicates

This paper discusses ecient distributed detection of global conjunctive predicates in a distributed program. Previous work in detection of such predicates is based on a checker process. The checker process requires O(n 2 m) time and space where m is the number of messages sent or received by any process and n is the number of processes over which the predicate is dened. In this paper, we introduce token-based algorithms which distribute the computation and space requirements of the detection procedure. The distributed algo-rithm has O(n 2 m) time, space and message complexity, distributed such that each process performs O(nm) work. We describe another distributed algorithm with O(Nm) total work, where N is the total number of processes in the system. The relative values of n and N determine which algorithm is more ecient for a specic application.