Searching Pareto Solutions of Bi-objective NVP System Design Problem with Breadth First Search Method

The n-version programming (NVP) is a programming approach for constructing fault tolerant software systems. This approach employs functionally equivalent, yet independently developed software components. Each component is independently designed and implemented to meet the same system requirements. The same set of inputs is supplied to all n versions and they produce their own results. A decision mechanism then gathers the results from n versions and determines the result to be delivered to the user. In general, the NVP design problem has been formulated as the single-objective problem maximizing the reliability under the constraint of the cost limit. For such formulations, the dynamic programming or the genetic algorithms have been used. They are, however, time-consuming and do not guarantee to produce the least-dominated solutions. In this paper, reformulate NVP design problem as the multi-objective optimization problem that seek Pareto solutions, and we then propose an algorithm that employs the BFS (breadth-first search) method to find the Pareto solutions under practical computation time