Detection of conjunctive stable predicates in dynamic systems

We present a distributed on-line algorithm for detecting conjunctive stable predicates in dynamic systems. The algorithm consists of a virtual network topology to maintain the causality relationships between distributed events and protocols to check the verification of the predicates over consistent global states. A lazy detection protocol has been developed to minimize the number of messages for the detection. Let Mc be the number of detection messages, then the message complexity of the algorithm is Mc ¿ M + n0, where M is the number of computation messages and n0 is the number of initial processes the computation starts with. Computation trees are maintained in the virtual network to reduce the detection delay. Suppose that hmax is the maximum height of the computation trees. The detection delay is O(hmax + n0). It has been proved that a solution is declared if and only if the global predicate is verified during the progress of the underlying distributed computation