TY - JOUR

T1 - Reliability Analysis of Replicated And-Or Graphs

AU - Liang, De Ron

AU - Jan, Rong Hong

AU - Tripathi, Satish K.

PY - 1997/7

Y1 - 1997/7

N2 - A computation task running in distributed systems can be represented as a directed graph H(V, E) whose vertices and edges may fail with known probabilities. In this paper, we introduce a reliability measure, called the distributed task reliability, to model the reliability of such computation tasks. The distributed task reliability is defined as the probability that the task can be successfully executed. Due to the and-fork/and-join constraint, the traditional network reliability problem is a special case of the distributed task reliability problem, where the former s known to be NP-hard in general graphs. For two-terminal and-or series-parallel (AOSP) graphs, the distributed task reliability can be computed in polynomial time. We consider a graph Hk(V̂, Ê), named a k-replicated and-or series-parallel (RAOSP) 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 vertices. It can be she wn that the RAOSP graphs are not AOSP graphs; thus, the existing polynomial algorithm does not apply. Previously, only exponential time algorithms as used in general graphs are known for computing the reliability of Hk(V̂, Ê). In this paper, we present a linear time algorithm with O(K(|V| + |E|)) complexity to evaluate the reliability of the graph Hk(V̂, Ê), where K = max{k222k, 23k}.

AB - A computation task running in distributed systems can be represented as a directed graph H(V, E) whose vertices and edges may fail with known probabilities. In this paper, we introduce a reliability measure, called the distributed task reliability, to model the reliability of such computation tasks. The distributed task reliability is defined as the probability that the task can be successfully executed. Due to the and-fork/and-join constraint, the traditional network reliability problem is a special case of the distributed task reliability problem, where the former s known to be NP-hard in general graphs. For two-terminal and-or series-parallel (AOSP) graphs, the distributed task reliability can be computed in polynomial time. We consider a graph Hk(V̂, Ê), named a k-replicated and-or series-parallel (RAOSP) 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 vertices. It can be she wn that the RAOSP graphs are not AOSP graphs; thus, the existing polynomial algorithm does not apply. Previously, only exponential time algorithms as used in general graphs are known for computing the reliability of Hk(V̂, Ê). In this paper, we present a linear time algorithm with O(K(|V| + |E|)) complexity to evaluate the reliability of the graph Hk(V̂, Ê), where K = max{k222k, 23k}.

UR - http://www.scopus.com/inward/record.url?scp=0347770173&partnerID=8YFLogxK

U2 - 10.1002/(SICI)1097-0037(199707)29:4<195::AID-NET2>3.0.CO;2-A

DO - 10.1002/(SICI)1097-0037(199707)29:4<195::AID-NET2>3.0.CO;2-A

M3 - 期刊論文

AN - SCOPUS:0347770173

VL - 29

SP - 195

EP - 203

JO - Networks

JF - Networks

SN - 0028-3045

IS - 4

ER -