Article Preview
Top1. Introduction
Improving the dependability of distributed programs is not an easy task. Many techniques were introduced in the literature to help in developing dependable distributed programs. A key technique which is used by several researchers is the detection of distributed predicates (Garg, 2002; Dumais & Li, 2002; Freiling & Jhumka, 2007; Chu & Brockmeyer, 2008; Garg & Waldecker, 1994; Garg & Waldecker, 1996). In this technique a specific run of a given distributed program is verified against certain properties.
The main components of a distributed predicates detection framework are shown in Figure 1. Algorithms to detect distributed predicates can be used to verify that a particular implementation of a given distributed system satisfies some required properties. Other verification techniques, like model checking, work on a model of the system rather than a particular implementation of it. However, for some distributed applications, especially those employed in safety critical environments, it is important to reason about a particular implementation rather than an abstract model of the system. This is considered one of the main advantages of distributed predicates’ detection techniques (Garg, 2002; Al Maghayreh, 2010).
Figure 1. The main components of a distributed predicates detection framework
The detection of distributed predicates has several applications, including the following:
- •
Detection of when a distributed application reaches some stable state: This includes 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 programs: For example, when testing a leader election algorithm, we can monitor the system to detect the presence of multiple leaders.
- •
Identifying bottlenecks: In this case we are interested in locating positions during the execution of a distributed application when more than n processes blocked at the same time.
- •
Symmetry in Communications: Distributed predicates’ detection techniques can be used to identify when a producer starts generating items faster than what the corresponding consumer can receive and process.
The detection of distributed predicates is a time consuming task due to the concurrency in distributed applications. In order to reduce the time to solve this problem, many methods have been introduced in the literature (Al Maghayreh, 2010; Garg, 2002; Chase & Garg, 1998). A brief review of these methods will be given in Section 4. However, most of these methods work efficiently for only certain classes of predicates. It has been proved that verifying whether a run of a distributed program satisfies certain property (predicate) or not is, in general, an NP-complete problem (Garg, 2002).
In this paper, a genetic algorithm is used to develop a more powerful technique for detecting distributed predicates. This technique can work efficiently for predicates under the possibly modality (a predicate under the possibly modality is evaluated to true if it is true in at least one global state (Garg, 2002)). A genetic algorithm is a popular artificial intelligent search technique that can be used effectively to solve problems with exponential size search space which is the case in distributed predicates’ detection. In Section 5, we will give a brief introduction to genetic algorithms.