A Simulated Annealing Based Algorithm for Detecting Distributed Predicates

Improving the dependability of distributed applications is a challenging task. Distributed predicates detection techniques (runtime verification) can help a lot in this regard by verifying that a given run of a distributed application satisfies certain properties (formally modeled as predicates). In general, these techniques can be exploited in the verification of the correctness of a particular implementation of a distributed system. In any distributed application, several processes are usually running concurrently. Consequently, the number of global states to be considered by the detection techniques is exponential (NP-Complete problem). In this paper, we have investigated the effectiveness of using a meta-heuristic algorithm in solving the problem of detecting distributed predicates. Namely, we have used the simulated annealing (SA) algorithm to develop an algorithm to detect distributed predicates. The results of the experiments demonstrate that the SA-based detection technique outperforms the state enumeration based detection technique.