The distributed program reliability analysis on ring-type topologies

Distributed computing system (DCS) has become very popular for its high fau lt-tolerance, potential for parallel processing, and better reliability per formance. One of the important issues in the design of the DCS is the relia bility performance. Distributed program reliability (DPR) is addressed to o btain this reliability measure, In this paper, we propose a polynomial-time algorithm for computing the DPR of ring topology and show that solving the DPR problem on a ring of trees topology is NP-hard. (C) 2001 Elsevier Scie nce Ltd. All rights reserved.