Article Preview
TopIntroduction
The problem of detecting distributed predicates (runtime verification) has attracted attention in the domain of asynchronous distributed systems (Yingchareonthawornchai et al., 2017; Natarajan et al., 2017; Chang and Garg, 2016; Zhu et al., 2016; Chauhan et al., 2013; Freiling and Jhumka, 2007; Garg, 2002; Dumais and Li, 2002). Several researchers have developed techniques to solve this problem. These techniques can be used to verify the satisfaction of some predefined properties (represented as predicates) in a run of a distributed application. Figure 1 demonstrates the distributed predicates detection environment (Maghayreh, 2010).
Figure 1. Distributed predicates detection environment (Maghayreh, 2010)
Distributed predicates detection techniques operate on a specific implementation of a distributed system. On the other hand, model checking techniques operate on an abstract model of the system. As a result, distributed predicates detection techniques can be more powerful in reasoning about the correctness of a specific implementation of a distributed system (Garg, 2002; Maghayreh, 2010).
Developers of distributed applications can use detection techniques in testing and debugging. For example, to implement one of the most common debugging commands “Stop the program when predicate P becomes true”, you need to detect the satisfaction of P. If predicate P involves variables of different processes in a distributed program, then the development of an efficient detection algorithm might be a very difficult task.
Due to concurrency, detecting distributed predicates is a very difficult and time-consuming job. Researchers have suggested several techniques to decrease the cost of detecting certain classes of distributed predicates (Zhu et al., 2016; Chauhan et al., 2013; Maghayreh, 2010; Garg, 2002). In Section 3, we will summarize some of these techniques. However, it has been proved that detecting a distributed predicate in a run of a distributed application is an NP-complete problem in general (Garg, 2002).
In (Karaboga and Basturk, 2008; Karaboga and Akay, 2009), a swarm intelligent algorithm known as the artificial bee colony (ABC) algorithm has been proposed. The ABC algorithm simulates the behavior of real bees in searching for food sources and exchanging the information with other bees. The main idea of the ABC algorithm is not complex, and it’s easy to implement. The ABC algorithm has been exploited in solving several problems in different domains (Senberber and Bagis, 2017; Koza and Karaboga, 2017; Ozdemr et al., 2017; Shaik and Reddy, 2016; Yang et al., 2015). In this paper, we have utilized the ABC algorithm in developing a powerful distributed predicates detection technique. The proposed technique can detect the satisfaction of any distributed predicate under the possibly modality (the possibly modality will be defined in the next section). Several experiments have been conducted to evaluate the performance of the ABC-based detection technique.