One of the techniques that have been used in the literature to enhance the dependability of distributed applications is the detection of distributed predicates techniques (also referred to as runtime verification). These techniques are used to verify that a given run of a distributed application satisfies certain properties (specified as predicates). Due to the existence of multiple processes running concurrently, the detection of a distributed predicate can incur significant overhead. Several researchers have worked on the development of techniques to reduce the cost of detecting distributed predicates. However, most of the techniques presented in the literature work efficiently for specific classes of predicates, like conjunctive predicates. This chapter presents a technique based on genetic algorithms to efficiently detect distributed predicates under the possibly modality. Several experiments have been conducted to demonstrate the effectiveness of the proposed technique.
TopIntroduction
Enhancing the dependability of distributed applications is a very difficult task. Many techniques were proposed and developed by several authors to help in improving the dependability of distributed applications. Distributed predicates detection techniques are one of the key techniques that have been developed and used by several researchers (Yingchareonthawornchai et al., 2017; Zhu et al., 2016; Shen and Kshemkalyani, 2014; Garg, 2002; Dumais & Li, 2002; Freiling & Jhumka, 2007; Chu & Brockmeyer, 2008; Garg & Waldecker, 1994; Garg & Waldecker, 1996). These techniques are used to verify that a specific run of a given distributed application satisfies certain properties. Figure 1 depicts the main components of a distributed predicates detection framework.
Model checking and theorem proving techniques can be used to verify that a particular model of a distributed application satisfies certain properties. However, for some distributed applications, especially those employed in safety critical environments, it is important to verify the correctness of a particular implementation rather than an abstract model of the application. This is one of the main strong sides of distributed predicates detection techniques (Garg, 2002; Al Maghayreh, 2010).
Figure 1. The main components of a distributed predicates detection framework
Algorithms for detecting distributed predicates have several applications, including the following:
- •
Detection of Stable States in Distributed Systems: Stable states are usually described by conditions that once become true they will not turn false anymore. For example, deadlock detection and loss of token in a token ring.
- •
Testing and Debugging of Distributed Applications: For example, to test a leader election program, we can monitor the system to detect the presence of multiple leaders.
- •
Identifying Bottlenecks: This involves locating positions during the execution of a distributed application when more than n processes are blocked simultaneously.
- •
Symmetry in Communications: For example, identifying when a producer starts generating items faster than what the corresponding consumer can receive and process.
Due to the concurrency in distributed applications, the detection of distributed predicates is a tedious time-consuming task. In order to reduce the time to solve this problem, several techniques have been proposed and developed in the literature (Yingchareonthawornchai et al., 2017; Zhu et al., 2016; Al Maghayreh, 2010; Garg, 2002; Chase & Garg, 1998). A brief review of these techniques will be presented in Section 4. However, most of these techniques work efficiently for certain classes of predicates only. It has been proved that the detection of the satisfaction of certain property (predicate) in a run of a distributed application is, in general, an NP-complete problem (Garg, 2002).