EFFICIENT DISTRIBUTED DETECTION OF CONJUNCTIONS OF LOCAL PREDICATES

Global predicate detection is a fundamental problem in distributed sys tems and finds applications in many domains such as testing and debugg ing distributed programs. This paper presents an efficient distributed algorithm to detect conjunctiva form global predicates in distributed systems. The algorithm detects the first consistent global state that satisfies the predicate even ii the predicate is unstable. Unlike pre viously proposed run-time predicate detection algorithms, our algorith m does not require exchange of control messages during the normal comp utation. AII the necessary information to detect predicates is piggyba cked on computation messages of application programs. The algorithm is distributed because the predicate detection efforts as well as the ne cessary information are equally distributed among the processes. We pr ove the correctness of the algorithm and compare its performance with respect to message, storage, and computational complexities with that of the previously proposed run-time predicate detection algorithms.