Using Genetic Programming to Identify Tradeoffs in Self-Stabilizing Programs: A Case Study

We focus on the use of genetic programming to identify trade-offs between closure and convergence properties of a stabilizing program. Closure property characterizes the behavior in the absence of faults whereas convergence property characterizes the recovery from an arbitrary state to a legitimate state. We describe how genetic programming (GP) can be applied to identify a trade-off for the behaviors in the absence of faults and in the presence of faults. This approach uses BDD (Binary Decision Diagram) based techniques. Subsequently, we use two objectives: closure and maximum convergence time and utilize NSGA-II (a multi-objective optimization algorithm) to identify the trade-off between the performances. We use the classic K-state token ring program to illustrate the trade-off and run experiments for three different approaches: (1) where we only consider trade-off based on process 0, (2) where only consider trade-off based on non-zero processes, and (3) where we consider both trade-offs. Several interesting results are found such as, special process (marked N - 3 in the K-state program) plays a critical role in providing the trade-off, while process 1 is the least important.