An n-parallel-task graph consists of an input node v0 (the source), an output node vn+1 (the sink), and n intermediate task nodes v1, v2, ..., vn, with each vi, i = 1, ..., n having a (directed) inlink from v0, and a (directed) outlink to vn+1. The source sends each task node exactly one of n distinct inputs, which are then processed and forwarded to the sink. The system is said to work if the output node correctly receives the results for all processed inputs. Nodes and links may fail however. We introduce a replicated version of the n-parallel-task graph in which node vi is replicated ri times, i = 0, 1, ..., n + 1, with each copy of a task node possessing an inlink from each of the r0 copies of the source, as well as an outlink to each of the rn+1 copies of the sink. The replicated n-parallel-task graph works if and only if there exists an output node which correctly receives the results for all processed inputs. We give an O(24rn+1r0n + 2rn+1r0 &Sgr;ni=1ri) algorithm to compute the reliability of replicated n-parallel-task graphs, for arbitrary replication indices ri, generalizing a previous result of Liang and Jan for the uniformly replicated case, i.e. ri = r, i = 0, ..., n + 1. We also give conditions under which the uniformly replicated case may be solved in O(24r log n) time. For constant ri and r, the nonuniform case requires linear time, while the uniform case requires logarithmic time.
