A BDD-Based Approach to Reliability-Optimal Module Allocation in Networks

摘要

We consider the problem of rinding an allocation of program modules to computing nodes of a distributed system. The objective of this problem is to maximize the probability of successfully executing these modules. Nodes and links of the distributed system are assumed to be subject to failures. We propose an algorithm for this problem which uses Ordered Binary Decision Diagrams (OBDDs) extensively. Recently OBDDs have gained attention as a powerful means for reliability evaluation. In this paper we show that the useful properties of OBDDs are also exploited effectively in the context of reliability optimization. Through experiments, we show that the intensive use of OBDD operations leads to a significant saving of computation time.