RELIABILITY-ANALYSIS OF REPLICATED AND-OR GRAPHS

A computation task running in distributed systems can be represented a s a directed graph H(V, E) whose vertices and edges may fail with know n probabilities. In this paper, we introduce a reliability measure, ca lled the distributed task reliability, to model the reliability of suc h computation tasks. The distributed task reliability is defined as th e probability that the task can be successfully executed. Due to the a nd-fork/and-join constraint, the traditional network reliability probl em is a special case of the distributed task reliability problem, wher e the former is known to be NP-hard in general graphs. For two-termina l and-or series-parallel (AOSP) graphs, the distributed task reliabili ty can be computed in polynomial time. We consider a graph H-k((V) ove r cap, (E) over cap, named a k-replicated and-or series-parallel (RAOS P) graph, which is obtained from an AOSP graph H(V, E) by adding (k - 1) replications to each vertex and adding proper edges between two ver tices. It can be shown that the RAOSP graphs are not AOSP graphs; thus , the existing polynomial algorithm does not apply. Previously, only e xponential time algorithms as used in general graphs are known for com puting the reliability of H-k((V) over cap, (E) over cap. In this pape r, we present a linear time algorithm with O(K(\V\ + \E\)) complexity to evaluate the reliability of the graph H-k((V) over cap, (E) over ca p), where K = max{k(2)2(2k), 2(3k)}. (C) 1997 John Wiley & Sons, Inc.