Linear-time algorithms for computing the reliability of bipartite and (# 2) star distributed computing systems

Let S=(V,F) denote a distributed computing system with star topology, where V is the set of nodes of S and F is the set of files distributed in V. The problem of computing the reliability of S has been shown to be #P-complete. Therefore, all known exact algorithms for this problem have exponential time complexity. This study presents two linear-time algorithms to compute the reliability of two restricted subclasses of S. The first algorithm runs in O(|F|) when the file distribution is limited to being bipartite and non-separable. The second algorithm runs in O(|V|), when each file is allocated to at most two distinct nodes and each node contains at most two distinct records. If the failure and working probabilities of every node are identical, then the computation can be accelerated to O(log(|V|)) time by means of the Fibonacci number and the Lucas number.