DocumentCode :
1671655
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
fYear :
1995
Firstpage :
423
Lastpage :
430
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Distributed Computing Systems, 1995., Proceedings of the 15th International Conference on
Conference_Location :
Vancouver, BC
ISSN :
1063-6927
Print_ISBN :
0-8186-7025-8
Type :
conf
DOI :
10.1109/ICDCS.1995.500047
Filename :
500047
Link To Document :
بازگشت