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

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

0.00 Avg rating0 Votes
Article ID: iaor20042019
Country: United Kingdom
Volume: 30
Issue: 11
Start Page Number: 1697
End Page Number: 1712
Publication Date: Sep 2003
Journal: Computers and Operations Research
Authors:
Keywords: combinatorial analysis
Abstract:

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 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.

Reviews

Required fields are marked *. Your email address will not be published.