Distributed algorithm to detect strong conjunctive predicates
This paper presents an on-line distributed algorithm for detection of Definitely(phi) for the class of conjunctive global predicates. The only known algorithm for detection of Definitely(phi) uses a centralized approach. A method for decentralizing the algorithm was also given, but the work load is not fairly distributed and the method uses a hierarchical structure. The centralized approach has a time, space, and total message complexity of O(n(2)m), where n is the number of processes and m is the maximum number of messages sent by any process. The proposed on-line distributed algorithm uses the concept of intervals rather than events, and assumes p is the maximum number of intervals at any process. The worst-case time complexity across all the processes is O(min(pn(2), mn(2))). The worst-case space overhead across all the processes is min(2mn(2), 2pn(2)). (C) 2003 Elsevier B.V. All rights reserved.
distributed computing predicate detection causality global state