Title :
Distributed algorithms for detecting conjunctive predicates
Author :
Garg, Vijay K. ; Chase, Craig M.
Author_Institution :
Parallel & Distributed Syst. Lab., Texas Univ., Austin, TX, USA
Abstract :
This paper discusses efficient distributed detection of global conjunctive predicates in a distributed program. Our methods correctly detect the first consistent cut in which the predicate is true, even if the predicate is unstable. Previous work in detection of such predicates is based on a centralized checker process. In this paper we introduce algorithms which distribute the computation and space requirements of the detection procedure. Two algorithms are presented. The first algorithm requires O (n2 m) time and space where m is the number of messages sent by any process and n is the number of processes over which the predicate is defined. This algorithm has identical time complexity to the original centralized algorithm. However computation, space and message requirements are distributed evenly over the n processes. The second algorithm requires 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 efficient for a specific application. Parallelism can be introduced into either distributed algorithm, reducing the average case time complexity. We show that the worst-case time complexity can not be improved beyond O(mn) with any on-line detection algorithm
Keywords :
computational complexity; distributed algorithms; centralized checker process; conjunctive predicates detection; distributed algorithms; distributed detection; distributed program; global conjunctive predicates; message requirements; time complexity; Clocks; Communication channels; Debugging; Detection algorithms; Distributed algorithms; Distributed computing; Instruments; Laboratories; Lifting equipment; Parallel processing; Testing;
Conference_Titel :
Distributed Computing Systems, 1995., Proceedings of the 15th International Conference on
Conference_Location :
Vancouver, BC
Print_ISBN :
0-8186-7025-8
DOI :
10.1109/ICDCS.1995.500047